Title :
A fast algorithm for finding the nearest neighbor of a word in a dictionary
Author_Institution :
Inst. of Inf. & Appl. Math., Bern, Switzerland
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;
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
DOI :
10.1109/ICDAR.1993.395657
