Fast Approximate Search in Large Dictionaries
Authors:
Open Access
- 1 December 2004
- journal article
- Published by MIT Press in Computational Linguistics
- Vol. 30 (4) , 451-477
Abstract
The need to correct garbled strings arises in many areas of natural language processing. If a dictionary is available that covers all possible input tokens, a natural set of candidates for correcting an erroneous input P is the set of all words in the dictionary for which the Levenshtein distance to Pdoes not exceed a given (small) bound k. In this article we describe methods for efficiently selecting such candidate sets. After introducing as a starting point a basic correction method based on the concept of a “universal Levenshtein automaton,” we show how two filtering methods known from the field of approximate text search can be used to improve the basic procedure in a significant way. The first method, which uses standard dictionaries plus dictionaries with reversed words, leads to very short correction times for most classes of input strings. Our evaluation results demonstrate that correction times for fixed-distance bounds depend on the expected number of correction candidates, which decreases for longer input words. Similarly the choice of an optimal filtering method depends on the length of the input words.Keywords
This publication has 30 references indexed in Scilit:
- Incremental Construction of Minimal Acyclic Finite-State AutomataComputational Linguistics, 2000
- Faster Approximate String MatchingAlgorithmica, 1999
- TECHNIQUES FOR IMPROVING OCR RESULTS1997
- HIDDEN MARKOV MODELS IN TEXT RECOGNITIONInternational Journal of Pattern Recognition and Artificial Intelligence, 1995
- HIERARCHICALLY CODED LEXICON WITH VARIANTSInternational Journal of Pattern Recognition and Artificial Intelligence, 1995
- Fast string matching using an n-gram algorithmSoftware: Practice and Experience, 1994
- An approximate string-matching algorithmTheoretical Computer Science, 1992
- Automatic spelling correction using a trigram similarity measureInformation Processing & Management, 1983
- Retrieval of misspelled names in an airlines passenger record systemCommunications of the ACM, 1962
- A program for correcting spelling errorsInformation and Control, 1960