Suffixbaum

Suffixbaum für abbabbab, Blätter sind mit den Startindizes (1-basiert) der entsprechenden Suffixe beschriftet, $ markiert das Ende eines Suffixes

Ein Suffixbaum ist in der Informatik eine vielseitige Datenstruktur, die effiziente Lösungen zahlreicher Probleme im Bereich der Stringverarbeitung ermöglicht. Ein Suffixbaum speichert alle Suffixe⁣⁣ (Endungen) einer Zeichenkette. Er kann in linearer Zeit mit linearem Speicherverbrauch aufgebaut werden und ermöglicht, einmal aufgebaut, das schnelle Durchführen vieler Operationen wie die Suche nach Wörtern oder Sätzen in längeren Texten.

Definition

Ein Suffixbaum ${\displaystyle T}$ für einen String ${\displaystyle S}$ mit ${\displaystyle n}$ Symbolen ist ein gerichteter Baum, der die folgenden Bedingungen erfüllt:

1. Der Baum hat ${\displaystyle n}$ Blätter
2. Jede Kante ist mit einem Teilstring von ${\displaystyle S}$ beschriftet
3. Jeder innere Knoten von ${\displaystyle T}$ (außer der Wurzel) hat mindestens zwei Kinder, deren Kantenbeschriftungen nie mit dem gleichen Symbol beginnen
4. Für jedes Blatt ${\displaystyle i}$ in ${\displaystyle T}$ ergeben die Beschriftungen der Kanten auf dem Pfad von der Wurzel zu ${\displaystyle i}$ aneinander gehängt das Suffix von ${\displaystyle S}$, das an Index ${\displaystyle i}$ beginnt
5. ${\displaystyle T}$ enthält alle Suffixe von ${\displaystyle S}$, wobei mehrfach auftretende Teilstrings nur einmal in ${\displaystyle T}$ enthalten sind (siehe Abbildung)

Ein solcher Baum kann nicht für Strings erzeugt werden, die ein Suffix enthalten, das auch ein Präfix von einem anderen Suffix ist. Beispielsweise ist das Suffix cd aus dem String abcdcd auch ein Präfix des Suffix cdcd. Um die vierte Regel nicht zu verletzen, kann in diesem Fall ein Endsymbol (typischerweise $) angehängt werden, das nicht im Alphabet des Strings vorkommt. Da dieses Zeichen nicht im Text vorkommen kann und das Ende jedes Suffixes ist, können alle Suffixe keine Präfixe mehr sein. Dadurch wird sichergestellt, dass es ${\displaystyle n}$ Blätter gibt, eins für jedes Suffix.[1] Da alle internen Knoten (Wurzel ausgenommen) verzweigt sind, kann es höchstens ${\displaystyle n-1}$ solcher Knoten geben. Damit kann es mit Wurzel und Blättern insgesamt nicht mehr als ${\displaystyle n+(n-1)+1=2n}$ Knoten geben.

Die String-Tiefe ${\displaystyle d(v)}$ eines Knotens ${\displaystyle v}$ gibt an, wie viele Zeichen die kombinierten Kantenbeschriftungen auf dem Weg von der Wurzel zum Knoten haben. Für ein Blatt entspricht das der Länge des Suffixes, das es repräsentiert.

Konstruktion

Der Baum besteht zu Anfang aus einem Wurzelknoten und einer Liste von (Zeigern auf) allen fortsetzbaren Stellen im Baum, das heißt zu Anfang aus lediglich einem Zeiger auf den Wurzelknoten.

Der Baum wird für ein schrittweise zu verlängerndes Wort aufgebaut. Für alle Knoten aus der Liste der fortsetzbaren Stellen wird eine Kante zu einem neuen Knoten gezogen. Diese Kante wird mit dem zuletzt an das Wort angefügten Buchstaben beschriftet. Dieser neue Knoten wird dann in eine Liste der fortsetzbaren Stellen für die nächste Iteration aufgenommen. Zuletzt wird immer auch der Startknoten mit in die neue Liste aufgenommen (da das leere Wort immer ein gültiges Suffix ist).

Existiert zu einer fortsetzbaren Stelle bereits eine Kante, deren Beschriftung dem zuletzt angefügten Buchstaben entspricht, so wird kein Knoten hinzugefügt, und stattdessen der bereits existierende Zielknoten in die Liste der fortsetzbaren Stellen aufgenommen.

Durch das Hinzufügen des Startknotens in jedem Schritt ist die Liste der fortsetzbaren Stellen nach ${\displaystyle n}$ Iterationen auch ${\displaystyle n+1}$ Elemente lang, was in quadratischer Laufzeit resultiert. Mithilfe des Suffixarrays und des LCP-Arrays ist es möglich, den Baum auch in linearer Zeit aufzubauen.

Dafür werden die Suffixe in der Reihenfolge des Suffixarrays ${\displaystyle A}$ eingefügt. Sei ${\displaystyle T_{i}}$ der partielle Suffixbaum, der die ersten ${\displaystyle i}$ Suffixe enthält und ${\displaystyle H}$ das LCP-Array.

Der Algorithmus beginnt mit ${\displaystyle T_{0}}$, also nur der Wurzel des Baums. Im Schritt ${\displaystyle i+1}$ wandern wir den rechtesten Pfad (also den Pfad von dem Blatt mit dem Label ${\displaystyle A[i]}$ bis zur Wurzel) von ${\displaystyle T_{i}}$ so lange herauf, bis wir den tiefsten Knoten ${\displaystyle v}$ mit der String-Tiefe ${\displaystyle d(v)\leq H[i+1]}$ finden. Wenn ${\displaystyle d(v)=H[i+1]}$, wird einfach ein neues Blatt ${\displaystyle x}$ als Kind von ${\displaystyle v}$ eingefügt. Dieses Blatt hat das Label ${\displaystyle A[i+1]}$. Damit erhalten wir ${\displaystyle T_{i+1}}$ und gehen zum nächsten Schritt. Wenn hingegen ${\displaystyle d(v)<H[i+1]}$ gilt, also das neue Suffix innerhalb einer Kante von ${\displaystyle v}$ zum rechtesten Kind ${\displaystyle w}$ abzweigt, muss die bestehende Kante ${\displaystyle (v,w)}$ aufgespalten werden. Dazu wird erst die Kante ${\displaystyle (v,w)}$ gelöscht. Dann wird ein neuer Knoten ${\displaystyle y}$ eingefügt, mit einer Kante ${\displaystyle (v,y)}$, die den Teil der Kantenbeschriftung bekommt, der direkt vor der Stelle liegt, an der aufgeteilt werden muss (formal: ${\displaystyle S_{A[i]+d(v)\dots A[i]+H[i+1]-1}}$). Dann wird die Kante ${\displaystyle (y,w)}$ eingefügt, die den restlichen Teil der ursprünglichen Kantenbeschriftung erhält (formal: ${\displaystyle S_{A[i]+H[i+1]\dots A[i]+d(w)-1}}$). Als Letztes wird ein neues Blatt ${\displaystyle x}$ (mit Label ${\displaystyle A[i+1]}$) und eine Kante ${\displaystyle (y,x)}$ eingefügt. Die Kante bekommt den Teil des neuen Suffixes ${\displaystyle A[i+1]}$ als Label, der bisher nicht von ${\displaystyle S_{i}}$ abgedeckt wird (formal: ${\displaystyle S^{A[i+1]+H[i+1]}}$).

Obwohl das Heraufwandern auf dem rechten Pfad in einem einzigen Schritt ${\displaystyle O(n)}$ Zeit in Anspruch nehmen könnte, ist die Laufzeit dieses Algorithmus durch ${\displaystyle O(n)}$ insgesamt begrenzt, denn: Jeder im Schritt ${\displaystyle i}$ durchquerte Knoten (außer dem letzten) wird vom rechten Pfad entfernt und wird für alle nachfolgenden Schritte ${\displaystyle j>i}$ nicht mehr betrachtet. Es werden also insgesamt höchstens ${\displaystyle 2n}$ Knoten durchlaufen.[2]

Anwendungen

Suffixbäume ermöglichen eine effiziente Lösung zahlreicher Probleme im Bereich der Stringverarbeitung. Eine verbreitete Anwendung besteht in der Implementierung von String-Matching-Algorithmen in Suchmaschinen aufgrund der geringen Laufzeitkomplexität.

Für die Fuzzy-String-Suche ermöglicht ein Suffixbaum effiziente Verfahren, wie beim Vergleich mit wildcards oder k-mismatch[3] oder in Form einer Beschleunigung der Ermittlung der Levenshtein-Distanz über hybrides dynamic programming[4].

Weitere Anwendungsgebiete sind in der Bioinformatik, u. a. in der DNA-Sequenzanalyse, und in der Datenkompression, zur Identifizierung von sich wiederholenden Daten, zu finden.

Suchen in Suffixbäumen

Ein Suchtext ${\displaystyle P[1,m]}$ kann im Suffixbaum ${\displaystyle T}$ gefunden werden, indem der Baum von der Wurzel an Buchstabe für Buchstabe heruntergewandert wird. Dabei werden maximal ${\displaystyle m}$ Zeichen verglichen. Wenn an jedem Knoten die ausgehenden Kanten lexikografisch sortiert sind, kann die richtige Kante mit binärer Suche in ${\displaystyle O(\log \sigma )}$ Zeit gefunden werden, wobei ${\displaystyle \sigma }$ die Anzahl der ausgehenden Kanten ist. Dadurch ergibt sich eine Laufzeit von ${\displaystyle O(m\log \sigma )}$. Durch gewichtete binäre Suche kann diese Lautzeit auf ${\displaystyle O(m+\log \sigma )}$ verbessert werden, wobei das Gewicht der Kanten durch die Anzahl der Blätter, die durch diese Kante erreicht werden können, bestimmt wird.

Um herauszufinden, wie oft der Suchtext ${\displaystyle P}$ im String ${\displaystyle S}$ vorkommt, wird ${\displaystyle T}$ so lange traversiert, bis ${\displaystyle P}$ komplett eingelesen wurde. Dies bringt uns zu einem Knoten ${\displaystyle v}$ oder einer eingehenden Kante zu Knoten ${\displaystyle v}$. Die Anzahl der Blätter im Subbaum ${\displaystyle S_{v}}$, mit ${\displaystyle v}$ als Wurzel, gibt an, wie oft ${\displaystyle P}$ in ${\displaystyle S}$ vorkommt. Wenn diese Information in jedem Knoten mitgespeichert wird, kann dies in konstanter Zeit geschehen.

Um die Stellen zu finden, an denen der Suchtext ${\displaystyle P}$ vorkommt, wird wieder Knoten ${\displaystyle v}$ gesucht und dann für alle Blätter von ${\displaystyle S_{v}}$ die Stelle im Text ausgegeben, die sie repräsentieren.

Geschichte

Das Konzept wurde erstmals von Weiner (1973)[5] eingeführt. Anstelle des Suffixes ${\displaystyle S[i\dots n]}$ speicherte Weiner in seinem Trie den Präfixbezeichner für jede Position, d. h. die kürzeste Zeichenkette, die bei ${\displaystyle i}$ beginnt und nur einmal in ${\displaystyle S}$ vorkommt. Sein Algorithmus D nimmt einen unkomprimierten Trie für ${\displaystyle S[k+1\dots n]}$ und erweitert ihn zu einem Trie für ${\displaystyle S[k\dots n]}$. Auf diese Weise kann, ausgehend vom trivialen Trie für ${\displaystyle S[n\dots n]}$, ein Trie für ${\displaystyle S[1\dots n]}$ durch ${\displaystyle n-1}$ aufeinanderfolgende Aufrufe von Algorithmus D aufgebaut werden; die Gesamtlaufzeit beträgt jedoch ${\displaystyle O(n^{2})}$. Weiners Algorithmus B benutzt mehrere Hilfsdatenstrukturen, um eine Gesamtlaufzeit zu erreichen, die linear zur Größe des konstruierten Trie ist. Letztere kann immer noch aus ${\displaystyle O(n^{2})}$ Knoten bestehen, z. B. für ${\displaystyle S=a^{n}b^{n}a^{n}b^{n}\$}$. Weiners Algorithmus C verwendet schließlich komprimierte Tries, um eine lineare Gesamtspeichergröße und Laufzeit zu erreichen. Das Lehrbuch Aho, Hopcroft & Ullman (1974, Kap. 9.5)[6] gab Weiners Ergebnisse in vereinfachter und eleganterer Form wieder und führte den Begriff Positionsbaum ein.

McCreight (1976)[7] war der Erste, der einen (komprimierten) Trie aller Suffixe von S erstellte. Obwohl das bei ${\displaystyle i}$ beginnende Suffix in der Regel länger ist als der Präfixbezeichner, unterscheiden sich ihre Pfaddarstellungen in einem komprimierten Trie nicht in der Größe. Andererseits konnte McCreight auf die meisten der Weiner'schen Hilfsdatenstrukturen verzichten; es blieben nur die Suffix-Links übrig.

Ukkonen (1995)[8] vereinfachte die Konstruktion weiter[9] und lieferte die erste Online-Konstruktion von Suffixbäumen, die heute als Ukkonen-Algorithmus bekannt ist, mit einer Laufzeit, die den damals schnellsten Algorithmen entspricht. Diese Algorithmen laufen alle in linearer Zeit für ein Alphabet konstanter Größe und haben sonst im schlimmsten Fall eine Laufzeit von ${\displaystyle O(n\log n)}$.

Farach (1997)[10] gab den ersten Algorithmus zur Konstruktion von Suffixbäumen an, der für alle Alphabete optimal ist. Insbesondere ist dies der erste Algorithmus mit linearer Zeit für Zeichenketten, die aus einem Alphabet von ganzen Zahlen in einem polynomialen Bereich gezogen werden. Farachs Algorithmus wurde zur Grundlage für neue Algorithmen zur Konstruktion von Suffixbäumen und Suffixarrays.

Siehe auch

• Suffixarray
• Trie
• Patricia-Trie

Literatur

• Dan Gusfield: Algorithms on Strings, Sequences and Trees. 1999, ISBN 978-0-521-58519-4 (englisch, Erstausgabe: 1997). 
• Hans-Joachim Böckenhauer und Dirk Bongartz: Algorithmische Grundlagen der Bioinformatik. 2003, ISBN 978-3-519-00398-4. 

Weblinks

Commons: Suffix tree – Sammlung von Bildern, Videos und Audiodateien

• Definition (nist.gov) (englisch)
• Fast String Searching with Suffix Trees (englisch)

Einzelnachweise

1. Introduction to Suffix Trees. In: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge 1997, ISBN 978-0-521-58519-4, S. 89–93, doi:10.1017/cbo9780511574931.007. 
2. Linear-Time Construction of Suffix Trees. In: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge 1997, ISBN 978-0-521-58519-4, S. 94–121, doi:10.1017/cbo9780511574931.008. 
3. Dan Gusfield: Algorithms on Strings, Sequences and Trees. 1999, ISBN 978-0-521-58519-4, S. 199 (englisch, Erstausgabe: 1997). 
4. Dan Gusfield: Algorithms on Strings, Sequences and Trees. 1999, ISBN 978-0-521-58519-4, S. 279 (englisch, Erstausgabe: 1997). 
5. Peter Weiner: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory (swat 1973). IEEE, Oktober 1973, S. 1–11, doi:10.1109/swat.1973.13. 
6. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The design and analysis of computer algorithms (= Addison-Wesley series in computer science and information processing). Addison-Wesley Pub. Co, Reading, Mass 1974, ISBN 978-0-201-00029-0. 
7. Edward M. McCreight: A Space-Economical Suffix Tree Construction Algorithm. In: J. ACM. Band 23, Nr. 2, 1. April 1976, ISSN 0004-5411, S. 262–272, doi:10.1145/321941.321946. 
8. E. Ukkonen: On-line construction of suffix trees. In: Algorithmica. Band 14, Nr. 3, 1. September 1995, ISSN 1432-0541, S. 249–260, doi:10.1007/BF01206331. 
9. R. Giegerich, S. Kurtz: From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction. In: Algorithmica. Band 19, Nr. 3, 1. November 1997, ISSN 1432-0541, S. 331–353, doi:10.1007/PL00009177. 
10. M. Farach: Optimal suffix tree construction with large alphabets. IEEE Comput. Soc, 1997, ISBN 978-0-8186-8197-4, S. 137–143, doi:10.1109/SFCS.1997.646102.