User: Guest  Login
Title:

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

Document type:
Technical Report
Author(s):
Abdullah N. Arslan; Johannes Nowak
Abstract:
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...     »
Keywords:
Algorithms and complexity; pattern matching; dictionary; approximate dictionary look-up; Patricia tree; Hamming distance; edit distance; indexing
Year:
2007
Year / month:
2007-02-01 00:00:00
Pages:
17
 BibTeX