Patent EP0415000A2 successfully refreshed from Google Patents.
EP0415000A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method and apparatus for spelling error detection and correction
Assignee: International Business Machines Corp
•
Filing: 1990-05-07
•
Granted: —
•
Expires: 2010-05-07
Abstract
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.
Inventors
- 👤 Frederick J. Damerau
- 👤 Eric K. Mays
- 👤 Robert L. Mercer
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-09 19:54
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/232
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
186 words
A method of detecting an error in an information signal, said method comprising the steps of: providing an input string of information signals W i , each information signal representing information; changing a first information signal W₁ in the input string to form a second information signal W₂ representing information different from the information represented by the first information signal, 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(W i |W c ) of misrepresenting the information represented by the candidate string of information signals W c as the input string of information signals W i ; comparing P(W i ) with the product P(W c )P(W i |W c ) ; and outputting a first output signal if P(W₁) is greater than P(W c )P(W i |W c ), or outputting a second output signal if P(W i ) is less than P(W c )P(W i |W c ),
Claim 2
Independent Claim
186 words
A method of detecting an error in an information signal, said method comprising the steps of: providing an input string of information signals W i , each information signal representing information; changing a first information signal W₁ in the input string to form a second information signal W₂ representing information different from the information represented by the first information signal, 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(W i |W c ) of misrepresenting the information represented by the candidate string of information signals W c as the input string of information signals W i ; comparing P(W i ) with the product P(W c )P(W i |W c ) ; and outputting a first output signal if P(W₁) is greater than P(W c )P(W i |W c ), or outputting a second output signal if P(W i ) is less than P(W c )P(W i |W c ),
Claim 3
Dependent Claim
63 words
A method as claimed in Claim 1, characterized in that: the first output signal comprises the input string of information signals; the second output signal comprises the candidate string of information signals; and the probability P(W i |W c ) is estimated as the probability P(W₁|W₂) of misrepresenting the information represented by the second information signal W₂ as the first information signal W₁.
Claim 4
Dependent Claim
87 words
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 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.
Claim 5
Independent Claim
125 words
A method as claimed in Claim. 3, characterized in that: the method further comprises the step of estimating the probability P(W 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(W i |W i ) with the product P(W c )P(W i |W c ) and the step of outputting comprises outputting the first output signal if P(W i )P(W i |W i ) is greater than P(W c )P(W i |W c ), or outputting the second output signal if P(W i )P(W i |W i ) is less than P(W c )P(W i |W c ).
Claim 6
Dependent Claim
35 words
A method as claimed in Claim 4, characterized in that: the probability P(W i |W i ) is estimated as the probability P(W₁|W₁) of correctly representing the information represented by the first information signal W₁.
Claim 7
Dependent Claim
79 words
A method as claimed in Claim 5, 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.
Claim 8
Dependent Claim
79 words
A method as claimed in Claim 5, 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.
Claim 9
Dependent Claim
94 words
A method as claimed in Claim 5, 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.
Claim 10
Dependent Claim
92 words
A method as claimed in Claim 5, 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.
Claim 11
Dependent Claim
83 words
A method as claimed in Claim 5, 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₂.
Claim 12
Dependent Claim
71 words
A method as claimed in Claim 5, 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₂.
Claim 13
Dependent Claim
30 words
A method as claimed in Claim 11, characterized in that: the probability P(W₁|W₁) is estimated to be 0.999; and the probability P(W i |W c ) is estimated to be
Claim 14
Dependent Claim
19 words
A method as claimed in Claim 1, characterized in that the second output signal comprises an error indication signal.
Claim 15
Independent Claim
199 words
An apparatus for detecting an error in an information signal, said apparatus comprising: means for providing an input string of information signals W i , each information signal representing information; means for changing a first information signal W₁ in the input string to form a second information signal W₂ representing information different from the information represented by the first information signal, 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(W i |W c ) of misrepresenting the information represented by the candidate string of information signals W c as the input string of information signals W i ; means for comparing P(W i ) with the product P(W c )P(W i |W c ) ; and means for outputting a first output signal if P(W i ) is greater than P(W c )P(W i |W c ), or outputting a second output signal if P(W i ) is less than P(W c )P(W i |W c ).
Claim 16
Independent Claim
199 words
An apparatus for detecting an error in an information signal, said apparatus comprising: means for providing an input string of information signals W i , each information signal representing information; means for changing a first information signal W₁ in the input string to form a second information signal W₂ representing information different from the information represented by the first information signal, 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(W i |W c ) of misrepresenting the information represented by the candidate string of information signals W c as the input string of information signals W i ; means for comparing P(W i ) with the product P(W c )P(W i |W c ) ; and means for outputting a first output signal if P(W i ) is greater than P(W c )P(W i |W c ), or outputting a second output signal if P(W i ) is less than P(W c )P(W i |W c ).
Claim 17
Dependent Claim
63 words
An apparatus as claimed in Claim 14, characterized in that: the first output signal comprises the input string of information signals; the second output signal comprises the candidate string of information signals; and the probability P(W i |W c ) is estimated as the probability P(W₁|W₂) of misrepresenting the information represented by the second information signal W₂ as the first information signal W₁.
Claim 18
Dependent Claim
87 words
An apparatus as claimed in Claim 15, 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.
Claim 19
Dependent Claim
125 words
An apparatus as claimed in Claim 16, characterized in that: the apparatus further comprises means for estimating the probability P(W 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(W i |W i ) with the product P(W c )P(W i |W c ) ; and the means for outputting comprises means for outputting the first output signal if P(W i )P(W i |W i ) is greater than P(W c )P(W i |W c ), or outputting the second output signal if P(W i )P(W i |W i ) is less than P(W c )P(W i |W c )
Claim 20
Dependent Claim
35 words
An apparatus as claimed in Claim 17, characterized in that: the probability P(W i |W i ) is estimated as the probability P(W₁|W₁) of correctly representing the information represented by the first information signal W₁.
Claim 21
Dependent Claim
85 words
An apparatus as claimed in Claim 18, 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.
Claim 22
Dependent Claim
85 words
An apparatus as claimed in Claim 18, 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.
Claim 23
Dependent Claim
100 words
An apparatus as claimed in Claim 18, 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 transposing 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.
Claim 24
Dependent Claim
98 words
An apparatus as claimed in Claim 18, 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.
Claim 25
Dependent Claim
87 words
An apparatus as claimed in Claim 18, 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₂.
Claim 26
Dependent Claim
75 words
An apparatus as claimed in Claim 18, 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₂.
Claim 27
Dependent Claim
28 words
An apparatus as claimed in Claim 24, characterized in that: the probability P(W₁|W₁) is estimated 0.999; and the probability P(W i |W c ) is estimated to be
Claim 28
Dependent Claim
19 words
An apparatus as claimed in Claim 14, characterized in that the second output signal comprises an error indication signal.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.