Large amounts of textual data like document collections, DNA sequence data, or the Internet call for fast look-up methods that avoid searching the whole corpus. This is often accomplished using tree-based data structures for text indexing such as tries, PATRICIA trees, or suffix trees. We present and analyze improved algorithms and index data structures for exact and error-tolerant search. Affix trees are a data structure for exact indexing. They are a generalization of suffix trees, allowing a bidirectional search by extending a pattern to the left and to the right during retrieval. We present an algorithm that constructs affix trees on-line in both directions, i.e., by augmenting the underlying string in both directions. An amortized analysis yields that the algorithm has a linear-time worst-case complexity. A space efficient method for error-tolerant searching in a dictionary for a pattern allowing some mismatches can be implemented with a trie or a PATRICIA tree. For a given mismatch probability q and a given maximum of allowed mismatches d, we study the average-case complexity of the number of comparisons for searching in a trie with n strings over an alphabet of size s. Using methods from complex analysis, we derive a sublinear behavior for d < log s n. For constant d, we can distinguish three cases depending upon q. For example, the search complexity for the Hamming distance is s(s-1)d / (d+1)! (logs n)d+1 + O( logd n ). To enable an even more efficient search, we utilize an index of a limited d-neighborhood of the text corpus. We show how the index can be used for various search problems requiring error-tolerant look-up. An average-case analysis proves that the index size is O(n logd n) while the look-up time is optimal in the worst-case with respect to the pattern size and the number of reported occurrences. It is possible to modify the data structure so that its size is bounded in the worst-case while the bound on the look-up time becomes average-case.
Übersetzte Kurzfassung:
Zum Durchsuchen großer Textmengen, wie Dokumentensammlungen, DNS-Sequenzdaten oder dem Internet, werden schnelle Methoden benötigt, mit denen nicht der gesamte Text überprüft werden muss. Dies gelingt häufig durch die Verwendung baumbasierter Datenstrukturen, wie Tries, PATRICIA-Bäumen oder Suffixbäumen. Wir beschreiben und analysieren verbesserte Algorithmen und Index-Datenstrukturen für exaktes und fehlertolerantes Suchen. Affixbäume sind eine Datenstruktur für die Indexierung von Texten zur exakten Suche. Sie stellen eine Verallgemeinerung von Suffixbäumen dar, ermöglichen jedoch eine bidirektionale Suche, bei der während der Suche das Suchwort am Anfang und am Ende erweitert werden kann. Wir stellen einen Algorithmus vor, der Affixbäume online und bidirektional, d. h. durch Erweiterung des zugrunde liegenden Textes an beiden Enden, konstruieren kann. Mittels amortisierter Analyse zeigen wir, dass der Algorithmus im schlechtesten Fall ein lineares Laufzeitverhalten hat. Eine speichereffiziente Möglichkeit zur fehlertoleranten Wörterbuchsuche eines Suchworts mit Abweichungen ("Mismatches") kann mit einem Trie oder einem PATRICIA-Baum realisiert werden. Gegeben seien eine Abweichungswahrscheinlichkeit q und eine Begrenzung der Anzahl der erlaubten Abweichungen d, dann untersuchen wir die durchschnittliche Komplexität der Anzahl der Vergleiche bei der Suche in einem Trie für n Wörter über einem Alphabet der Größe s. Mit Methoden der komplexen Analysis leiten wir ein sublineares Verhalten für d < logs n her. Für ein konstantes d können wir differenziert nach q drei Komplexitätsfälle unterscheiden. Dies ergibt z. B. für die Hamming-Distanz eine Komplexität von s(s-1)d / (d+1)! (logs n)d+1 + O( logd n ). Um eine noch effizientere Suche zu ermöglichen, setzen wir einen Index für eine beschränkte d-Nachbarschaft der zugrunde liegenden Texte ein. Wir zeigen, wie dieser Index für verschiedene Suchprobleme der fehlertoleranten Suche genutzt werden kann. Im Rahmen einer Analyse des Durchschnittsfalls beweisen wir, dass die Indexgröße O(n logd n) ist, während die Suchzeit selbst im schlechtesten Fall mit Bezug auf die Länge des Suchwortes und die Anzahl der Fundstellen asymptotisch optimal ist. Es ist möglich, die Beschränkung der Indexgröße im schlechtesten Fall sicher zu stellen, wobei dann jedoch die Begrenzung der Suchzeit nur noch für den Durchschnittsfall gilt.
Veröffentlichung:
Universitätsbibliothek der Technischen Universität München
Login
BibTeX