Suffix Trees

Definition:
Ein Suffix Tree $T$ für einen String $S$ mit $n$ Zeichen ist ein Baum mit genau $n$ Blättern, welche von 1 bis $n$ numeriert sind. Jeder innere Knoten, außer der Wurzel hat mindestens 2 Kinder und jeder Knoten ist mit einem Teilstring von $S$ beschriftet. Keine zwei Kanten eines Knotens haben Kantenbeschriftungen, die mit dem selben Zeichen beginnen. Von der Wurzel bis zu jedem Blatt lassen sich durch Konkatenation der Kantenbeschriftungen alle Suffixe von $S$ ablesen.

Baum für "ababba":

 6: a
 1: ababba
 3: abba
 5: ba
 2: babba
 4: bba

     |       |(3:abba)|leaf
     |(1:a.b)|
     |       |(5:ba)|leaf
root:|
     |     |(3:a.bba)|leaf
     |(2:b)|
     |     |(5:ba)|leaf

Analyse:
- Der Baum hat wegen $n$ Blättern und Grad $\geq 2$ der inneren Knoten höchstens $floor(n/2)+floor(n/4)+...=n-1$ innere Knoten und benötigt somit nur linearen Speicherplatz $O(n)$.
- Zum Testen, ob irgendein Teilstring $T$ der Länge $m$ als Suffix in $S$ enthalten ist, wird der Baum von der Wurzel gemäß dem Suffix in Zeit $O(m)$ durchlaufen.
- Der Baum lässt sich in linearer Zeit $O(n)$ erstellen [McCreight] [Ukkonen].

Algorithmus: (Suffix Tree erstellen)
Zunächst String $S=S[1]...S[n]$ in Baum einfügen, dann Anfangsposition um eins erhöhen und Suffix $S[2]...S[n]$ mit Baum vergleichen, dabei Knoten und Zweig einfügen usw.

Bemerkungen:
Dieser Algorithmus ist noch primitiv. Er lässt sich erweitern um Suffixzeiger, die vom zuletzt eingefügten Knoten auf Verzweigungen anderer Teilbäume zeigen, ab denen dieselben Suffixe erreichbar sind. Den Zeigern folgend lassen sich zusätzliche Einträge mit gleichen Suffixen schneller realisieren. Der Baum ist in linearer Laufzeit erstellbar [McCreight].