ACM Journal of Experimental Algorithmics · 2011 · 86 citations · 119 references
ComputingComputer ScienceComputational LinguisticsInformation RetrievalNatural Language ProcessingRetrieval ModelsSequence Similarity SearchEdit DistanceExact Match RetrievalIndexing Data StructuresSequence FilteringString Indexing
The primary goal of this article is to survey state-of-the-art indexing methods for approximate dictionary searching. To improve understanding of the field, we introduce a taxonomy that classifies all methods into direct methods and sequence-based filtering methods. We focus on infrequently updated dictionaries, which are used primarily for retrieval. Therefore, we consider indices that are optimized for retrieval rather than for update. The indices are assumed to be associative, that is, capable of storing and retrieving auxiliary information, such as string identifiers. All solutions are lossless and guarantee retrieval of strings within a specified edit distance k . Benchmark results are presented for the practically important cases of k =1, 2, and 3. We concentrate on natural language datasets, which include synthetic English and Russian dictionaries, as well as dictionaries of frequent words extracted from the ClueWeb09 collection. In addition, we carry out experiments with dictionaries containing DNA sequences. The article is concluded with a discussion of benchmark results and directions for future research.
119
Binary codes capable of correcting deletions, insertions and reversals
V.I. Levenshtein · Soviet physics. Doklady · 1965 · 10.4K citations
Multidimensional binary search trees used for associative searching
Jon Bentley · Communications of the ACM · 1975 · 7.5K citations · Full text