Text auto-correction via N-grams

• US 9,779,080 B2
• Filed: 07/09/2012
• Issued: 10/03/2017
• Est. Priority Date: 07/09/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Caskey, Sasha P, Kanevsky, Dimitri, Kozloski, James R., Sainath, Tara N
• Primary Examiner(s): Ortiz Sanchez, Michael
• Application Number:
  US13/544,941
• Publication Number:
  US 20140012567A1
• Time in Patent Office: 1,912 Days
• Field of Search: 704 1- 10
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

An input text string is received that contains characters or words. The input text string can be completed or corrected using contact scores based on n-grams. In addition, a subsequent text string and a preceding text string for the input text string are also identified, again using n-gram scores. A corrected text string is created by inserting the preceding text string before the input text string and appending the subsequent text string after the input text string.

Claims

1. A method for text auto-correction, the method comprising:

receiving an input text string on an electronic text input interface device, the input text string comprising N words and a categorical topic;

generating a subsequent text string comprising a plurality of N−

1 subsequent words forming a subsequent phrase within the categorical topic by determining probabilities that the N−

1 subsequent words follow the N words in the input test string;

generating a preceding text string comprising a plurality of N−

1 preceding words forming a preceding phrase for the input text string within the categorical topic by determining probabilities that the N−

1 preceding words following precede the N words in the input test string;

creating a corrected text string by inserting the preceding phrase before the input text string and appending the subsequent phrase after the input text string; and

displaying the corrected text string on the electronic text input interface device.

2. The method of claim 1, wherein:

the step of receiving the input text string further comprises receiving an input text string comprising the N words forming an input phrase; and

the method further comprises replacing the input phrase with a substitute input phrase comprising N words based on N-gram content scores associated with the input phrase comprising the N words and the substitute input phrase expressing a probability of accuracy of content.

3. The method of claim 2, wherein the step of replacing the input phrase with the substitute input phrase further comprises:

identifying a plurality of sub-phrases in the input phrase, each sub-phrase comprising a number of words less than the N words forming the input phrase;

identifying a plurality of substitute sub-phrases, each substitute sub-phrase associated with one of the sub-phrases in the input phrase;

forming a plurality of candidate substitute input phrases, each candidate substitute input phrase comprising a unique combination of the input phrase and at least one of the plurality of substitute sub-phrases;

assigning a content score to the input phrase and to each one of the candidate substitute input phrases;

selecting the candidate substitute input phrase having a highest content score as the substitute input phrase; and

replacing the input phrase with the substitute input phrase only if a substitute input phrase content score is higher than an input phrase content score.

4. The method of claim 1, wherein:

the step of receiving the input text string comprises;

receiving the N words comprising a first language; and

translating the N words to a second language; and

the steps of generating the subsequent text string and the preceding text string further comprise generating a subsequent text string comprising a plurality of N−

1 subsequent words in the second language forming a subsequent phrase and generating a preceding text string comprising a plurality of N−

1 preceding words in the second language forming a preceding phrase.

5. The method of claim 1, wherein:

the step of receiving the input text string further comprises receiving an input text string comprising a plurality of N words forming an input phrase in a first language; and

the method further comprises;

replacing the input phrase with a substitute input phrase based on content scores associated with the input phrase and the substitute input phrase expressing a probability of accuracy of content; and

translating the substitute input phrase into a second language.

6. The method of claim 1, wherein the method further comprises locating the input text string in a state graph comprising a plurality of states and a plurality of transitions between pairs of states, each state comprising a given text string and each transition comprising a probability that text strings in a given pair of states associated with that transition comprise a sequence of text strings.

7. The method of claim 6, wherein:

the step of locating the input text string further comprises locating the input text string in an input state; and

the steps of generating a subsequent text string and a preceding text string further comprise;

generating a subsequent state comprising the subsequent text string such that a transition between the input state and the subsequent state comprises a highest probability associated with a sequence comprising the input text string followed by the subsequent text string; and

generating a preceding state comprising the preceding text string such that a transition between the input state and the preceding state comprises a highest probability associated with a sequence comprising the preceding text string followed by the input text string.

8. The method of claim 1, wherein:

the step of receiving the input text string further comprises receiving at least one core word; and

the method further comprises completing the input phrase containing the core word.

9. The method of claim 8, wherein:

step of receiving at least one core word further comprises receiving a plurality of core words; and

the input phrase comprises the plurality of core words such the core words are non-contiguous words in the input phrase.

10. A non-transitory computer-readable storage medium containing a computer-readable code that when read by a computer causes the computer to perform a method for text auto-correction, the method comprising:

receiving an input text string on an electronic text input interface device, the input text string comprising N words and a categorical topic;

generating a subsequent text string comprising a plurality of N−

1 subsequent words forming a subsequent phrase within the categorical topic by determining probabilities that the N−

1 subsequent words follow the N words in the input test string;

generating a preceding text string comprising a plurality of N−

1 preceding words forming a preceding phrase for the input text string within the categorical topic by determining probabilities that the N−

1 preceding words following precede the N words in the input test string;

creating a corrected text string by inserting the preceding phrase before the input text string and appending the subsequent phrase after the input text string; and

displaying the corrected text string on the electronic text input interface device.

11. The non-transitory computer-readable medium of claim 10, wherein:

the step of receiving the input text string further comprises receiving an input text string comprising the N words forming an input phrase; and

the method further comprises replacing the input phrase with a substitute input phrase comprising N words based on content scores associated with the input phrase and the substitute input phrase expressing a probability of accuracy of content.

12. The non-transitory computer-readable medium of claim 11, wherein the step of replacing the input phrase with the substitute input phrase further comprises:

identifying a plurality of sub-phrases in the input phrase, each sub-phrase comprising a number of words less than the N words forming the input phrase;

identifying a plurality of substitute sub-phrases, each substitute sub-phrase associated with one of the sub-phrases in the input phrase;

forming a plurality of candidate substitute input phrases, each candidate substitute input phrase comprising a unique combination of the input phrase and at least one of the plurality of substitute sub-phrases;

assigning a content score to each one of the candidate substitute input phrases; and

selecting the candidate substitute input phrase having a highest content score as the substitute input phrase.

13. The non-transitory computer-readable medium of claim 12, wherein:

the method further comprises assigning a content score to the input phrase; and

the step of replacing the input phrase further comprises replacing the input phrase with the substitute input phrase only if a substitute input phrase content score is higher than an input phrase content score.

14. The non-transitory computer-readable medium of claim 10, wherein:

the step of receiving the input text string comprises;

receiving the N words comprising a first language; and

translating the N words to a second language; and

the steps of generating the subsequent text string and the preceding text string further comprise generating a subsequent text string comprising a plurality of N−

1 subsequent words in the second language forming a subsequent phrase and generating a preceding text string comprising a plurality of N−

1 preceding words in the second language forming a preceding phrase.

15. The non-transitory computer-readable medium of claim 10, wherein:

the method further comprises locating the input text string in an input state of a state graph comprising a plurality of states and a plurality of transitions between pairs of states, each state comprising a given text string and each transition comprising a probability that text strings in a given pair of states associated with that transition comprise a sequence of text strings; and

the steps of generating a subsequent text string and a preceding text string further comprise;

generating a subsequent state comprising the subsequent text string such that a transition between the input state and the subsequent state comprises a highest probability associated with a sequence comprising the input text string followed by the subsequent text string; and

generating a preceding state comprising the preceding text string such that a transition between the input state and the preceding state comprises a highest probability associated with a sequence comprising the preceding text string followed by the input text string.

16. The non-transitory computer-readable medium of claim 10, wherein:

the method further comprises determining the categorical topic related to the N words.

17. The non-transitory computer-readable medium of claim 10, wherein:

the step of receiving the input text string further comprises receiving a plurality of core words; and

the method further comprises completing the input phrase comprising the plurality of core words such the core words are non-contiguous words in the input phrase.

18. A method for text auto-correction, the method comprising:

receiving an input text string on an electronic text input interface device, the input text string comprising N words;

locating the input text string in an input state of a state graph comprising a plurality of states and a plurality of transitions between pairs of states, each state comprising a given phrase and each transition comprising an N-gram score expressing a probability that phrases in a given pair of states associated with that transition comprise a sequence of phrases, the input state comprising an input phrase containing each input word in the N words;

identifying a subsequent state in the state graph comprising a subsequent phrase comprising a plurality of N−

1 subsequent words such that a transition between the input state and the subsequent state comprises an N-gram score expressing highest probability associated with a sequence comprising the input phrase followed by the subsequent phrase;

identifying a preceding state in the state graph comprising a preceding phrase comprising a plurality of N−

1 preceding words such that a transition between the input state and the preceding state comprises an N-gram score expressing highest probability associated with a sequence comprising the preceding phrase followed by the input phrase; and

creating a corrected text string by inserting the preceding phrase before the input phrase and appending the subsequent phrase after the input phrase; and

displaying the corrected text string on the electronic text input interface device.

19. A system for text auto-correction, the system comprising:

a text input interface device to receive an input text string from a user, the text input string comprising N words;

a semantic processing module in communication with the text input device to use an N-gram language model to evaluate the input text string and extend the input text string in at least two directions by generating a subsequent text string comprising a plurality of N−

1 subsequent words forming a subsequent phrase by determining probabilities from the N-gram language model that the N−

1 subsequent words follow the N words in the input text string and generating a preceding text string comprising a plurality of N−

1 preceding words forming a preceding phrase for the input text string by determining probabilities from the N-gram language model that the N−

1 preceding words precede the N words in the input text string and creating a corrected text string by inserting the preceding phrase before the input text string and appending the subsequent phrase after the input text string; and

a user interface in communication with the text input interface and the semantic processing module to display the corrected text string to the user for approval.

20. The system of claim 19, wherein the semantic processing module further comprises:

a content score generator to generate content scores and to associate the content scores with text strings, the content scores expressing a probability of accuracy of content within a given text string;

a content score evaluator in communication with the content score generator to evaluate and to compare content scores associated with text strings; and

a text string modifier in communication with the content score evaluator to create the corrected input text string only if a corrected input text string content score is higher than the input text string content score.

21. The system of claim 20, wherein the content scores comprise N-gram scores for the input text string comprising N characters.

22. The system of claim 19, wherein the semantic processing module further comprises a substitute input text string generator in communication with the content score generator to generate candidate substitute input text strings.

23. The system of claim 22, wherein the substitute input text string generator comprises:

a sub-phrase identifier to identify sub-phrases in the input text string, each sub-phrase comprising a number of characters less than a plurality of characters forming the input text string;

a substitute sub-phrase generator to generate a plurality of substitute sub-phrases, each substitute sub-phrase associated with one of the sub-phrases in the input text string; and

a substitute sub-phrase assembly module to form a plurality of candidate substitute input data strings, each candidate substitute input data string comprising a unique combination of the input data string and at least one of the plurality of substitute sub-phrases.

24. The system of claim 19, wherein the semantic processing module further comprises a text string expansion module in communication with the content score generator to generate the subsequent text string and the preceding text string for the corrected input text string.