DocumentCode
2629717
Title
A fast algorithm for finding the nearest neighbor of a word in a dictionary
Author
Bunke, Horst
Author_Institution
Inst. of Inf. & Appl. Math., Bern, Switzerland
fYear
1993
fDate
20-22 Oct 1993
Firstpage
632
Lastpage
637
Abstract
A new algorithm for string edit distance computation is proposed. It needs time that is only linear in the length of one of the two strings to be matched, provided that the other string has undergone some preprocessing in an off-line phase. The algorithm can be extended to matching a word against a dictionary of any size. In this case the time complexity is independent of the length of the dictionary words, and the number of entries in the dictionary
Keywords
computational complexity; glossaries; optical character recognition; pattern matching; string matching; dictionary; dictionary words; nearest neighbor; offline phase; preprocessing; string edit distance computation; string length; time complexity; word matching; Automata; Character recognition; Dictionaries; Dynamic programming; Informatics; Mathematics; Nearest neighbor searches; Optical character recognition software; Optical distortion; Statistics;
fLanguage
English
Publisher
ieee
Conference_Titel
Document Analysis and Recognition, 1993., Proceedings of the Second International Conference on
Conference_Location
Tsukuba Science City
Print_ISBN
0-8186-4960-7
Type
conf
DOI
10.1109/ICDAR.1993.395657
Filename
395657
Link To Document