Efficient approximate dictionary look-up for long words over small alphabets

Given a dictionary W consisting of n strings of length m each, the approximate dictionary look-up problem asks if there is a member in W within a given distance d from a given query string q. We present new hybrid tree/dynamic programming algorithms for the approximate dictionary look-up problem. The approach works for both Hamming and edit distances. We use a new tree data structure, prefix-partitioned look-up tree, which generalizes Patricia trees. The complexities of the algorithms depend on the height h and branching factor b of the tree used. Our approach is space-efficient, and answers a query in O(m(b-1)^d h^{d+1}) time when Hamming distance is used (the time complexity increases by a factor of O(db^d h^d) for the edit-distance case).     «

Given a dictionary W consisting of n strings of length m each, the approximate dictionary look-up problem asks if there is a member in W within a given distance d from a given query string q. We present new hybrid tree/dynamic programming algorithms for the approximate dictionary look-up problem. The approach works for both Hamming and edit distances. We use a new tree data structure, prefix-partitioned look-up tree, which generalizes Patricia trees. The complexities of the algorithms depend on...     »