Suffix-Links

Definition 11   Sei $x\alpha$ ein beliebiger String mit $x\in \Sigma$ und $\alpha \in \Sigma^*$. Wenn ein innerer Knoten v Label $x\alpha$ besitzt und ein anderer Knoten s(v) den Label $\alpha$, so bezeichnen wir den Zeiger $v\rightarrow s(v)$ als Suffix-Link.

Lemma 1   Wenn ein neuer innerer Knoten v mit Label $x\alpha$ in Erweiterung j einer Phase i+1 hinzugefügt wird, dann gilt eine der beiden Aussagen:

1.

Der Pfad mit Label $\alpha$ endet schon in einem inneren Knoten s(v).

2.

Am Ende von String $\alpha$ wird in Erweiterung j+1 von Phase i+1 ein neuer innerer Knoten s(v) angelegt.

Beweis: Da v ein neuer Knoten ist, muß Regel 2 angewandt worden sein, d.h. es gibt ein neues Blatt mit Nummer j, und die Kante zum Blatt hat Label S[i+1]. Außerdem gibt es von v aus noch mindestens einen anderen Pfad, dessen Label z.B. mit c beginnt (siehe Abbildung 20).

  

Abbildung 20: Zwei aufeinander folgende Erweiterungen in Phase i+1

In Erweiterung j+1 wird das Präfix $\alpha$ im Baum gesucht, von dem wir wissen, daß es auf jeden Fall von c gefolgt wird. Dann gibt es zwei Fälle:

1.

$\alpha$ wird nur von c gefolgt. Dann gibt es wie in Erweiterung j ein neues Blatt (mit Nummer j+1, die Kante zum Blatt hat Label S[i+1]) und einen neuen inneren Knoten s(v).

2.

$\alpha$ wird auch von anderen Buchstaben als c gefolgt. Dann gibt es schon einen Knoten s(v).

Korollar 2   In Ukkonens Algorithmus hat jeder neu kreierte innere Knoten am Ende der nächsten Erweiterung einen ausgehenden Suffix-Link.

Beweis: Übung.

anders ausgedrückt:

Korollar 3   Wenn in einem beliebigen impliziten Suffix-Baum ${\cal{T}}_i$ ein innerer Knoten Label $x\alpha$ hat, dann gibt es in ${\cal{T}}_i$ einen Knoten s(v) mit Label $\alpha$.

Man beachte, daß s(v) durchaus die Wurzel sein kann. Wie benutzen wir Suffix-Links während des Algorithmus? Wir betrachten dazu die beiden ersten Erweiterungen in irgendeiner Phase i+1.

1.

Die erste Erweiterung erfolgt immer nach Regel 1 und kann deshalb in konstanter Zeit ausgeführt werden (siehe auch Abbildung 21 1).

2.

Sei (v,1) die Kante, welche in Blatt 1 endet und $x\alpha=S[1..i]$. Wir müssen nun $\alpha=S[2..i]$ in ${\cal{T}}_{i+1}$ suchen. Dazu gibt es zwei Möglichkeiten (siehe auch auch Abbildung 21 2) :

(a)

v ist die Wurzel. Dann suche $\alpha$ naiv.

(b)

v ist ein innerer Knoten. Sei $\gamma$ der Label der Kante (v,1). Wir folgen dann dem Link von v zu s(v), folgen dem Pfad mit Label $\gamma$ nach unten und wenden die Erweiterungsregeln für S[i+1] an.

  

Abbildung 21: Wie werden Suffix-Links benutzt ?

Analog geht man in den Erweiterungen für j>1 vor, wobei man eventuell nicht von einem Blatt nach oben läuft, sondern von einem inneren Knoten nach oben läuft oder direkt einem, in dem Knoten schon vorhandenen, Suffix-Link folgt.

Wir stellen fest, daß der Algorithmus in Erweiterung j nie mehr als einen Knoten im Baum nach oben läuft, da es nach Korollar 2 dort einen Suffix-Link gibt. Bringt uns dies eine Verbesserung in der Laufzeit? Wenn wir nach Beobachtung 2 die Kanten nur mit den entsprechenden Indizes beschriften, so können wir beim Durchqueren des Baumes von v nach s(v) und dann bis zum Ende von $\gamma$ jede Kante in konstanter Zeit durchlaufen, da die Beschriftung nicht verglichen werden muß. Die beiden Abbildungen 22 und 23 zeigen die letzten Phasen von Ukkonens Algorithmus für den String xabxacbxd.

  

Abbildung 22: Beispiel 1. Teil

  

Abbildung 23: Beispiel 2. Teil

Wir brauchen noch folgende Beobachtung:

Beobachtung 3   Sei (v,s(v)) ein Suffix-Link, der während Ukkonens Algorithmus durchquert wird. Die Knotentiefe von v ist dann höchstens um eins größer als die von s(v).

Diese Beobachtung folgt direkt, da jeder innerer Knoten auf dem Pfad zu v einen Suffix-Link zu verschiedenen Knoten auf dem Pfad von der Wurzel zu s(v) hat. Somit gilt folgender Satz:

Satz 8   Jede Phase in Ukkonens Algorithmus braucht O(m) Zeit.

Beweis: In den $i+1\leq m$ Erweiterungen in Phase i+1 läuft der Algorithmus jeweils höchstens um eine Kante nach oben, überquert eventuell einen Suffix-Link und läuft einige Kanten nach unten. Wenn man dabei die Knotentiefe der durchlaufenen Knoten betrachtet, so nimmt sie um höchstens zwei ab (laufe zu v dann zu s(v)) und nimmt dann etwas zu. Da kein Knoten eine Knotentiefe > m haben kann und über alle Erweiterungen summiert die Knotentiefe in dieser Phase um höchstens 2m abnimmt, kann die Knotentiefe um höchsten 3m zunehmen. Insgesamt können also höchstens 5m Knoten besucht werden. Da jeder Besuch konstante Zeit kostet, folgt der Satz.

haben wir nun eine Laufzeit von O(m²). Jetzt fehlen uns nur noch zwei Beobachtungen, um die Laufzeit von O(m²) auf O(m) zu drücken.

Beobachtung 4   Sobald in einer Phase i+1 in einer Erweiterung j Regel 3 angewendet wird, kann die Phase beendet werden, da danach immer Regel 3 angewendet wird. Wir nennen die Erweiterungen bis j explizit, die Erweiterung ab j implizit.

Beobachtung 5   Ein Blatt bleibt immer ein Blatt, d.h. es wird immer durch Regel 1 erweitert. Weiter gilt, daß es am Anfang von Phase i immer eine Sequenz von Erweiterungen nach Regel 1 und 2 gibt. Sei j_i die letzte Erweiterung in dieser Sequenz. Da Regel 2 immer ein neues Blatt erzeugt, gilt $j_i\leq j_{i+1}$. Beschriftet man nun alle Blätter im Laufe des Algorithmus nicht mit (p,i+1) sondern mit einem globalen Endmarker (p,e), so kann man die Erweiterungen bis j_i implizit vornehmen, indem man e auf i+1 setzt.

Man kann also die Vorgehensweise in Phase i+1 wie folgt beschreiben:

1.

Setze e auf i+1.

2.

Führe mit Hilfe von Suffix-Links Erweiterungen durch, bis in Erweiterung j^* Regel 3 angewandt wird.

3.

Setze j_i+1 auf j^*-1 und gehe zur nächsten Phase.

Somit haben aufeinanderfolgende Phasen des Algorithmus höchstens einen Index gemeinsam, für den explizite Erweiterungen berechnet werden (siehe Abbildung 24).

  

Abbildung 24: Explizite Erweiterungen im Laufe des Algorithmus

Zusammenfassend gilt nun folgender Satz:

Satz 9   Ukkonens Algorithmus konstruiert einen impliziten Suffix-Baum ${\cal{T}}_m$ in Zeit O(m).

Beweis: Die Zeit für alle impliziten Erweiterungen ist in jeder Phase konstant und somit O(m) für die m Phasen. Wenn $\bar{j}$ der Index der expliziten Erweiterungen während des Laufs des Algorithmus ist, so nimmt $\bar{j}$ nie ab, bleibt aber zwischen zwei aufeinander folgenden Phasen gleich. Da es nur m Phasen gibt und $\bar{j}$ durch m beschränkt ist, gibt es insgesamt höchstens 2m explizite Erweiterungen. Da die auf eine Phase i folgende Phase i+1 mit der letzten expliziten Erweiterung j^* von Phase i anfängt, ändert sich die Knotentiefe nicht, und es folgt analog zum Beweis von Satz 8, daß insgesamt nur O(m) Knoten durchlaufen werden.