Method and system for generating spelling suggestions

• US 7,584,093 B2
• Filed: 04/25/2005
• Issued: 09/01/2009
• Est. Priority Date: 04/25/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Igarashi, Hisakazu, Hart, Edward C. Jr., Ramsey, William D., Schmid, Patricia M., Potter, Douglas W.
• Primary Examiner(s): Han; Qi
• Application Number:
  US11/113,612
• Publication Number:
  US 20060241944A1
• Time in Patent Office: 1,590 Days
• Field of Search: 704/9, 704/4, 704/10, 704/1
• US Class Current: 704/9
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms

Abstract

A computer implemented method of suggesting replacement words for words of a string. In the method, an input string of input words is received. The input words are then matched to subject words of a candidate table. Next, candidate replacement words and scores from the candidate table corresponding to the matched subject words are extracted. Each score is indicative of a probability that the input word should be replaced with the corresponding candidate replacement word. Finally, replacement of the input words with their corresponding candidate replacement words is selectively suggested based on the scores for the replacement words. Another aspect of the present invention is directed to a spell checking system that is configured to implement the method.

Claims

1. A method comprising:

providing a computer comprising a processor;

providing a tangible computer storage medium;

executing instructions stored in the computer storage medium using the processor;

receiving an input string comprising two or more input words;

suggesting a replacement word for one of the input words responsive to executing the instructions comprising;

obtaining candidate replacement words for one of the input words;

obtaining a candidate score for each candidate replacement word, each candidate score indicative of a probability that the input word should be replaced with the corresponding candidate replacement word;

generating a candidate replacement string for each candidate replacement word, each candidate replacement string comprising the candidate replacement word and the input words of the input string less the input word corresponding to the candidate replacement word;

producing probability scores for each of the candidate replacement strings based on statistical data;

calculating a final score for each of the candidate replacement words based on the candidate score for the candidate replacement word and the probability score for the candidate replacement string containing the candidate replacement word; and

suggesting replacement of the input word with one of the corresponding candidate replacement words based on the final scores of the candidate replacement words.

2. The method of claim 1, wherein obtaining candidate replacement words for one of the input words comprises:

matching the input word to subject words of a candidate table; and

obtaining one or more candidate replacement words from the candidate table corresponding to the matched subject word.

3. The method of claim 2, wherein the probability scores are based on a likelihood of the words of the candidate replacement string appearing together.

4. The method of claim 2, wherein the subject words and the corresponding candidate replacement words of the candidate table are each in the form of a lexicon identifier that identifies the words in a lexicon.

5. The method of claim 2, wherein the candidate replacement words of the candidate table include words having an edit distance from their corresponding subject words that meets a threshold.

6. The method of claim 2, wherein the candidate replacement words of the candidate table include words that have a similar meaning to their corresponding subject words.

7. The method of claim 2, wherein the candidate replacement words of the candidate table include words that have a phonetic match to their corresponding subject words.

8. The method of claim 2, wherein the candidate replacement words of the candidate table include words that are common corrections to their corresponding subject words.

9. A system comprising:

a computer including a processor;

a tangible computer-readable medium;

program modules comprising instructions executable by the processor to suggest replacement words for input words of an input string, the modules comprising;

a candidate generator including an output of one or more candidate replacement words and corresponding candidate scores for one of the input words that match a subject word of a candidate table, wherein each candidate score is indicative of a probability that the input word should be replaced with the corresponding candidate replacement word;

a contextual spelling engine receives the output of one or more candidate replacement words and produces a candidate replacement string for each candidate replacement word, each candidate replacement string comprising the candidate replacement word and the input words of the input string less the input word corresponding to the candidate replacement word; and

a language model having an output of probability scores for each of the candidate replacement strings, the probability scores based on statistical data;

wherein the contextual spelling engine calculates a final score for each of the candidate replacement words based on the candidate score for the candidate replacement word and the probability score for the candidate replacement string containing the candidate replacement word, and outputs one of the candidate replacement words based on the final scores.

10. The system of claim 9, including a candidate exclusion table including a list of candidate replacement words that are excluded from one of the output of the candidate generator and the output of the contextual spelling engine.

11. The system of claim 9, wherein the probability scores are based on a likelihood of the words of the candidate replacement string appearing together.

12. The system of claim 9, wherein the candidate replacement words of the candidate table include words having an edit distance from their corresponding subject words that meets a threshold.

13. The system of claim 9, wherein the candidate replacement words of the candidate table include words that have a similar meaning to their corresponding subject words.

14. The system of claim 9, wherein the candidate replacement words of the candidate table include words that have a phonetic match to their corresponding subject words.

15. The system of claim 9, wherein the candidate replacement words of the candidate table include words that are common corrections to their corresponding subject words.

16. A method comprising:

providing a computer comprising a processor;

providing a tangible computer storage medium;

executing instructions stored in the computer storage medium using the processor;

receiving an original input string of two or more input words, wherein at least one of the input words is misspelled;

suggesting a replacement word for one of the input words responsive to executing the instructions comprising;

correcting the misspelled input words of the original input string to thereby generate a corrected input string that contains only correctly spelled input words;

matching the input words of the corrected input string to subject words of a candidate table;

extracting candidate replacement words and corresponding candidate scores from the candidate table each corresponding to the matched subject words, wherein each candidate score is indicative of a probability that the input word of the corrected input string should be replaced with the corresponding candidate replacement word;

generating a candidate replacement string for each candidate replacement word, each candidate replacement string comprising the candidate replacement word and the input words of the corrected input string less the input word corresponding to the candidate replacement word;

producing probability scores for each of the candidate replacement strings based on statistical data;

calculating a final score for each of the candidate replacement words based on the candidate score for the candidate replacement word and the probability score for the candidate replacement string containing the candidate replacement word; and

selectively suggesting replacement of the input words of the corrected input string with their corresponding candidate replacement words based on the final scores for the candidate replacement words.

17. The method of claim 16, wherein the candidate replacement words of the candidate table include words having an edit distance from their corresponding subject words that meets a threshold.

18. The method of claim 16, wherein the candidate replacement words of the candidate table include words that have a similar meaning to their corresponding subject words.

19. The method of claim 16, wherein the candidate replacement words of the candidate table include words that have a phonetic match to their corresponding subject words.

20. The method of claim 16, wherein the candidate replacement words of the candidate table include words that are common corrections to their corresponding subject words.

21. The method of claim 16, wherein the probability scores are based on a likelihood of the words of the candidate replacement string appearing together.