Automatic spelling correction for machine translation

[0001] This application claims the benefit under 35 U.S.C. §119 of U.S. Patent Application No. 60/842,546, titled “Automatic Spelling Correction for Machine Translation,” filed Sep. 5, 2006, which is incorporated by reference herein in its entirety.

[0002] This application incorporates by reference the entire disclosure of U.S. Provisional Application No. 60/775,570 entitled “Encoding and Adaptive, Scalable Accessing of Distributed Models,” filed Feb. 21, 2006.

[0003] The subject matter of this specification relates generally to machine translation.

[0004] The World Wide Web (the “web”) includes web pages having text content written in a wide variety of natural languages. To avoid the time and expense of translating these web pages manually, machine translation systems have been adapted to translate text in web pages. For example, some online machine translation services allow a user to submit a Universal Resource Locator (URL) of a web page. The translation service obtains text from the web page located at the submitted URL, translates the text, and outputs a translation for display to the user.

[0005] A drawback of machine translation systems is that such systems may assume that the text has correct spelling. Any incorrectly spelled word in the input text may result in an incorrect, incomplete, or incomprehensible translation. Asking the author of the web page or the user requesting the translation to correct the spelling in the web page would generally be impractical.

[0006] In general, one aspect of the subject matter described in this specification can be embodied in methods that include receiving a text input including words in a source language for translation; identifying one or more words in the text input as suspect words; for each suspect word, identifying one or more candidate words; determining a score for the text input; determining a score for each of one or more candidate inputs, each candidate input being the text input with one or more of the suspect words each replaced by a respective candidate word; selecting a candidate input whose score is highest among the scores for the candidate inputs and is greater than the score for the text input by at least a predefined threshold, if any, and otherwise selecting the text input; and providing as the translation of the text input into a target language a translation of the selected candidate input into the target language if the candidate input was selected, or a translation of the text input into the target language if the text input was selected. Other embodiments of this aspect include corresponding systems, apparatus, computer program products, and computer readable media.

[0007] In general, another aspect of the subject matter described in this specification can be embodied in methods that include receiving a text input including words in a source language for translation; identifying one or more words in the text input as suspect words; for each suspect word, identifying one or more candidate words; obtaining from a machine translation system a translation of the text input into a target language and a translation of each of one or more candidate inputs into the target language, each candidate input being the text input with one or more of the suspect words each replaced by a respective candidate word; determining a score for the text input translation; determining a score for each of the candidate input translations; and providing as the translation of the text input into the target language a candidate input translation whose score is highest among the scores for the candidate input translations and is greater than the score for the text input translation by at least a predefined threshold, if any, or the text input translation. Other embodiments of this aspect include corresponding systems, apparatus, computer program products, and computer readable media.

[0008] Particular embodiments of the subject matter described in this specification can be implemented to realize one or more of the following advantages. Machine translation of text can be more efficient. Spelling errors or regional spelling variations in text can be accounted for by a translation system when the translation system is attempting to translating the text.

[0009] The details of one or more embodiments of the subject matter described in this specification are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages of the subject matter will become apparent from the description, the drawings, and the claims.

[0016] Like reference numbers and designations in the various drawings indicate like elements.

[0017] FIG. 1 is a block diagram illustrating a machine translation system in context. One or more client devices 102, one or more document hosts 104, and a machine translation system 106 are interconnected by a data communication network 108. The network 108 can include, without limitation, a local area network (LAN), a wide area network (WAN), wired or wireless networks, the public Internet, or any combination of them.

[0018] A client device 102 can be any device that can communicate with other computers, systems, or devices. Examples of client devices include desktop computers, notebook computers, network terminals, personal digital assistants (PDAs), media player devices, mobile phones, smartphones, set-top boxes, video game consoles, and so on. The client device 102 can include one or more processors, volatile memory, non-volatile memory, output devices (e.g., a display, an audio output), and input devices (e.g., keyboard, mouse, buttons). In some implementations, the client device includes an application (e.g., a web browser). A user can access a web-based user interface of the machine translation system 106 or document hosts 104 through the web browser, for example.

[0019] The machine translation system 106 translates documents containing text written in natural (i.e., human) languages. The machine translation system 106 translates text written in a source natural language into text written in a target natural language. The text input, the text to be translated, can be provided by a user or retrieved by the machine translation system 106. The output of the machine translation system 106, the text in the target language, can be displayed to a user, used as an input of another process, and/or stored in storage (e.g., in any form of volatile or non-volatile memory).

[0020] In some implementations, the text input to be translated is provided by a user. For example, a user can access, from a client 102, a web-based interface to the machine translation system 106. The web-based interface allows the user to enter and submit a block of text to be translated in a fillable online form, to upload a document file containing the text to be translated (e.g., a plain text document, a Portable Document Format (PDF) document, etc.), or to submit a URL of a web page containing the text to be translated. The user can also specify the source language and the target language. The machine translation system 106 receives the text input, translates the input, and outputs the translation to the user by displaying the translation at the client 102 or transmitting a document file containing the translation to the client 102.

[0021] In some other implementations, the machine translation system 106 can be configured by a user or an administrator to automatically retrieve the text input. For example, the machine translation system 106 can be configured to automatically retrieve and translate documents from a particular domain or at particular URLs. The documents can be retrieved from document hosts 104, where the documents are stored.

[0022] The machine translation system 106 can include a plurality of computers (e.g., servers). In some implementations, the machine translation system 106 is a distributed system. The distributed system can be implemented in different manners. Partition and replication are two examples of various techniques available for implementing the distributed system. In partition, a particular item within such a system, e.g., a database server or a processing server, is divided or partitioned into different partitions that are physically located on different machines (e.g., computers), respectively. Each partition is less than the entire item and different partitions can be different from one another in some implementations and can have some degree of overlap in other implementations. Partition allows a large item to be implemented in the system without being limited to the capacity of a single machine. Because different partitions are at different machines and can be accessed separately, the partition can, among other beneficial features, handle high load and allow for scalability and reliability. The scale and other specific details of the partition can certainly vary depending on the requirements and restraints in a particular automated processing system. A large database, for example, may be difficult to store in a single machine (e.g., a database server) or it may not be economical to use a single expensive machine to store the large database. Accordingly, the large database may be partitioned into a number of smaller database partitions so that each of a number of selected machines has a sufficient storage to store each database partition. Different machines may be networked to operate as a “virtual” single database to a client accessing the database. A processing server may also be partitioned into different partitioning processing servers where each partitioning processing server provides a portion of the processing function of the original processing server and different partitioning processing servers are designed to partition mostly different processing functions.

[0023] Replication is another technique for the distributed system and is different from partition. In replication, a particular item within such a system, e.g., a database server or a processing server, is duplicated or cloned onto one or more replica machines such as computers. Each replica may be substantially identical to the item being replicated in function and other aspects. Replication allows an item to be implemented in a way that increases the availability or the capacity for any function of the item being replicated, to reduce the latency or delay in accessing any function of the item being replicated, and to provide redundancy for any function of the item being replicated. Because a single item usually has a limited capacity, replication makes the function of the item being replicated available to multiple requests from clients when such requests are made either the same time or processing and serving of the different requests overlap in time. The redundancy of the replication is that, if one machine for the item fails, one or more other replicated machines for the item are still available to the system. Notably, the scale and other details of the replication can vary depending on the requirements and restraints in a particular automated processing system. A highly used database, for example, may be replicated on different database servers. As another example, a processing server may be replicated into one or more replica processing servers that can operate in parallel with one another. Like the partition, replication may be implemented to be invisible to a client accessing the system because different machines that replicate the same processing server may be networked to operate as a “virtual” single processing server to a client accessing the database.

[0024] A replication design, when implemented, can incorporate a load balancing mechanism to monitor the work load of different machines for the replication and, based on the work load, to manage or distribute incoming work load to the different machines. This load balancing mechanism can be implemented with different load balancing policies depending on the requirements and constraints of the specific automated processing system. As an example, the load balancing mechanism may be implemented to reduce the delay in accessing a particular function or a piece of information in the replicated part of the system by directing new requests to a replicated machine operating in a light load or in an idle mode.

[0025] The load balancing mechanism may be extended to managing operations of different machines that are not exactly replicas of one another as described above. For example, several processing servers, such as machine translation servers, may operate based on different language translation resources using the same machine translation scheme (e.g., all are statistical machine translation (“SMT”) servers or servers but with different language models). Here, some SMT servers may produce high-quality translations at slow speeds while others may produce low-quality translations at high speeds. A load balancing mechanism may be implemented to control the translation tasks of different segments of a document or different documents based on one or more considerations, such as the quality and timing requirements and constraints. In this example, the load balancing mechanism, although its name still suggesting some “load” balancing operations, does balance something that is not necessarily the work load of different machines. The term “load” balancing as used in this disclosure, thus, is not intended to limit the function to literally loading balancing. Rather, for lack of a better generic term and for the vivid image of the “load balancing,” the term “load balancing mechanism,” “load balancer,” and “load balancing module,” and “load balancing server” are generally used to indicate a mechanism that manages and distributes requests or tasks at different machines in balancing certain considerations associated with the operations and conditions of the machines, the nature of the requests or tasks, and operations and conditions of other parts of the system. In some implementations, the load balancing mechanism may be implemented as a component attached to a machine that is primarily designed for a function different from the load balancing mechanism, or as an individual machine in situations where the balancing mechanism may be handling high traffic to some machines. To be sure, the partition and replication for the distributed machine processing of this disclosure can certainly apply to the load balancing mechanism with different machines when needed.

[0026] In some implementations, a distributed machine translation system can include machine translation resource servers and a translation server. Each machine translation resource server stores and is operable to serve a partition of a collection of machine translation resource data for translation from a source natural language to a target natural language. The respective partitions together constitute the collection of machine translation resource data and each respective partition is less than the collection of machine translation resource data. The translation server is operable to receive source text in the source natural language to be translated into the target natural language and is further operable to obtain machine translation resource data from the machine translation resource servers and to use the obtained machine translation resource data to translate the source text into the target natural language.

[0027] As an example of the above implementation, FIG. 5 is a block diagram of a distributed machine translation (DMT) system to illustrate specific applications of the partition, replication and load balancing of the distributed machine processing of this disclosure. Parameters K, Land M are positive integers (i.e., 1, 2, . . . ). Multiple translation front ends, which may be computer servers, are arranged in parallel with one another and are used to interface with requests from client devices 102 for translating documents and deliver translated documents to client devices 102. A client may be connected on a computer network such as the Internet to which the DMT system in FIG. 5 is linked. The DMT system also includes segment translation servers that interface with translation resource servers to retrieve translation resource data and use the retrieved data to perform translation tasks. A load balancer server is connected between the segment translation servers and the translation front ends to monitor, manage and control exchanges between the translation front ends and the segment servers and operations of the translation front ends and the segment servers. The load balancer server can be replicated with one or more replica load balancer servers.

[0028] The translation front ends are in the replication configuration and operate in parallel with one another. The segment translation servers are also in the replication configuration. The resource servers are partition servers that store partitions of the entire translation resource data and other resources and information for the segment translation servers to perform the translation tasks. Each resource server is shown to have one or more replica resource servers. The translation resource data and other resources and information in the resource servers may include one or more language models for one or more different natural languages, one or more translation models for translations between one or more different source natural languages and one or more different target natural languages, one or more transliteration dictionaries between one or more source natural languages and one or more target natural languages, and other dictionaries or vocabularies. Segment translation servers may implement the same or different machine translation decoding schemes such as rule-based machine translation and statistical machine translation.

[0029] Each translation front end operates to receive a document to be translated by the system and to send the translated document to the client. Upon receiving a document, the translation front end divides the document into multiple smaller segments where each segment may include one or more tokens. One example of a segment is a sentence within a paragraph. The content of a segment may vary in different implementations and may be, range from words to multiple sentences. The front end may direct all segments to the load balancer for distribution to the segment translation servers and a segment translation server processes the assigned segment and translates the assigned segment by using desired translation resource data from one or more resource servers. Each translated segment is then sent back to the original requesting translation front end via the load balancer. After receiving all translated segments back, the original requesting translation front end assembles the translated segments into a translated document and sends the translated document to the client. In some implementations, the front end may first determine whether a proper translation for a segment is available and retrieves that translation as the translated segment without sending that segment to the load balancer.

[0030] A load balancing mechanism, a “back end” load balancing mechanism, that is different from the load balancer, may be implemented between the resource servers and segment translation servers. In one implementation, each segment translation server may include a segment load balancer as part of the server to control, manage, distribute the requests from that segment translation server to the resource servers. The entire segment load balancers together constitute the back end load balancing mechanism. Each segment load balancer can certainly be a separate machine if so desired and may be replicated or even partitioned if needed.

[0031] Each load balancing mechanism can include a monitoring mechanism to monitor activities, conditions and operations of various machines involved in the operations of that load balancing mechanism. This may be implemented in various ways. For example, a communication protocol may be used to provide monitoring communications between the load balancing mechanism and each machine under monitoring.

[0032] FIG. 6 is a block diagram of one implementation of the distributed machine translation system in FIG. 5 that uses a translation model and a language model for a statistical machine translation (SMT). SMT decoders may be implemented in at least some of the segment translation servers. The translation model provides mapping information between the source natural language and the target natural language and scoring information associated with each mapping. In one implementation, for example, the mapping information between the source natural language and the target natural language may be many possible pairs of language strings between the target and source natural languages. The scoring information may include statistical data for each mapping between the source natural language and the target natural language such as a probability a pair of language strings between the target and source natural languages. Other statistical data may also be used as the scoring information. The language model provides many possible language strings in the target natural language and the corresponding language model scoring information for each string. A string includes one or more language tokens and a token can be the smallest language unit handled by the system. Each string can be an n-gram which is a sequence of n tokens in the target natural language, wherein n is a positive integer. Various tokenization techniques may be used to construct a token from one or more of symbols and marks including diacritical marks and punctuation marks, letters, and characters in a natural language. The language model scoring information can include statistical data for each string or n-gram in the language model. The statistical data may include information related to a respective frequency of occurrence of each of the respective n-grams in a corpus of natural language text, such as a probability, a smoothing probability, or a smoothing coefficient that is related to a respective frequency of occurrence of each of the respective n grams in a corpus of target natural language text. The language model scoring information may also include information other than statistical data.

[0033] A SMT decoder in a segment translation server, after receiving an assigned segment to decode, first retrieves needed information from the translation model and then requests needed data from the language model based on the information from the translation model. The SMT decoder computes statistics on all possible translations from various arrangements of tokens in the target natural language and search for the best translation.

[0034] The translation quality of a statistical machine translation (SMT) system, if properly designed, can be improved by increasing either or both of the translation model (TM) and the language model (LM) of the system. Hence, the DMT system in FIG. 6 may have large TM and LM that may require partition in practice. For example, a currently available LM for English is about 200 billion words in size. A large TM may be on the order of magnitude of 200 million words. As more documents are made available on line, the LM may increase further in size. Hence, partition described in this disclosure provides an effective approach to high-quality MT systems using the distributed machine processing in the system configurations shown in this disclosure and other system configurations. Certainly, replication and load balancing are desired features in such DMT systems and other MT systems.

[0035] FIG. 6 further shows one or more servers for other translation resources and data in addition to the LM and TM servers. This feature may be an optional feature to further improve various properties of the system in FIG. 6. For example, a segment translation server may be designed to use other translation resources and data for translating a segment with or without the SMT processing with LM/TM data. Examples for the one or more servers for other translation resources and data include a transliteration dictionary server between the target and source natural languages, a rule-based machine translation server, a transliteration processing server which a rule-based algorithm to produce transliteration data, and other resources that aid the translation from the source natural language to the target natural language.

[0036] The example in FIG. 6 is one implementation of a MT system using LM/TM. This type of systems may include language model servers, a translation model server serving a translation model; and a translation server operable to receive source text in a source natural language to be translated into the target natural language. Each language model server stores and is operable to serve a partition of a language model for the target natural language and the respective partitions together constitute the entire language model. The translation server is operable to perform machine translation obtaining translation model data from the translation model server and obtaining language model data from language model servers.

[0037] As an example, a MT system using LM/TM can include language model servers respectively storing and operable to serve different partitions of a language model for a particular target natural language. The respective partitions together constitute the entire language model and each respective partition is less than the whole of the language model. One or more replica language model servers can be included for each of the language model servers. This system also can include translation model servers respectively storing and operable to serve different partitions of a translation model for translation between the target natural language and a human source language. The respective partitions together constitute the entire translation model and each respective partition is less than the whole of the translation model. One or more replica translation model servers can be included for each of the translation model servers. Translation front ends can also be included where each is operable to divide source text, in the natural language to be translated into the target natural language, into segments in the source natural language. This system can include segment translation servers each operable to perform machine translation obtaining translation model data from the translation model servers and the replica translation model servers and obtaining language model data from language model servers and the replica language model servers. A load balancing module can also be included and is operable to assign the segments to one or more of the segment translation servers for translation, according to translation load at the segment translation servers.

[0038] The machine translation system 106 also includes functionality for determining scores for texts and translations of the texts. For example, the DMT system described above can determine scores for a translation of a text (e.g., a document) using statistical data derived from a language model and/or a translation model. Further, the machine translation system 106 can include functionality for determining scores for texts. In some implementations, a text is scored using statistical data in a language model for the source language of the text. The score can be determined as a probability of occurrence of the text based on the statistical data for the words in the text. In some implementations, in the DMT system, the text scoring functionality can be included as modules, instruction sets, or the like in the translation servers or servers for additional resources described above; or they can be in additional servers.

[0039] The machine translation system 106 can perform translation using any of a number of machine translation techniques. In some implementations, a statistical machine translation technique is used to perform translation from a source language to a target language based on a translation model associated with the source and target languages and a language model associated with the target language. The machine translation system 106 can include one or more computers, such as computer servers, for storing the translation models and language models used in the machine translation processes and for serving data from those models to other parts of the machine translation system 106. In other implementations, the machine translation system 106 implements a rules-based machine translation technique, or a hybrid statistical and rule-based technique, and the machine translation system 106 can include servers for storing the rules.

[0040] In some other implementations, translation can be performed using translation templates or patterns that might be applied recursively. An example of a translation template is a sentence in a source language and a corresponding, pre-specified translation in a target language. The source language sentence includes one or more placeholders for words. The target language translation of the sentence includes placeholders that corresponds to the placeholders in the source language sentence. A translation of a word that appears in place of a placeholder in the source language sentence replaces the corresponding placeholder in the target language translation.

[0041] In some implementations of statistical machine translation techniques, the translation model includes mapping information between the source natural language and the target natural language and scoring information associated with each mapping. The mapping information can include a relation between (1) one or more tokens (e.g., ideograms, words, phrases, etc.) in the source natural language and (2) one or more tokens (e.g., ideograms, words, phrases, etc.) in the target natural language. In some implementations, the mapping information between the source natural language and the target natural language can be many possible pairs of language strings between the target and source natural languages. The scoring information can include statistical data for each mapping, such as a probability of a pair of language strings. Other statistical data can also be used as part of the scoring information.

[0042] The language model for a language includes a collection of possible strings of text in the language and corresponding language model scoring information for each string. A string is made up of one or more language tokens. A token is the smallest language unit handled by the system. Each string can be an n-gram, which is a sequence of n tokens in the language, where n is a positive integer. Various tokenization techniques can be used to construct a token from one or more of symbols and marks, including diacritical marks and punctuation marks, letters, and characters, in the language. The language model scoring information can include statistical data for each n-gram in the language model. The statistical data generally includes data representing a frequency of occurrence of each of the respective n-grams in a corpus of text, such as a probability, a smoothed probability, or a smoothing coefficient that is related to a respective frequency of occurrence of each of the respective n-grams in the corpus of text. The language model scoring information can also include information other than statistical data.

[0043] The language model for a language and a translation model between a source language and a target language can be generated from a large corpus of documents. The corpus of documents may be drawn from a wide variety of sources or from sources of a particular kind. For example, a corpus of documents that is meant to be representative of the English language generally may include English-language documents that are drawn randomly from all over the World Wide Web. A language model that is generated from such a corpus may be used to model the English language generally. As another example, a corpus of documents that is meant to be representative of the English language as used in news articles may include English-language documents that are drawn only from news sources and news organizations. A language model generated from such a corpus can be used to model the English language as used in the news context. Similarly, a translation model may model translation between languages generally or within specific contexts based on the corpus or corpora of documents from which the translation model is generated.

[0044] A vocabulary or dictionary can also be generated from a corpus of documents. In some implementations, the vocabulary or dictionary includes unique words, including any misspelled words, that appear in the corpus of documents and their corresponding frequencies of occurrence within the corpus. In some other implementations, a vocabulary or dictionary includes distinct n-grams that occur in the corpus of documents, where n is a positive integer. In one exemplary implementation, n is 5. A probability of occurrence of a word can be determined based on the frequency of occurrence of the word within the corpus or vocabulary or the frequencies of occurrence of the corresponding n-grams of a specified length within the corpus or vocabulary, and the size of the vocabulary and/or corpus. Depending on the corpus of documents from which the vocabulary is generated, the vocabulary may model the frequencies of words or n-grams in a language generally or in particular contexts. The vocabulary may be considered an extension of the language model.

[0045] In operation, a machine translation system 106 that uses a statistical machine translation technique, after receiving an input to translate, first retrieves needed data from the translation model and then retrieves needed data from the language model based on the information from the translation model. The system computes statistics on many possible translations from various arrangements of tokens in the target natural language and searches for a best translation, which the machine translation system 106 presents to a client 102 or other systems.

[0046] The input into the machine translation system 106 includes text to be translated. The text includes one or more words. Some of these words may be misspelled. If these misspellings are not corrected, the output translation may be incomplete, incorrect, or incomprehensible. The machine translation system 106 may perform automatic spelling correction on the text before translating the text or as part of the search for the best translation, further details of which are described below.

[0047] FIG. 2 is a flow diagram illustrating an example process 200 for automatically correcting spelling in a machine translation input. A text input is received by the machine translation system (202). The text in the text input is written in a source language and may include one or more words. The text input here may be the whole or a part of a document of text to be translated. One or more suspect words in the text input are identified (204). In some implementations, a word is identified as suspect based on the frequency of occurrence of the word. That is, a word may be identified as a suspect word if it has a “low” frequency of occurrence. The frequency of occurrence of a word can be determined from the language model and/or a vocabulary for the language in which the text input is written. In some implementations, a “low” frequency of occurrence is a frequency that is below a predefined frequency floor, which may be expressed as an absolute number of occurrences in a corpus or vocabulary. In some implementations, the frequency floor is 50. In another example implementation, the frequency floor is 10. In some implementations, a different floor may be set for different languages, and a floor may be adjusted based on the size of the corpus of documents and/or size of the vocabulary.

[0048] For each identified suspect word, one or more candidate words are identified (206). One or more candidate words are identified for each suspect word. In some implementations, the candidate words are identified from the vocabulary and/or the language model for the source language. In some other implementations, the candidate words are be identified from the vocabularies and/or translation model associated with the source and target languages. In some implementations, words below a predefined frequency threshold are ignored when searching a vocabulary for possible candidate words. The frequency threshold may be an absolute number or a function of the frequency of the suspect word.

[0049] In some implementations, the candidate words are those words in the vocabulary having an edit distance (e.g., the Levenshtein distance) from the suspect word that is less than a predefined edit distance threshold (but greater than 0). In some implementations, the edit distance threshold is 2; and a candidate word is a word that has an edit distance of 1 from the suspect word. In some other implementations, the edit distance threshold is 3; and a candidate word is a word that has an edit distance of 1 or 2 from the suspect word.

[0050] A score for the text input as it was received by the machine translation system is determined (208). In some implementations, the score for the text input is the probability of occurrence of the text input, determined using a language model for the source language of the text input. One or more candidate inputs written in the source language are generated and scores for these candidate inputs are determined (210). In some implementations, a candidate input is the text input with one or more of its suspect words replaced by a respective candidate word. In some implementations, the score for the text input or a candidate input is the probability of occurrence of the text input or the candidate input, respectively, determined using a language model for the source language. For example, if the text input and the candidate input are sentences, then the score of the text input or a candidate input is the probability of occurrence of the sentence, which can be calculated as the product of conditional probabilities of the words in the sentence. For example, the probability of occurrence of the sentence can be calculated as the probability of the first word in the sentence multiplied by the probability of the second word given the first word, multiplied by the probability of the third word given the second word, and so forth. In some implementations the probability of occurrence of a word is the frequency of occurrence of the word, as indicated in the language model, divided

[0051] In some implementations, particular techniques can be used to make the process of finding the highest scoring input more efficient. In an example implementation, dynamic programming is used. In another example implementation, a score is determined for an input using less than all of the words of the input. For example, if the suspect word is near either end of the input, then the score may be determined using the words in that vicinity.

[0052] If there is a candidate input whose score is greater than the score of the text input by at least a predefined threshold (212—Yes), then the highest scoring candidate input (whose score is greater than the score of the text input by at least the predefined threshold) is selected (216). If multiple candidate inputs have scores greater than the score of the text input by at least the predefined threshold, the candidate input among the candidate inputs with the highest score (e.g., highest probability of occurrence) is selected. If none of the candidate inputs have scores that are higher than the score of the text input by the predefined threshold (212—No), the text input is selected (214). In some implementations, the predefined threshold is N times the text input score, where N is a real number greater than 1.0. In some implementation, N is 10. In some other implementations, N is 2 or 3.

[0053] The selected input is translated into a target language (218). If a candidate input was selected, then the selected candidate input is translated. If the text input was selected (because none of the candidate inputs had a score higher than the threshold), then the text input is translated. The translation output can be transmitted to a client 102 for presentation to a user, stored and/or processed further within the machine translation system, or transmitted to other computers for further processing or storage.

[0054] FIGS. 3A-3B are a flow diagram illustrating another example process 300 for automatically correcting spelling in a machine translation input. A text input is received by the machine translation system 106 (302). One or more suspect words in the text input are identified (304). For each identified suspect word, one or more candidate words are identified (306). Blocks 302-306 are the same as blocks 202-206 described above in reference to FIG. 2.

[0055] The text input as received is translated into a target language (308). A score for the translation is determined (310). In some implementations, the score for the translation is the probability of occurrence of the translation. The probability of occurrence of the translation can be determined from a language model for the target language and/or a translation model for translating the source language to the target language.

[0056] One or more candidate inputs in the source language are generated, and the candidate inputs are translated into the target language (312). Scores for the translations of the candidate inputs are determined (314). A candidate input is the text input with one or more of its suspect words replaced by a respective candidate word. In some implementations, the score for a translation is the probability of occurrence of the translation, determined using a language model associated with the target language and/or a translation model associated with the source and target languages.

[0057] If there is a candidate input whose translation has a score that is greater than the score of the translation of the text input by at least a predefined threshold (316—Yes), the highest scoring candidate input translation amongst the candidate input translations is selected (320). If multiple candidate input translations has scores that are greater than the score for the text input translation by at least the threshold, then the candidate translation with the highest score (e.g., highest probability of occurrence) is selected. If there is no candidate input whose translation has a score that is greater than that of the translation of the text input by at least the predefined threshold (316—No), the translation of the text input as received is selected (318). In some implementations, the predefined threshold is that the candidate input translation score be at least N times greater than the text input translation score, where N is a real number greater than 1.0. In some implementations, N is 10. In some other implementations, N is 2 or 3. The selected translation may be transmitted to a client 102 for presentation to a user, stored and/or processed further within the machine translation system, or transmitted to other computers for further processing or storage.

[0058] In some implementations, the process for translating the text inputs and candidate inputs and for determining scores for the translations includes generating a word lattice or word graph representing the text input and the candidate inputs. The word lattice, which includes weights, is provided to the translation module. As part of the translation process, the system selects a path in the word lattice corresponding to one of the input choices. The selected path represents a best (highest scoring) translation among the alternatives. In some implementations, the score threshold criterion is then be applied, if the highest scoring translation is associated with a candidate input, to determine if the translation for the candidate input should be selected. In some other implementations, the highest scoring translation is selected regardless of the score threshold criterion.

[0059] In some implementations, particular techniques are used to identify candidate words efficiently, rather than comparing the suspect word with the entire vocabulary. In some implementations, a trie of prefixes of the suspect word is generated. The trie includes nodes representing prefixes of the suspect word and strings formed from these prefixes that are different from the suspect word. From the trie, strings of a particular edit distance from the suspect word are identified. The identified strings whose frequencies in the vocabulary or language model are above a threshold are identified as candidate words.

[0060] Another optimization technique is to generate from a list of words (e.g., words in the vocabulary with a frequency that is higher than a specified minimum) a mapping from a word with a letter taken out to the original word, and also the word to itself. Such a mapping may have entries like:

[0061] “ca”→“cat can car”

[0062] “at”→“cat bat rat art ate at”

[0063] “ct”→“cat cot act”

[0064] “cat”→“cat cart”

[0065] When identifying candidate words, each letter (if the edit distance criterion is 1 or less; more may be taken out if the edit distance criterion is a larger number) is taken out of the suspect word in turn. For example, if the suspect word is “cet,” the strings “et,” “ct,” “ce,” and “cet” may be generated. Words that map from these strings are identified from the mapping. These words include words that are edit distance 1 from the suspect word, plus some others. A brute force edit distance comparison between these words, which is a smaller set than the entire vocabulary, and the suspect word may then be performed to find the candidate words.

[0066] In some implementations, the identification of candidate words also include identification of candidate combinations of words formed by splitting or dividing the suspect word into two, in order to account for the possibility that the suspect word is a concatenation of two words. An m-letter suspect word may be divided into two words m-l ways. A candidate combination may be substituted for the suspect word. If a candidate input with a candidate word combination is the highest scoring candidate input and its score is higher than that of the text input by at least the predefined threshold, then the candidate input (with the word combination) is selected.

[0067] In some implementations, not all m-l combinations generated from dividing an m-letter suspect need be identified as candidate word combinations. For example, in one exemplary implementation, combinations that leave one-letter words may be ignored. In another implementation, particular word combinations may be identified from a suspect word based on how the letters of the word is written in the source language and/or font used for the text input. That is, in some languages and/or fonts, particular combinations of adjacent letters may include a visually perceivable space. The visually perceivable space indicates a possible location where the author of the text input forgot to insert a whitespace and thus a possible candidate word combination.

[0068] FIG. 4 illustrates an example of a machine translation input and candidate inputs with candidate words substituted for the suspect word. In FIG. 4, the example text input to be translated is the sentence “I love going to the threater.” A suspect word that may be identified in the text input sentence is “threater.” Candidate words that may be identified for the suspect word “threater” may include “theater,” “threat,” “threaten,” as well as divisions of “threater” into two strings, including “t hreater,” “th reater,” “thr eater,” “thre ater,” “threa ter,” “threat er,” and “threate r.” The suspect word may be replaced by any of these candidates to form a candidate input. For example, if “threater” is replaced by “theater,” then the candidate input “I love going to the theater” is formed. If “threater” is replaced by “threa ter,” then the candidate input “I love going to the threa ter” is formed. Scores for text input and the candidate inputs, or for translations of them, may be determined in using processes 200 or 300 as described above.

[0069] The implementations described in this specification can help improve the quality of machine translation by finding and correcting spelling mistakes in the texts to be translated. The systems and techniques described in this specification may also be used to improve machine translation quality for languages that have regional spelling variations (e.g., British English vs. American English) or dialectical variations, as well as improving the machine translation quality of words that are written in an alternative form in the text to be translated (e.g., a noun is written in a plural form that is not known to the language model or the translation model).

[0070] The disclosed and other embodiments and the functional operations described in this specification can be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. The disclosed and other embodiments can be implemented as one or more computer program products, i.e., one or more modules of computer program instructions encoded on a computer readable medium for execution by, or to control the operation of, data processing apparatus. The computer readable medium can be a machine-readable storage device, a machine-readable storage substrate, a memory device, a composition of matter effecting a machine-readable propagated signal, or a combination of one or more them. The term “data processing apparatus” encompasses all apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers. The apparatus can include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them. A propagated signal is an artificially generated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal, that is generated to encode information for transmission to suitable receiver apparatus.

[0071] A computer program (also known as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, and it can be deployed in any form, including as a stand alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program does not necessarily correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub programs, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network.

[0072] The processes and logic flows described in this specification can be performed by one or more programmable processors executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit).

[0073] Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read only memory or a random access memory or both. The essential elements of a computer are a processor for performing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. However, a computer need not have such devices. Computer readable media suitable for storing computer program instructions and data include all forms of non volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and CD ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry.

[0074] To provide for interaction with a user, the disclosed embodiments can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input.

[0075] The disclosed embodiments can be implemented in a computing system that includes a back end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of what is disclosed here, or any combination of one or more such back end, middleware, or front end components. The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (“WAN”), e.g., the Internet.

[0076] The computing system can include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other.

[0077] While this specification contains many specifics, these should not be construed as limitations on the scope of what being claims or of what may be claimed, but rather as descriptions of features specific to particular embodiments. Certain features that are described in this specification in the context of separate embodiments can also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable subcombination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or variation of a subcombination.

[0078] Similarly, while operations are depicted in the drawings in a particular order, this should not be understand as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system components in the embodiments described above should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.

[0079] Thus, particular embodiments have been described. Other embodiments are within the scope of the following claims.