Filter algorithms for approximate string matching
Stefan Burkhardt · Max Planck Institute for Plasma Physics · 2002
In this work we present new results and methods for approximate string matching with filter algorithms. We begin with the presentation of QUASAR, our efficient implementation of an improved version of the filter based on the q-gram lemma. The q-gram lemma provides a method based on matching substrings to quickly detect potential matches to a query in a subject or target. We improved and implemented an algorithm originally introduced in 1991. This resulted in a very efficient program for approximate string matching using an index. It was successfully applied to EST-clustering, a problem from computational biology. The second part of our work introduces a new class of filters based on q-grams. We analyze the potential of this somewhat more complicated approach for use in filters for approximate string matching with an index. We consider two important distance measures in approximate string matching, the Hamming and the edit distance. For both problems we provide all the tools required to solve them using q-grams. This includes threshold computation and the selection of good q-grams using predictions of their speed and filtration effciency. Furthermore we consider the potential of q-grams for use in lossy filters. We support our findings with extensive experiments. Our results prove that q-grams are superior to existing filter approaches with respect to speed, filtration efficiency and their potential for use in lossy filters. In dieser Arbeit beschreiben wir neue Ergebnisse und Verfahren auf dem Gebiet der Filteralgorithmen fur Aehnlichkeitssuche in Textdatenbanken. Im ersten Teil stellen wir QUASAR, die Implementierung eines verbesserten Filters basierend auf dem sogenannten q-gram Lemma, vor. Dieses Lemma basiert auf dem Vergleich von kurzen Teilwoerten und ermoglicht die effiziente Erkennung der Teile einer Textdatenbank, die einer bestimmten Anfrage ahneln. Der zweite Teil der Arbeit stellt eine neue Klasse von Filtern die q-grams mit Lucken, sogenannte gapped q-grams, benutzen vor. Wir untersuchen das Potential dieser komplexeren q-grams fur die Nutzung in Filteralgorithmen fur Index-basierte Ahnlichkeitssuche in Textdatenbanken.-