Benutzer: Gast  Login
Titel:

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

Dokumenttyp:
Technical Report
Autor(en):
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...     »
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
 BibTeX