User: Guest  Login
Document type:
Technical Report 
Author(s):
Abdullah N. Arslan; Johannes Nowak 
Title:
Efficient approximate dictionary look-up for long words over small alphabets 
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