Fault-tolerant romanized input method for non-roman characters

Abstract

Fault-tolerant systems and methods to process and correct input spelling errors for non-Roman based languages such as Chinese, Japanese, and Korean (CJK) are disclosed. The method may be applied to a Chinese input method using pinyin. For example, the method may generally include receiving a pinyin input representing characters in Chinese, the input having at least one original pinyin, identifying potentially incorrect pinyins in the input, expanding each potentially incorrect pinyin to at least one additional alternative pinyin, each pair of potentially incorrect and corresponding alternative pinyin having a proximity measurement, converting each pinyin in the input and each alternative pinyin to Chinese characters, computing likelihoods of possible conversions of the pinyin input to Chinese characters, each possible Chinese conversion being a combination of the converted original and/or alternative pinyins of the input, the probabilities being based on the proximity measurement and optionally on a context of the possible Chinese conversion, and determining a most likely Chinese conversion from the possible conversions.

1 . A fault-tolerant input processing method, comprising: 
 receiving an input in a format representing characters in a language, the input having at least one original component;    identifying potentially incorrect components of the input;    expanding each potentially incorrect component of the input to at least one additional alternative component in the format, each pair of the potentially incorrect component of the input and the corresponding additional alternative component having a proximity measurement;    converting each component of the input and each additional alternative component in the format to the language;    computing likelihoods of possible conversions of the input to characters in the language, each possible conversion being a combination of the converted original and/or alternative components of the input, the likelihoods being based at least in part on the proximity measurement; and    determining a most likely conversion to characters in the language from the possible conversions of the input.    
   
   
       2 . The method of  claim 1 , wherein the identifying potentially incorrect components of the input is based on pairs of confusingly similar components.  
   
   
       3 . The method of  claim 1 , wherein the identifying potentially incorrect components of the input is based on confusing pairs of vowels and consonants.  
   
   
       4 . The method of  claim 1 , wherein each potentially incorrect component is associated with at least one additional confusingly similar alternative component and wherein the expanding includes expanding each potentially incorrect component to every additional alternative component associated with the potentially incorrect component.  
   
   
       5 . The method of  claim 1 , wherein the converting of each component is one of converting each component individually and converting multiple components jointly.  
   
   
       6 . The method of  claim 1 , wherein the computing likelihoods is also based on a context of the possible conversion.  
   
   
       7 . The method of  claim 1 , wherein the determining the most likely conversion includes determining more than one most likely conversion.  
   
   
       8 . The method of  claim 1 , wherein the most likely conversion includes a first possible conversion comprising only converted original components of the input and a second possible conversion comprising at least one converted alternative component of the input if the likelihood of the second possible conversion exceeds the likelihood of the first possible conversion by a predetermined threshold.  
   
   
       9 . The method of  claim 1 , wherein the language is a non-Roman based language.  
   
   
       10 . The method of  claim 1 , wherein the language is Chinese and the format is pinyin.  
   
   
       11 . The method of  claim 1 , wherein the input is a user search query.  
   
   
       12 . A fault-tolerant input system, comprising: 
 a receiver,adapted to receive an input having at least one original component in a format representing characters in a language;    an identifier adapted to identify potentially incorrect components of the received input;    an expander adapted to expand each potentially incorrect component of the received input to at least one additional alternative component in the format, each pair of the potentially incorrect component of the input and the corresponding additional alternative component having a proximity measurement;    a converter adapted to convert each component of the received input and each additional alternative component in the format to the language;    a computing module adapted to compute likelihoods of possible conversions of the received input to characters in the language, each possible conversion being a combination of the converted original and/or alternative components of the received input, the likelihoods being based at least in part on the proximity measurement; and    an output module adapted to determine a most likely conversion to characters in the language from the possible conversions of the input.    
   
   
       13 . The system of  claim 12 , wherein the identifier is further adapted to identify based on pairs of confusingly similar components.  
   
   
       14 . The system of  claim 12 , wherein the identifier is further adapted to identify based on confusing pairs of vowels and consonants.  
   
   
       15 . The system of  claim 12 , wherein each potentially incorrect component is associated with at least one additional confusingly similar alternative component and wherein the expander is further adapted to expand each potentially incorrect component to every additional alternative component associated with the potentially incorrect component.  
   
   
       16 . The system of  claim 12 , wherein the converter is further adapted to convert each component by one of converting each component individually and converting multiple components jointly.  
   
   
       17 . The system of  claim 12 , wherein the computing module is further adapted to compute likelihoods based on a context of the possible conversion.  
   
   
       18 . The system of  claim 12 , wherein the output module is further adapted to determine more than one most likely conversion.  
   
   
       19 . The system of  claim 12 , wherein the most likely conversion includes a first possible conversion comprising only converted original components of the input and a second possible conversion comprising at least one converted alternative component of the input if the likelihood of the second possible conversion exceeds the likelihood of the first possible conversion by a predetermined threshold.  
   
   
       20 . The system of  claim 12 , wherein the language is a non-Roman based language.  
   
   
       21 . The system of  claim 12 , wherein the language is Chinese and the format is pinyin.  
   
   
       22 . The system of  claim 12 , wherein the system is a search engine and the received input is a search query.  
   
   
       23 . A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium on which are stored instructions executable on a computer processor, the instructions including: 
 receiving an input in a format representing characters in a language, the input having at least one original component;    identifying potentially incorrect components of the input;    expanding each potentially incorrect component of the input to at least one additional alternative component in the format, each pair of the potentially incorrect component of the input and the corresponding additional alternative component having a proximity measurement;    converting each component of the input and each additional alternative component in the format to the language;    computing probabilities of possible conversions of the input to characters in the language, each possible conversion being a combination of the converted original and/or alternative components of the input, the probabilities being based at least in part on the proximity measurement; and    determining a most likely conversion to characters in the language from the possible conversions of the input.    
   
   
       24 . The computer program product of  claim 23 , wherein the identifying potentially incorrect components of the input is based on pairs of confusingly similar components.  
   
   
       25 . The computer program product of  claim 23 , wherein the identifying potentially incorrect components of the input is based on confusing pairs of vowels and consonants.  
   
   
       26 . The computer program product of  claim 23 , wherein each potentially incorrect component is associated with at least one additional confusingly similar alternative component and wherein the expanding includes expanding each potentially incorrect component to every additional alternative component associated with the potentially incorrect component.  
   
   
       27 . The computer program product of  claim 23 , wherein the converting of each component is one of converting each component individually and converting multiple components jointly.  
   
   
       28 . The computer program product of  claim 23 , wherein the computing probabilities is also based on a context of the possible conversion.  
   
   
       29 . The computer program product of  claim 23 , wherein the determining the most likely conversion includes determining more than one most likely conversion.  
   
   
       30 . The computer program product of  claim 23 , wherein the most likely conversion includes a first possible conversion comprising only converted original components of the input and a second possible conversion comprising at least one converted alternative component of the input if the probability of the second possible conversion exceeds the probability of the first possible conversion by a predetermined threshold.  
   
   
       31 . The computer program product of  claim 23 , wherein the language is a non-Roman based language.  
   
   
       32 . The computer program product of  claim 23 , wherein the language is Chinese and the format is pinyin.  
   
   
       33 . The computer program product of  claim 23 , wherein the input is a user search query.  
   
   
       34 . A method for generating proximity measurements, comprising; 
 collecting user inputs in a format representing characters in a language and rates of user selection of corresponding candidates decoded from the user inputs into the language;    identifying user inputs having a low rate of candidate selection as non-selected inputs;    assigning a modified input close in confusion proximity to each corresponding non-selected input as a corresponding intended input, the modified input having a higher rate of candidate selection than the corresponding non-selected input; and    determining the proximity measurement for each pair of modified input and non-selected input based on a percentage of the corresponding non-selected input is entered as input without a user selection of any of the decoded candidates being made.    
   
   
       35 . The method of  claim 34 , wherein the confusion proximity is based on a list of pairs of confusingly similar elements in the format and the modified input differs from the corresponding non-selected input by one or more pairs of the confusingly similar elements.  
   
   
       36 . The method of  claim 34 , wherein the language is a non-Roman based language and the format is a Romanized representation of the language.  
   
   
       37 . The method of  claim 34 , wherein the language is Chinese and the format is pinyin.  
   
   
       38 . The method of  claim 34 , wherein the user inputs are user search queries.