Benutzer: Gast  Login
Dokumenttyp:
Technical Report 
Autor(en):
Abdullah N. Arslan; Johannes Nowak 
Titel:
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...    »
 
Stichworte:
Algorithms and complexity; pattern matching; dictionary; approximate dictionary look-up; Patricia tree; Hamming distance; edit distance; indexing 
Jahr:
2007 
Jahr / Monat:
2007-02-01 00:00:00 
Seiten/Umfang:
17