Improved Fast Similarity Search In Dictionaries
Karch Daniel, Luxen Dennis, Sanders Peter. Arxiv 2010
[Paper]
ARXIV
We engineer an algorithm to solve the approximate dictionary matching
problem. Given a list of words , maximum distance fixed at
preprocessing time and a query word , we would like to retrieve all words
from that can be transformed into with or less edit
operations. We present data structures that support fault tolerant queries by
generating an index. On top of that, we present a generalization of the method
that eases memory consumption and preprocessing time significantly. At the same
time, running times of queries are virtually unaffected. We are able to match
in lists of hundreds of thousands of words and beyond within microseconds for
reasonable distances.
Similar Work
