US6131102A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for cost computation of spelling suggestions and automatic replacement
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1998-06-15
•
Granted: 2000-10-10
•
Expires: 2018-06-15
Abstract
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.
Inventors
- 👤 Douglas W. Potter
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 03:15
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/232
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
124 words
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.
Claim 2
Dependent Claim
124 words
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.
Claim 3
Dependent Claim
23 words
The method recited in claim 1, wherein the plurality of generic transformation types comprises a substitution, a deletion, an insertion, and a transposition.
Claim 4
Dependent Claim
43 words
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.
Claim 5
Dependent Claim
14 words
A computer-readable medium having computer-executable instructions for performing the steps recited in claim 3.
Claim 6
Dependent Claim
122 words
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.
Claim 7
Dependent Claim
122 words
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.
Claim 8
Dependent Claim
19 words
The method recited in claim 5, wherein each path corresponds to a suggested word for replacing the misspelled word.
Claim 9
Dependent Claim
35 words
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.
Claim 10
Dependent Claim
144 words
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.
Claim 11
Dependent Claim
144 words
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.
References Cited (Backward Citations)
US4915546A
Cited
US4913566A
Cited
US5258909A
Cited
US5261112A
Cited
US5845306A
Cited
US5802205A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-10-10 | 2004-04-10 | 2004-10-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-10-10 | 2008-04-10 | 2008-10-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-10-10 | 2012-04-10 | 2012-10-10 | $7700.00 | Window Closed / Lapsed |