Proc. 8th Annual International Computing and Combinatorics Conference
(COCOON'02), LNCS 2387, Singapore, August 2002, pp. 127-136.
Abdullah N. Arslan and Ömer Egecioglu
Dictionary Look-Up Within Small Edit Distance
Abstract.
Let W be a dictionary consisting
of n binary strings of length m each, represented as a trie.
The usual d-query asks if there exists a string in
W within Hamming distance d of
a given binary query string q.
We present an algorithm to determine
if there is a member in W within edit distance d
of a given query string q of length m.
The method takes time O(d m^{d+1}) in the RAM model, independent of n,
and requires O(dm) additional space.
omer@cs.ucsb.edu