Data processing: presentation processing of document – operator i – Presentation processing of document – Layout
Reexamination Certificate
2000-09-20
2003-09-09
Hong, Stephen S. (Department: 2178)
Data processing: presentation processing of document, operator i
Presentation processing of document
Layout
C707S793000, C707S793000
Reexamination Certificate
active
06616704
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to a very fast method for correcting the spelling of a word or phrase in a document. The method has application to any technique which searches documents.
2. Background Description
Suppose that we are given a word, G, and we wish to find one or more other words from a list of candidate words that are within a given edit distance from G. Here, the edit distance between two words is the smallest number of operations which transform the candidate word into the given word (each operation consisting of removing one letter, adding one letter, replacing one letter with another letter, or transposing two letters).
In “The String-to-String Correction Problem”, JACM, 21(1), pp. 168-173 (1974), R. A. Wagner and M. J. Fischer showed that the edit distance between two words G and C could be computed in time proportional to the length of G times the length of C. Subsequently, in “Algorithms for Approximate String Matching”, Information and Control, 64, pp. 100-118 (1985), E. Ukkonen improved the running time of the algorithm. This latter result is called the “slow method” in the following description.
SUMMARY OF THE INVENTION
According to the invention, there is provided a method which proceeds in two steps: first applying a very fast method (comparing G to each candidate word) for eliminating most candidate words from consideration (without computing the exact edit distance between G and any candidate word), followed by the “slow method” which computes the exact edit distance between G and each of the few remaining candidate words. The second step is the slow exact method well-known in the art as described by Ukkonen.
The invention consists of (1) a new fast approximate method and (2) combining this fast approximate method with the slow method. The combination results in a method that is almost as fast as the fast approximate method and as exact as the slow method.
REFERENCES:
patent: 5218536 (1993-06-01), McWherter
patent: 5465309 (1995-11-01), Johnson
patent: 5572423 (1996-11-01), Church
patent: 5845306 (1998-12-01), Schabes et al.
patent: 5901255 (1999-05-01), Yagasaki
patent: 6041323 (2000-03-01), Kubota
Veronis, “Correction of phonographic errors in natural language interfaces”, ACM, 1988, pp. 101-115.*
Peterson, “Computer programs for detecting and correcting spelling errors”, Communications of the ACM, vol. 23, No. 12, Dec. 1980, pp. 676-687.*
Turba, “Checking for spelling and typographical errors in computer-based text”, Proceedings of the ACM SIGPLAN SIGOA symposium on Text manipulation, Jun. 1981, pp. 51-60.*
R. Wagner et al., “The String-to-String Correction Problem”, Journal of the Association for Computing Machinery, vol. 21, No. 1, Jan. 1974, pp. 168-173.
E. Ukkonen, “Algorithms for Approximate String Matching”, Information and Control, 64, pp. 100-118 (1985).
Birman Alexander
Gail, Jr. Harry R.
Hantler Sidney L.
Leeman, Jr. George B.
Milch Daniel
Hong Stephen S.
Kaufman Stephen C.
Whitham Curtis & Christofferson, P.C.
LandOfFree
Two step method for correcting spelling of a word or phrase... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Two step method for correcting spelling of a word or phrase..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two step method for correcting spelling of a word or phrase... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3018046