Data processing: database and file management or data structures – Database design – Data structure types
Patent
1998-06-15
2000-10-10
Hong, Stephen S.
Data processing: database and file management or data structures
Database design
Data structure types
707532, G06F 1721
Patent
active
061311022
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.
REFERENCES:
patent: 4913566 (1990-04-01), Sakai et al.
patent: 4915546 (1990-04-01), Kobayshi et al.
patent: 5258909 (1993-11-01), Damerau et al.
patent: 5261112 (1993-11-01), Futatsugi et al.
patent: 5802205 (1998-09-01), Emico et al.
patent: 5845306 (1998-12-01), Schabes et al.
Spelling mistakes: how well do correctors perform?; D. G. Hendry and T. R. G. Green; INTERACT '93 and CHI '93 conference companion on Human factors in computing systems, 1993, pp. 83-84.
Small domains spell fast strictness analysis; R. C. Sekar, Shaunak Pawagi and I. V. Ramarkrishnan; Proceedings of the seventeeth annual ACM symposium on Principles of programming languages , 1990, pp. 169-183.
Hong Stephen S.
Microsoft Corporation
LandOfFree
Method and system for cost computation of spelling suggestions a does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for cost computation of spelling suggestions a, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for cost computation of spelling suggestions a will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2263436