Image analysis – Pattern recognition – Context analysis or word recognition
Patent
1995-06-07
1998-06-30
Johns, Andrew
Image analysis
Pattern recognition
Context analysis or word recognition
382229, G06K 936, G06K 972
Patent
active
057745889
ABSTRACT:
A system and method for more efficiently comparing an unverified string to a lexicon, which filters the lexicon through multiple steps to reduce the number of entries to be directly compared with the unverified string. The method begins by preparing the lexicon with an n-gram encoding, partitioning and hashing process, which can be accomplished in advance of any processing of unverified strings. The unknown is compared first by partitioning and hashing it in the same way to reduce the lexicon in a computationally inexpensive manner. This is followed by an encoded vector comparison step, and finally by a direct string comparison step, which is the most computationally expensive. The reduction of the lexicon is accomplished without arbitrarily eliminating any large portions of the lexicon that might contain relevant candidates. At the same time, the method avoids the need to compare the unverified string directly or indirectly with all the entries in the lexicon. The final candidate list includes only highly possible and ranked candidates for the unverified string, and the size of the final list is adjustable.
REFERENCES:
patent: 3969698 (1976-07-01), Bollinger et al.
patent: 3995254 (1976-11-01), Rosenbaum
patent: 4010445 (1977-03-01), Hoshino
patent: 4058795 (1977-11-01), Balm
patent: 4754489 (1988-06-01), Bokser
patent: 4771385 (1988-09-01), Egami et al.
patent: 4799271 (1989-01-01), Nagasawa et al.
patent: 4903206 (1990-02-01), Itoh et al.
patent: 4979227 (1990-12-01), Mittelbach et al.
patent: 5050218 (1991-09-01), Ikeda et al.
patent: 5062143 (1991-10-01), Schmitt
patent: 5133023 (1992-07-01), Bokser
patent: 5136289 (1992-08-01), Yoshida et al.
patent: 5261009 (1993-11-01), Bokser
patent: 5276741 (1994-01-01), Aragon
patent: 5325444 (1994-06-01), Cass et al.
patent: 5329609 (1994-07-01), Sanada et al.
William B. Cavnar and Alan J. Vayda, Using Superimposing Coding of N-gram Lists for Efficient Inexact Matching, Environmental Research Institute of Michigan, pp. 253-267, 480-493.
Owolabi et al., "Fast Approximate String Matching," Software--Practice and Experience, vol. 18, No. 4, pp. 387-393 (Apr. 1988).
Takahashi et al., "A Spelling Correction Method and Its Application to an OCR System," Pattern Recignition, vol. 23, No. 3/4, pp. 363-377 (Jan. 1990).
Zobel et al., "Finding Approximate Matches in Large Lexicons," Software--Practice and Experience, vol. 25, No. 3, pp. 331-345 (Mar. 1995).
William J. Masek and Michael S. Paterson, "A Faster Algorithm Computing String Edit Distances," of Journal Computer And System Sciences, 20, 18-13 (1980), pp. 18-31.
Roy Lowrance and Robert A. Wagner, "An Extension of the String-to-String Correction Problem," Journal of the Association for Computing Machinery, vol. 22, No. 2, Apr. 1975 pp. 177-183.
Robert A. Wagner and Michael J. Fischer, "The String-to-String Correction Problem," Journal of Association for Computing Machinery, vol. 21, No. 1, Jan. 1974, pp. 168-173.
Sun Wu and Udi Manber, "AGREP--A Fast Approximate Pattern-Matching Tool," Dept. of Computer Science University of Arizona.
Edward M. Riseman, "A Contexual Postprocessing System For Error Correction Using Binary N-Grams" IEE Transactions On Computers, vol. C-23, No. 5, May 1974, pp. 480, 481-493.
Davis Monica S.
Johns Andrew
United Parcel Service of America Inc.
LandOfFree
Method and system for comparing strings with entries of a lexico 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 comparing strings with entries of a lexico, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for comparing strings with entries of a lexico will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1868803