Method for correcting spelling using error frequencies

• US 5,572,423 A
• Filed: 01/23/1995
• Issued: 11/05/1996
• Est. Priority Date: 06/14/1990
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Church, Kenneth W.
• Primary Examiner(s): Harvey, Jack B.
• Assistant Examiner(s): CHUNG TRANS, XUONG MY
• Application Number:
  US08/376,693
• Time in Patent Office: 652 Days
• Field of Search: 364/419.12, 364/419.11, 364/419.14
• US Class Current: 715/257
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

An improved method for correcting spelling errors in text wherein candidate expressions for replacing a misspelled word are assigned probability functions. The misspelled word can be replaced automatically with the candidate expression having the highest probability function or candidate expressions can be displayed to a user in rank order of their probability functions for the user to make a choice. The probability function for a candidate expression is based on (1) the probability of occurrence of the candidate expression appearing in text and/or (2) the probability of occurrence of the particular typographical modification needed to convert the candidate expression into the misspelled word.

Claims

1. In an automatic machine, a method of correcting incorrectly-spelled words in an object text stored in a memory wherein an incorrectly-spelled word is identified and a plurality of correctly-spelled candidate expressions is generated to replace said incorrectly-spelled word, which comprises:

determining a probability function for each candidate expression, said probability function being based on both (1) a first stored probability of occurrence of said candidate expression in text independent of context and (2) a second stored probability of occurrence of the particular typographical modification that, when applied to said candidate expression, results in said incorrectly-spelled word, said first stored probability being computed from the number of occurrences of said candidate word in a large body of text in relation to the total number of words in said large body of text, said second probability being computed from the number of occurrences of said particular typographical modification in a training text containing known incorrectly-spelled words in relation to the total number of occurrences in said training text of the character or combination of characters modified by said particular typographical modification, and

replacing said incorrectly-spelled word in said stored object text with the candidate expression having the highest probability function.

2. In an automatic machine, a method of suggesting corrections for incorrectly-spelled words in an object text stored in a memory wherein ann incorrectly-spelled word is identified and a plurality of correctly-spelled candidate expressions is generated to replace said incorrectly-spelled word, which comprises:

determining a probability function for each candidate expression, said probability function being based on both (1) a first stored probability of occurrence of said candidate expression in text independent of context and (2) a second stored probability of occurrence of the particular typographical modification that, when applied to said candidate expression, results in said incorrectly-spelled word, said first stored probability being computed from the number of occurrences of said candidate word in a large body of text in relation to the total number of words in said large body of text, said second probability being computed from the number of occurrences of said particular typographical modification in a training text containing known incorrectly-spelled words in relation to the total number of occurrences in said training text of the character or combination of characters modified by said particular typographical modification, and

displaying said candidate expressions in descending rank order of their probability functions.

3. A method of using a computer to correct misspelled words in an object text, comprising the steps of:

storing, in memory means accessible to said computer, said object text, a dictionary of acceptable words and a table containing probabilities of occurrence of said acceptable words, the probability for each acceptable word being computed from the number of occurrences of said acceptable word in a large body of text in relation to the total number of words in said large body of text,

comparing each word of said object text with said acceptable words and identifying as misspelled each word of said text for which a match cannot be found,

for each misspelled word, generating a plurality of candidate words to replace said misspelled word by adding, deleting, substituting and transposing characters in said misspelled word and verifying that each candidate word appears in said dictionary,

retrieving from said table the probability of occurrence of each candidate word and

replacing said misspelled word in said stored object text with the candidate word associated with the highest probability of occurrence.

4. A method of using a computer to correct misspelled words in an object text, comprising the steps of:

storing, in memory means accessible to said computer, said object text, a dictionary of acceptable words, a first table containing probabilities of occurrence of said acceptable words and a second table containing probabilities of occurrence of particular typographical errors, the probability in said first table for each acceptable word being computed from the number of occurrences of said acceptable word in a large body of text in relation to the total number of words in said large body of text, the probability in said second table for each particular typographical error being computed from the number of occurrences of said particular typographical error in a training text containing known typographical errors in relation to the total number of occurrences in said training text of the character or combination of characters involved in said typographical error,

comparing each word of said object text with said acceptable words and identifying as misspelled each word of said text for which a match cannot be found,

for each said misspelled word, generating a plurality of candidate words to replace said misspelled word by adding, deleting, substituting and transposing characters in said misspelled word and verifying that each candidate word appears in said dictionary,

for each candidate word, retrieving from said first table the probability of occurrence of said candidate word and from said second table the probability of occurrence of the particular typographical error that, when applied to said candidate word, results in said misspelled word,

for each candidate word, calculating a probability function based on said retrieved probabilities, and

replacing said misspelled word in said stored object text with the candidate word having the highest probability function.

5. A method of using a programmed computer to correct incorrectly spelled words in an object text, comprising the steps of:

storing, in memory means accessible to said computer, said object text, a dictionary of acceptable words, a first table containing probabilities of occurrence of said acceptable words independent of context and a second table containing probabilities of occurrence of particular typographical errors, the probability in said first table for each acceptable word being computed from the number of occurrences of said acceptable word in a large body of text in relation to the total number of words in said large body of text, the probability in said second table for each particular typographical error being computed from the number of occurrences of said particular typographical error in a training text containing known typographical errors in relation to the total number of occurrences in said training text of the character or combination of characters involved in said particular typographical error,

comparing each word of said object text with said acceptable words and identifying as an incorrectly spelled word each word of said text for which a match cannot be found,

for each said incorrectly spelled word, creating a plurality of correctly-spelled candidate words to replace said incorrectly spelled word by adding, deleting, substituting and transposing characters in said incorrectly spelled word and verifying that each candidate word appears in said dictionary,

for each candidate word, retrieving both (1) the probability from said first table associated with said candidate expression and (2) the probability from said second table associated with the particular typographical error that, when applied to said candidate word, results in said incorrectly spelled word,

for each candidate word, calculating a probability function based on said retrieved probabilities, and

replacing said incorrectly spelled word in said stored object text with the candidate word having the highest probability function.

6. A method of using a programmed computer to suggest candidate words as replacements for incorrectly-spelled words in an object text, comprising the steps of:

storing, in memory means accessible to said computer, said object text, a dictionary of acceptable words a first table containing probabilities of occurrence of said acceptable words independent of context and a second table containing probabilities of occurrence of particular typographical errors, the probability in said first table for each acceptable word being computed from the number of occurrences of said acceptable word in a large body of text in relation to the total number of words in said large body of text, the probability in said second table for each particular typographical error being computed from the number of occurrences of said particular typographical error in a training text containing known typographical errors in relation to the total number of occurrences in said training text of the character or combination of characters involved in said particular typographical error,

comparing each word of said object text with said acceptable words and identifying as an incorrectly-spelled word each word of said text for which a match cannot be found,

for each incorrectly-spelled word, creating a plurality of correctly-spelled candidate words to replace said incorrectly-spelled word by adding, deleting, substituting and transposing the characters in said incorrectly-spelled word and verifying that each candidate word appears in said dictionary,

for each candidate word, retrieving both (1) the probability from said first table associated with said candidate expression and (2) the probability from said second table associated with the particular typographical error that, when applied to said candidate word, results in said incorrectly-spelled word,

for each candidate word, calculating a probability function based on said retrieved probabilities, and

displaying said candidate expressions in descending rank order of their associated probability functions.