Translated abstract:
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.