Method and apparatus for "wrong word" spelling error detection and correction

• US 5,258,909 A
• Filed: 08/31/1989
• Issued: 11/02/1993
• Est. Priority Date: 08/31/1989
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mays, Eric K., Damerau, Frederick J., Mercer, Robert L.
• Primary Examiner(s): Hayes, Gail O.
• Application Number:
  US07/401,584
• Time in Patent Office: 1,524 Days
• Field of Search: 364/419
• US Class Current: 715/257
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

A method of detecting and correcting an error in a string of information signals. When each information signal represents a word, the method detects and corrects spelling errors. The method detects and corrects an error which is a properly spelled word, but which is the wrong (not intended) word. For example, the method is capable of detecting and correcting a misspelling of "HORSE" as "HOUSE". In the spelling error detection and correction method, a first word in an input string of words is changed to form a second word different from a first word to form a candidate string of words. The spellings of the first word and the second word are in the spelling dictionary. The probability of occurrence of the input string of words is compared to the product of the probability of occurrence of the candidate string of words multiplied by the probability of misrepresenting the candidate string of words as the input string of words. If the former is greater than or equal to the latter, no correction is made. If the former is less than the latter, the candidate string of words is selected as a spelling correction.

Claims

1. A spelling error detection method, said method comprising the steps of:

providing an input string of words T_i =W_i produced by a word processor, each word having a spelling;

changing the spelling of a first word T₁ =W₁ in the input string to form a second word W₂ different from the first word;

replacing the first word W₁ in the input string W_i with the second word W₂ to form a candidate string of words W_c ;

estimating the probability P(W_i) of occurrence of the input string of words;

estimating the probability P(W_c) of occurrence of the candidate string of words;

estimating the probability P(T_i |W_c) of misrepresenting the candidate string of words W_c as the input string of words T_i ;

comparing P(W_i) with the product P(W_c)P(T_i |W_c); and

outputting the input string of words if P(W_i) is greater than P(W_c)P(T_i |W_c), or outputting an error indication if P(W_i) is less than P(W_c)P(T_i |W_c).

2. A method as claimed in claim 1, characterized in that:

the second output comprises the candidate string of words; and

the probability P(T_i |W_c) is estimated as the probability P(T₁ |W₂) of misspelling the second word W₂ as the first word T₁.

3. A method as claimed in claim 2, characterized in that:

the method further comprises the step of providing a set of words, each word having a spelling;

each word in the input string of words is a member of the set of words; and

the second word W₂ is a member of the set of words.

4. A method as claimed in claim 3, characterized in that:

the method further comprises the step of estimating the probability P(T_i |W_i) of correctly spelling all of the words in the input string of words W_i ;

the step of comparing comprises comparing the product P(W_i)P(T_i |W_i) with the product; and

the step of outputting comprises outputting the first output if P(W_i)P(T_i |W_i) is greater than, or outputting the second output if P(W_i)P(T_i |W_i) is less than P(W_c)P(T_i |W_c).

5. A method as claimed in claim 4, characterized in that the probability P(T_i |W_i) is estimated as the probability P(T₁ |W₁) of correctly spelling the first word T₁.

6. A method as claimed in claim 5, characterized in that the step of changing the spelling of the first word W₁ to form the second word W₂ comprises:

adding a letter to the first word to form a tentative word;

comparing the tentative word to each word in the set of words; and

using the tentative word as the second word W₂ if the tentative word matches a word in the set of words.

7. A method as claimed in claim 5, characterized in that the step of changing the spelling of the first word W₁ to form the second word W₂ comprises:

deleting a letter from the first word to form a tentative word;

comparing the tentative word to each word in the set of words; and

using the tentative word as the second word W₂ if the tentative word matches a word in the set of words.

8. A method as claimed in claim 5, characterized in that:

the first word comprises at least two letters; and

the step of changing the spelling of the first word W₁ to form the second word W₂ comprises;

transposing at least two letters in the first word to form a tentative word;

comparing the tentative word to each word in the set of words; and

using the tentative word as the second word W₂ if the tentative word matches a word in the set of words.

9. A method as claimed in claim 5, characterized in that:

the first word comprises at least one letter; and

the step of changing the spelling of the first word W₁ to form the second word W₂ comprises;

replacing a letter in the first word with a different letter to form a tentative word;

comparing the tentative word to each word in the set of words; and

using the tentative word as the second word W₂ if the tentative word matches a word in the set of words.

10. A method as claimed in claim 5, characterized in that the step of changing the spelling of the first word W₁ to form the second word W₂ comprises:

identifying a confusion group of M different words in the set of words, each word in the confusion group having a spelling which differs from the spelling of the first word by no more than two letters; and

selecting one word in the confusion group as the second word W₂.

11. A method as claimed in claim 5, characterized in that the step of changing the spelling of the first word W₁ to form the second word W₂ comprises:

identifying a confusion group of M different words in the set of words, each word in the confusion group being confusable with the first word; and

selecting one word in the confusion group as the second word W₂.

12. A method as claimed in claim 11, characterized in that:

the probability P(T₁ |W₁) is estimated to be 0.999; and

the probability P(T_i |W_c) is estimated to be (0.001/M).

13. A method of detecting an error in an information signal, said method comprising the steps of:

providing an input string of information signals T_i =W_i, each information signal representing information;

changing a first information signal T₁ =W₁ in the input string to form a second information signal W₂ representing information different from the information represented by the first information signal;

replacing the first information signal W₁ in the input string W_i with the second information signal W₂ to form a candidate string of information signals W_c ;

estimating the probability P(W_i) of occurrence of the input string of information signals;

estimating the probability P(W_c) of occurrence of the candidate string of information signals;

estimating the probability P(T_i |W_c) of misrepresenting the information represented by the candidate string of information signals W_c as the input string of information signals T_i ;

comparing P(W_i) with the product P(W_c)P(T_i |W_c); and

outputting the input string of information signals if P(W_i) is greater than P(W_c)P(T_i |W_c), or outputting an error indication signal if P(W_i) is less than P(W_c)P(T_i |W_c).

14. A method as claimed in claim 13, characterized in that:

the second output signal comprises the candidate string of information signals; and

the probability P(T_i |W_c) is estimated as the probability P(T₁ |W₂) of misrepresenting the information represented by the second information signal W₂ as the first information signal T₁.

15. A method as claimed in claim 14, characterized in that:

the method further comprises the step of providing a set of words, each word having a spelling;

each information signal in the input string of information signals represents a word which is a member of the set of words; and

the second information signal W₂ represents a word which is a member of the set of words, the word represented by the second information signal being different from the word being represented by the first information signal.

16. A method as claimed in claim 15, characterized in that:

the method further comprises the step of estimating the probability P(T_i |W_i) of correctly representing the information represented by all of the information signals in the input string of information signals W_i ;

the step of comparing comprises comparing the product P(W_i)P(T_i |W_i) with the product P(W_c)P(T_i |W_c); and

the step of outputting comprises outputting the first output signal if P(W_i)P(T_i |W_i) is greater than P(W_c)P(T_i |W_c), or outputting the second output signal if P(W_i)P(T_i |W_i) is less than P(W_c)P(T_i |W_c).

17. A method as claimed in claim 16, characterized in that:

the probability P(T_i |W_i) is estimated as the probability P(T₁ |W₁) of correctly representing the information represented by the first information signal T₁.

18. A method as claimed in claim 17, characterized in that the step of changing the first information signal W₁ to form the second information signal W₂ comprises:

adding a letter to the word represented by the first information signal to form a tentative word;

comparing the tentative word to each word in the set of words; and

representing the tentative word as the second information signal W₂ if the tentative word matches a word in the set of words.

19. A method as claimed in claim 17, characterized in that the step of changing the first information signal W₁ to form the second information signal W₂ comprises:

deleting a letter from the word represented by the first information signal to form a tentative word;

comparing the tentative word to each word in the set of words; and

representing the tentative word as the second information signal W₂ if the tentative word matches a word in the set of words.

20. A method as claimed in claim 17, characterized in that:

the first information signal represents a word having at least two letters; and

the step of changing the first information signal W₁ to form the second information signal W₂ comprises;

transposing at least two letters in the word represented by the first information signal to form a tentative word;

comparing the tentative word to each word in the set of words; and

representing the tentative word as the second information signal W₂ if the tentative word matches a word in the set of words.

21. A method as claimed in claim 17, characterized in that:

the first information signal represents a word having at least one letter; and

the step of changing the first information signal W₁ to form the second information signal W₂ comprises;

replacing a letter in the word represented by the first information signal to form a tentative word;

comparing the tentative word to each word in the set of words; and

representing the tentative word as the second information signal W₂ if the tentative word matches a word in the set of words.

22. A method as claimed in claim 17, characterized in that the step of changing the first information signal W₁ to form the second information signal W₂ comprises:

identifying a confusion group of M different words in the set of words, each word in the confusion group having a spelling which differs from the spelling of the word represented by the first information signal by no more than two letters; and

representing one word in the confusion group as the second information signal W₂.

23. A method as claimed in claim 17, characterized in that the step of changing the first information signal W₁ to form the second information signal W₂ comprises:

identifying a confusion group of M different words in the set of words, each word in the confusion group being confusable with the word represented by the first information signal; and

representing one word in the confusion group as the second information signal W₂.

24. A method as claimed in claim 23, characterized in that:

the probability P(T₁ |W₁) is estimated to be 0.999; and

the probability P(T_i |W_c) is estimated to be (0.001/M).

25. An apparatus for detecting an error in an information signal, said apparatus comprising:

means for providing an input string of information signals T_i =W_i, each information signal representing information;

means for changing a first information signal T₁ =W₁ in the input string to form a second information signal W₂ representing information different from the information represented by the first information signal;

means for replacing the first information signal W₁ in the input string with the second information signal W₂ to form a candidate string of information signals W_c ;

means for estimating the probability P(W_i) of occurrence of the input string of information signals;

means for estimating the probability P(W_c) of occurrence of the candidate string of information signals;

means for estimating the probability P(T_i |W_c) of misrepresenting the information represented by the candidate string of information signals W_c as the input string of information signals T_i ;

means for comparing P(W_i) with the product P(W_c)P(T_i |W_c); and

means for outputting the input string of information signals if P(W_i) is greater than P(W_c)P(T_i |W_c), or outputting an error indication signal if P(W_i) is less than P(W_c)P(T_i |W_c).

26. An apparatus as claimed in claim 25, characterized in that:

the second output signal comprises the candidate string of information signals; and

the probability P(T_i |W_c) is estimated as the probability P(T₁ |W₂) of misrepresenting the information represented by the second information signal W₂ as the first information signal T₁.

27. An apparatus as claimed in claim 26, characterized in that:

the apparatus further comprises dictionary means for storing a set of words, each word having a spelling;

each information signal in the input string of information signals represents a word which is a member of the set of words; and

the second information signal W₂ represents a word which is a member of the set of words, the word represented by the second information signal being different from the word being represented by the first information signal.

28. An apparatus as claimed in claim 27, characterized in that:

the apparatus further comprises means for estimating the probability P(T_i |W_i) of correctly representing all of the information represented by the input string of information signals W_i ;

the means for comparing comprises means for comparing the product P(W_i)P(T_i |W_i) with the product P(W_c)P(T_i |W_c); and

the means for outputting comprises means for outputting the first output signal if P(W_i)P(T_i |W_i) is greater than P(W_c)P(T_i |W_c), or outputting the second output signal if P(W_i)P(T_i |W_i) is less than P(W_c)P(T_i |W_c).

29. An apparatus as claimed in claim 28, characterized in that:

the probability P(T_i |W_i) is estimated as the probability P(T₁ |W₁) of correctly representing the information represented by the first information signal W₁.

30. An apparatus as claimed in claim 29, characterized in that the means for changing the first information signal W₁ to form the second information signal W₂ comprises:

means for adding a letter to the word represented by the first information signal to form a tentative word;

means for comparing the tentative word to each word in the set of words; and

means for representing the tentative word as the second information signal W₂ if the tentative word matches a word in the set of words.

31. An apparatus as claimed in claim 29, characterized in that the means for changing the first information signal W₁ to form the second information signal W₂ comprises:

means for deleting a letter from the word represented by the first information signal to form a tentative word;

means for comparing the tentative word to each word in the set of words; and

means for representing the tentative word as the second information signal W₂ if the tentative word matches a word in the set of words.

32. An apparatus as claimed in claim 27, characterized in that

the first information signal represents a word having at least two letters;

and

the means for changing the first information signal W₁ to form the second information signal W₂ comprises;

means for transporting at least two letters in the word represented by the first information signal to form a tentative word;

means for comparing the tentative word to each word in the set of words; and

means for representing the tentative word as the second information signal W₂ if the tentative word matches a word in the set of words.

33. An apparatus as claimed in claim 29, characterized in that:

the first information signal represents a word having at least one letter; and

the means for changing the first information signal W₁ to form the second information signal W₂ comprises;

means for replacing a letter in the word represented by the first information signal to form a tentative word;

means for comparing the tentative word to each word in the set of words; and

means for representing the tentative word as the second information signal W₂ if the tentative word matches a word in the set of words.

34. An apparatus as claimed in claim 29, characterized in that the means for changing the first information signal W₁ to form the second information signal W₂ comprises:

means for identifying a confusion group of M different words in the set of words, each word in the confusion group having a spelling which differs from the spelling of the word represented by the first information signal by no more than two letters; and

means for representing one word in the confusion group as the second information signal W₂.

35. An apparatus as claimed in claim 29, characterized in that the means for changing the first information signal W₁ to form the second information signal W₂ comprises:

means for identifying a confusion group of M different words in the set of words, each word in the confusion group being confusable with the word represented by the first information signal; and

means for representing one word in the confusion group as the second information signal W₂.

36. A method as claimed in claim 35, characterized in that:

the probability P(T₁ |W₁) is estimated to be 0.999; and

the probability P(T_i |W_c) is estimated to be (0.001/M).