Method and system for cost computation of spelling suggestions and automatic replacement

• US 6,131,102 A
• Filed: 06/15/1998
• Issued: 10/10/2000
• Est. Priority Date: 06/15/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Potter, Douglas W.
• Primary Examiner(s): Hong, Stephen S.
• Application Number:
  US09/094,955
• Time in Patent Office: 848 Days
• Field of Search: 707/532, 707/533, 707/501, 400/63
• US Class Current: 715/257
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

Suggestions may be ordered by their associated costs so that the best suggestions may be displayed to the user and so that, in certain instances, a misspelled word entered by the user may be automatically replaced with a suggestion. To begin generating suggestions and costs, the user input and dictionary word (path of a trie) are considered in parallel. State variables are maintained such as the current cost of the dictionary word and the number of letter positions that have gone unmatched up to the current pointer position, also referred to as the offset. If the offset is zero and the next letters match, the cost associated with the dictionary word is maintained equal to zero. However, if the offset is zero and the next letters of the user input and the dictionary word do not match, then a cost for the dictionary word may not yet be determined. Otherwise, if the offset is greater than zero, possible paths in the trie and associated costs for the paths are determined. If a cost or multiple costs are determined, then the cost(s) is applied to the dictionary word, the offset is set to zero, and the matching process continues. If a cost can not be determined, then the offset is incremented by one and the matching process continues. Dictionary words (paths) are eliminated from consideration when their associated costs become too high. At the end of the matching method, the dictionary word (path) with the lowest cost is typically the best suggestion to replace the misspelled word.

Claims

1. For an electronic system for spell-checking an electronic document, a method for generating a numerical cost in association with a suggested word for replacing a misspelled word, the method comprising the steps of:

comparing the suggested word to the misspelled word to determine the transformation between the suggested word and the misspelled word and assigning a cost to that transformation, wherein the cost is based on determining whether the transformation is stored in a built-in string list; and

if so, retrieving a built-in string numerical cost from the built-in string list and if the transformation matches one of a plurality of generic transformation types comprising a generic numerical cost stored in association with the matching generic transformation type, then retrieving the generic numerical cost.

2. The method recited in claim 1, wherein the plurality of generic transformation types comprises a substitution, a deletion, an insertion, and a transposition.

3. The method recited in claim 2, further comprising the step of:

if the transformation does not match one of a plurality of generic transformation types, then storing an indication that a numerical cost could not be determined in association with the suggested word.

4. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 3.

5. For an electronic system for creating and editing an electronic document, a method for generating a numerical cost in association with suggested words for replacing a misspelled word, the method comprising the steps of:

(a) determining whether an offset value is equal to zero, wherein the offset value is equal to the number of previous letters in one of the suggested words that have not matched the misspelled word;

(b) if the offset value is not equal to zero, then determining associated numerical costs for possible paths of a trie and applying these associated numerical costs to their corresponding paths; and

(c) adding end costs, beginning costs, and frequency costs to the paths, resulting in a total numerical cost for each path.

6. The method recited in claim 5, wherein each path corresponds to a suggested word for replacing the misspelled word.

7. The method recited in claim 5, where the total numerical cost computed for each path corresponding to each suggested word is transmitted to the main application for its use in response to a misspelled word.

8. For an electronic system for creating and editing an electronic document, a method for generating a numerical cost in association with suggested words for replacing a misspelled word, the method comprising the steps of:

(a) determining whether an offset value is equal to zero, wherein the offset value is equal to the number of previous letters in one of the suggested words that have not matched the misspelled word;

(b) if the offset value is not equal to zero, then determining associated numerical costs for possible paths of a trie and applying these associated numerical costs to their corresponding paths;

(c) adding end costs, beginning costs, and frequency costs to the paths, resulting in a total numerical cost for each path; and

,

(d) transmitting the total numerical cost for each path to the main application for its use in response to a misspelled word.