# US 8,788,258 B1 · Machine translation using global lexical selection and sentence reconstruction > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,788,258 B1 - Document ID: US8788258B1 - Status: Granted - Kind: B1 - Application number: 11/686,681 - Filed: 2007-03-15 - Granted: 2014-07-22 - Earliest claimed: 2007-03-15 - Assignees: AT&T Intellectual Property II, L.P. - Applicants: Srinivas Bangalore; Patrick Haffner; Stephan Kanthak - Inventors: Srinivas Bangalore; Patrick Haffner; Stephan Kanthak - Web page: https://patentgrep.com/patent/US8788258B1 ## CPC - G06F 40/44: Statistical methods, e.g. probability models - G11B 27/105: {of operating discs} - G06F 40/58: Use of machine translation, e.g. for multi-lingual retrieval, for server-side translation for client devices or for real-time translation - G11B 27/28: by using information signals recorded by the same method as the main recording {(G11B27/22 takes precedence)} - H04N 5/45: Picture in picture {, e.g. displaying simultaneously another television channel in a region of the screen} - H04N 5/765: Interface circuits between an apparatus for recording and another apparatus - H04N 21/232: Content retrieval operation {locally} within server, e.g. reading video streams from disk arrays {(storage management G06F3/0604; details of querying and searching of video data from a database G06F16/739)} - H04N 21/233: Processing of audio elementary streams {(monitoring, identification or recognition of audio in broadcast systems H04H60/58)} - H04N 21/235: Processing of additional data, e.g. scrambling of additional data or processing content descriptors - H04N 21/25825: {involving client display capabilities, e.g. screen resolution of a mobile phone (optimising the visualisation of content during browsing in the Internet G06F16/9577; processing of terminal status or physical abilities in wireless networks H04W8/22; authentication in wireless network security H04W12/06)} - H04N 21/4316: {for displaying supplemental content in a region of the screen, e.g. an advertisement in a separate window} - H04N 21/47: End-user applications - H04N 21/4828: {for searching programme descriptors (retrieval of video data G06F16/739)} - H04N 21/812: {involving advertisement data (advertising per se G06Q30/02)} - H04N 21/84: Generation or processing of descriptive data, e.g. content descriptors {(systems specially adapted for using meta-information in broadcast systems H04H60/73)} - H04N 21/8456: {by decomposing the content in the time domain, e.g. in time segments} - H04N 21/8547: involving timestamps for synchronizing content - G06F 40/45: Example-based machine translation; Alignment - G10L 15/26: Speech to text systems (G10L15/08 takes precedence) - H04N 21/2662: Controlling the complexity of the video stream, e.g. by scaling the resolution or bitrate of the video stream based on the client capabilities - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G11B: INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER (recording measured values in a way that does not require playback through a transducer G01D9/00; recording or playback apparatus using mechanically marked tape, e.g. punched paper tape, or using unit records, e.g. punched or magnetically marked cards G06K; transferring data from one type of record carrier to another G06K1/18; circuits for coupling output of reproducer to radio receiver H04B1/20; gramophone pick-ups or like acoustic electromechanical transducers or circuits therefor H04R) - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION - G10L: SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING ## Abstract Disclosed are systems, methods, and computer-readable media for performing translations from a source language to a target language. The method comprises receiving a source phrase, generating a target bag of words based on a global lexical selection of words that loosely couples the source words/phrases and target words/phrases, and reconstructing a target phrase or sentence by considering all permutations of words with a conditional probability greater than a threshold. ## Claims ### Claim 1 A method comprising: receiving a source phrase in a source language; classifying the source phrase into a phrase meaning; matching the phrase meaning to a target phrase automaton in a target language, the target phrase automaton comprising a plurality of states and a plurality of arcs interconnecting the plurality of states to define a sentence path, each of the plurality of states defining a word position slot for inserting a word from a bag of words, and each of the plurality of arcs associated with a pre-defined insertion cost for inserting the word from the bag of words based on a previous state in the sentence path, wherein the predefined insertion cost has one of a positive and negative value which is associated with one of penalizing and rewarding the sentence path based on how many words are in the sentence path in order to produce more words in a target sentence relative to the source phrase; determining, for each word position slot in each target phrase automaton, a target word possibility from the bag of words associated with the word position slot based on at least one of a lexical translation of words in the source phrase and a phrase-to-phrase mapping; calculating a target sentence probability for the sentence path based at least on the pre-defined insertion cost associated with each of the plurality of arcs for the sentence path; and upon determining that the sentence path has a probability above a threshold, constructing the target sentence using the sentence path. ### Claim 2 (depends on 1) The method of claim 1, wherein the target word possibility for each word position is weighted by a target language model. ### Claim 3 (depends on 1) The method of claim 1, wherein the target word possibility for each word position is detected independently. ### Claim 4 (depends on 1) The method of claim 1, further comprising: adjusting a length of the target sentence by adding optional deletions when constructing the target sentence. ### Claim 5 (depends on 1) The method of claim 1, wherein the determining for each word position slot of the target word possibility does not use information about previous words and subsequent words. ### Claim 6 (depends on 1) The method of claim 1, wherein function words in the target word possibility of each word position serve as attributes on contentful lexical items. ### Claim 7 (depends on 6) The method of claim 6, wherein the attributes are at least one of definiteness, tenses and case. ### Claim 8 A system comprising: a processor; and a computer-readable storage medium storing instructions which, when executed by the processor, cause the processor to perform operations comprising: receiving a source phrase in a source language; classifying the source phrase into a phrase meaning; matching the phrase meaning to a target phrase automaton in a target language, the target phrase automaton comprising a plurality of states and a plurality of arcs interconnecting the plurality of states to define a sentence path, each of the plurality of states defining a word position slot for inserting a word from a bag of words, and each of the plurality of arcs associated with a pre-defined insertion cost for inserting the word from the bag of words based on a previous state in the sentence path, wherein the predefined insertion cost has one of a positive and negative value which is associated with one of penalizing and rewarding the sentence path based on how many words are in the sentence path in order to produce more words in a target sentence relative to the source phrase; determining, for each word position slot in each target phrase automaton, a target word possibility from the bag of words associated with the word position slot based on at least one of a lexical translation of words in the source phrase and a phrase-to-phrase mapping; calculating a target sentence probability for the sentence path based at least on the pre-defined insertion cost associated with each of the plurality of arcs for the sentence path; and upon determining that the sentence path has a probability above a threshold, constructing the target sentence using the sentence path. ### Claim 9 (depends on 8) The system of claim 8, wherein the target word possibility for each word position is weighted by a target language model. ### Claim 10 (depends on 8) The system of claim 8, wherein the target word possibility for each word position is detected independently. ### Claim 11 (depends on 8) The system of claim 8, the computer-readable storage medium storing additional instructions which, when executed on the processor, perform a method further comprising: adjusting a length of the target sentence by adding optional deletions when constructing the target sentence. ### Claim 12 (depends on 8) The system of claim 8, wherein the determining for each word position slot of the target word possibility does not use information about previous words and subsequent words. ### Claim 13 (depends on 8) The system of claim 8, wherein function words in the target word possibility of each word position serve as attributes on contentful lexical items. ### Claim 14 (depends on 13) The system of claim 13, wherein the attributes are at least one of definiteness, tenses and case. ### Claim 15 A computer-readable storage device having instructions stored which, when executed by a computing device, cause the computing device to perform operations comprising: receiving a source phrase in a source language; classifying the source phrase into a phrase meaning; matching the phrase meaning to a target phrase automaton in a target language, the target phrase automaton comprising a plurality of states and a plurality of arcs interconnecting the plurality of states to define a sentence path, each of the plurality of states defining a word position slot for inserting a word from a bag of words, and each of the plurality of arcs associated with a pre-defined insertion cost for inserting the word from the bag of words based on a previous state in the sentence path, wherein the predefined insertion cost has one of a positive and negative value which is associated with one of penalizing and rewarding the sentence path based on how many words are in the sentence path in order to produce more words in a target sentence relative to the source phrase; determining, for each word position slot in each target phrase automaton, a target word possibility from the bag of words associated with the word position slot based on at least one of a lexical translation of words in the source phrase and a phrase-to-phrase mapping; calculating a target sentence probability for the sentence path based at least on the pre-defined insertion cost associated with each of the plurality of arcs for the sentence path; and upon determining that the sentence path has a probability above a threshold, constructing the target sentence using the sentence path. ### Claim 16 (depends on 15) The computer-readable storage device of claim 15, wherein the target word possibility for each word position is weighted by a target language model. ### Claim 17 (depends on 15) The computer-readable storage device of claim 15, wherein the target word possibility for each word position is detected independently. ### Claim 18 (depends on 15) The computer-readable storage device of claim 15, wherein the non-transitory computer-readable medium stores additional instructions which, when executed on the computing device, cause the computing device to perform operations further comprising: adjusting a length of the target sentence by adding optional deletions when constructing the target sentence. ### Claim 19 (depends on 15) The computer-readable storage device of claim 15, wherein the determining for each word position slot of the target word possibility does not use information about previous words and subsequent words. ### Claim 20 (depends on 15) The computer-readable storage device of claim 15, wherein function words in the target word possibility of each word position serve as attributes on contentful lexical items. ### Claim 21 (depends on 20) The computer-readable storage device of claim 20, wherein the attributes are at least one of definiteness, tenses and case.