Konstruktion vonSuffix BumenProf. Dr. S. AlbersProf. Dr. Th. Ottmann

WS03/04

Ukkonens Algorithmus: Impliziter Suffix BaumDefinition: Ein impliziter Suffix Baum ist der Baum, den man aus demSuffix Baum fr t$ enthlt indem man :

(1) $ von den Markierungen der Kanten entfernt,

(2) Kanten ohne Markierung entfernt,

(3) Knoten mit nur einem Kind entfernt.

WS03/04

Ukkonens Algorithmus: Impliziter Suffix Baumt = x a b x a $ 1 2 3 4 5 6x ab x a $$142563b x a $a$$$ a x b

WS03/04

Ukkonens Algorithmus: Impliziter Suffix Baum(1) Entfernen der Kantenmarkierung $ fr t = x a b x a $x ab x a 142563b x a aa x b

WS03/04

Ukkonens Algorithmus: Impliziter Suffix Baum(2) nicht markierten Kanten entfernen

t = x a b x a $ 1 2 3 4 5 6x ab x a 123b x a aa x b

WS03/04

Ukkonens Algorithmus: Impliziter Suffix Baum(3) Knoten mit nur einem Kind entfernen

t = x a b x a $ 1 2 3 4 5 6x a b x a 123a b x a a x b

WS03/04

Ukkonens AlgorithmusSei t = t1t2t3 ... tm

Ukk arbeitet online: Der Suffix Baum ST(t) wird schrittweise durch Konstruktion einer Reihe von impliziten Suffix Bumen fr alle Prfixe von t konstruiert:

ST(), ST(t1), ST(t1t2), ..., ST(t1t2 ... tm)

ST() ist der leere implizite Suffix Baum. Er besteht nur aus der Wurzel

WS03/04

Ukkonens AlgorithmusDie Methode wird online genannt, weil in jedem Schritt der impliziteSuffix Baum fr ein Anfangsstck von t konstruiert wird ohne den Rest des Inputstrings zu kennen.Der Algorithmus arbeitet also inkrementell, da er den Input String zeichenweise von links nach rechts liest.

WS03/04

Ukkonens AlgorithmusInkrementelle Konstruktion des impliziten Suffixbaumes:

Induktionsanfang: ST() besteht nur aus der Wurzel.

Induktionsschritt: Aus ST(t1 .... ti) wird ST(t1 ... titi+1), fr alle i < m Sei Ii der implizite Suffix Baum fr t[1...i]Zuerst konstruiert man I1 : Der Baum hat nur eine Kante, die mit dem Zeichen t1 markiert ist.Die in Phase i+1 zu lsende Aufgabe ist, Ii+1 aus Ii fr i = 1 bis m 1 zu konstruieren.

WS03/04

Ukkonens AlgorithmusPseudo-code Formulierung von ukk:

Konstruiere Baum I1for i = 1 to m 1 dobegin {Phase i+1}for j = 1 to i +1 do begin {Erweiterung j}Finde das Ende des Pfades von der Wurzel, der mit t[j ... i] markiert ist, im aktuellen Baum.Falls erforderlich, erweitere ihn durch Hinzufgen des Zeichens t[i+1], damit gewhrleistet ist, dass derString t[j...i+1] im Baum ist. end;end;

WS03/04

Ziel: Verbesserung der Laufzeit von ukkUnterscheide zwischen impliziten und expliziten ErweiterungenIn Phase i+1 werden alle impliziten Erweiterungen auf einmal in konstanter Zeit ausgefhrt.Die Gesamtzahl aller (echten) expliziten Erweiterungen in allen m-1 Erweiterungs-Phasen kann durch O(m) beschrnkt werden.Benutze Suffix-Links, um den Zeitaufwand pro expliziter Erweiterung (amortisiert) in konstanter Zeit auszufhren.Zeige, dass Suffix-Links whrend der expliziten Erweiterungen mit konstantem Zusatzaufwand eingefgt werden knnen, so dass jeder implizite Suffix Baum am Ende einer jeden Erweiterungsphase fr alle inneren Knoten Suffix-Links hat.

WS03/04

Beispielt = a c c a $aa ca c ca c c acc ccc a a11 21 21 3 2Schritt 1Schritt 2I1 I2 I3 I4

WS03/04

Ukkonens AlgorithmusJede Erweiterung j wird so durchgefhrt, dass man das Ende desPfades von der Wurzel, gekennzeichnet mit t[j...i], findet und denPfad durch das Zeichen t[i+1] erweitert.

In Phase i+1 wird zuerst der String t[1...i+1] in den Baum eingefgt,gefolgt von den Strings t[2...i+1] , t[3...i+1] ,....(entsprechend den Erweiterungen 1,2,3,.... In Phase i+1)

Erweiterung i+1 in Phase i+1 fgt das einzelne Zeichent[i+1] in den Baum ein (es sei denn es ist schon vorhanden)

WS03/04

Ukk: Suffix Erweiterungs-RegelnDer Erweiterungs-Schritt j (in Phase i+1) wird nach einer der folgenden Regeln durchgefhrt:

Regel 1:Wenn t[j...i] in einem Blatt endet, wird t[i+1] an die Markierung der zum Blatt fhrenden Kante angehngt.

Regel 2: Falls kein Pfad vom Ende von t[j...i] mit dem Zeichen t[i+1] anfngt, wird eine neue Kante zu einem neuen Blatt erzeugt, die mit dem Zeichen t[i+1] markiert wird. (Das ist die einzige Erweiterung, die die Anzahl der Bltter im Baum erhht! Das Blatt reprsentiert bei Position j beginnende Suffixe.)

Regel 3: Falls ein mit dem Zeichen t[i+1] markierter Pfad am Ende von t[j..i] beginnt, tut man nichts. (Denn dann tritt t[ji+1] tritt bereits im Baum auf.)

WS03/04

Beispielt = a c c a $t[1...3] = acc t[1...4] = accaa c cc c1 2a c c ac c1 2ErweitereSuffix 1Regel 1t[1..4] = accaErweitereSuffix 2Regel 1a c c ac c a1 2t[2..4] = ccaa c c acc a a1 3 2ErweitereSuffix 3Regel 2t[3..4] = cat[4..4] = aRegel 3a ist bereitsim BaumI3

WS03/04

Beobachtung 1Bei Durchfhrung von Phase i +1 (der Vorgang, durch den Ii+1 aus Iikonstruiert wird) kann man beobachten:

(1) Sobald in Erweiterung j erstmals Regel 3 angewandt wurde, muss der Pfad, der mit t[j...i] im aktuellen Baum Ii markiert ist, eine Fortsetzung mit Zeichen t[i+1] haben. Dann muss auch fr jedes j j der Pfad , der mit t[j... i] markiert ist, ebenfalls eine Fortsetzung mit Zeichen t[i+1] haben.

Daher wird Regel 3 auch fr Erweiterung j fr j= j+1... i+1 angewandt. Wenn man also einmal Regel 3 fr eine Erweiterung j in Phase i +1angewandt hat kann man diese Phase beenden.

WS03/04

Beobachtung 2

(2) Sobald man ein in Ii ein Blatt erzeugt, bleibt dies ein Blatt in allenBumen Ii fr i> i. (Einmal ein Blatt, immer ein Blatt!)Denn, es gibt keine Regel fr das Entfernen von Bltternt = a c c a b a a c b a .

WS03/04

Vermeiden unntiger SchritteFolgerung:Blatt 1 wird in Phase 1 erstellt, daher gibt es in jeder Phase i + 1 eine Anfangssequenz von aufeinanderfolgenden Erweiterungen(angefangen bei Erweiterung 1) bei der Regel 1 oder Regel 2angewandt wird.

Sei ji die letzte Erweiterung in Phase i, die nach Regel 1 oder 2 erfolgt;d.h. jede Erweiterung j, mit j> ji , erfolgt nach Regel 3. Da jede Anwendung von Regel 2 ein neues Blatt erstellt, gilt nach Beobachtung 2: ji ji+1

Nicht alle Erweiterungen mssen explizit durchgefhrt werden!

WS03/04

Explizite ErweiterungenReihenfolge der expliziten Erweiterungen:

Phase 1: berechne Erweiterungen j1 = 1Phase 2: berechne Erweiterungen j1+ 1 ... j2Phase 3: berechne Erweiterungen j2 +1 ... j3....Phase i-1: berechne Erweiterungen ji-2 + 1... ji-1Phase i: berechne Erweiterungen ji-1 + 1... ji

In jeden zwei aufeinanderfolgenden Phasen gibt es hchstens einenIndex, der in beiden Phasen betrachtet werden muss, um die erforderlichen Erweiterungen durchzufhren.

WS03/04

Implizite ErweiterungenDer Algorithmus kann nun verbessert werden:

Die in Phase i+1 auszufhrenden Erweiterungen j fr j [1, ji]basieren alle auf Regel 1 und es wird nur konstante Zeitbentigt, um all diese Erweiterungen implizit durchzufhren.(Benutze globale Variable zur Markierung der aktuellen Textlnge!)

Falls j [ji +1, i+1] ist, sucht man das Ende des mit t[j...i] markierten Pfades und erweitert ihn mit dem Zeichen t[i+1] indem man Regel 2 oder 3 anwendet.Falls dabei Regel 3 angewandt wird setzt man nur ji+1 = j1 und beendet Phase i+1.

WS03/04

Beispiel fr implizite und exlpizite ErweiterungenBeispiel: Konstruktion des impliziten Suffix Baumes frt = pucupcupu

WS03/04

Struktur der Erweiterungs-Phasent = pucupcupu Suffixe, die zu einer Erweiterung nach Regel 2 fhren, sind mit * markiert

Unterstrichene Suffixe markieren die letzte Erweiterung nach Regel 2

Suffixe, die eine Phase beenden (erstmalige Anwendung von Regel 3) sind blau markiert.

i:0 1 2 3 4 5 6 7 8 9*ppupucpucupucuppucupcpucupcupucupcuppucupcupu*uucucuucupucupcucupcuucupcupucupcupu*ccucupcupccupcucupcupcupcupuu*upupcupcuupcupupcupup*pcpcupcuppcupuccucup*cupuuup*upuppuu

WS03/04

BeobachtungenSolange der Algorithmus explizite Erweiterungen ausfhrt, merkt man sich im Index j* den Index der gerade aktuell ausgefhrten expliziten Erweiterung. Im Verlaufe der Ausfhrung des Algorithmus nimmt j* niemals ab,sondern kann zwischen zwei aufeinanderfolgenden Phasen hchstens gleich bleiben.Da es nur m Phasen gibt (m = |t|), und j* durch m begrenzt ist, fhrtder Algorithmus daher nur 2m explizite Erweiterungen aus.

WS03/04

Ukkonens Algorithmus: VerbesserungRevidierte Pseudocode Formulierung von uuk:

Konstruiere Baum I1; j* = 1;for i = 1 to m 1 dobegin {Phase i+1}for j = j* +1 to i +1 do begin {Erweiterung j}Finde das Ende des Pfades von der Wurzel mit Markierung t[j ... i] im aktuellen Baum.Falls erforderlich, erweitere ihn durch Hinzufgung des Zeichens t[i+1], damit gewhrleistet wird, dass der String t[j...i+1] im Baum ist. j* = j; if Regel 3 wurde angewandt im Erweiterungsschritt jthen j* = j 1 und beende Phase i+1;end;end;

WS03/04

Nutzung von Suffix-LinksNutze Suffix-Links zur Beschleunigung des Schritts:

Finde das Ende des Pfades von der Wurzelmit Markierung t[j ... i] im aktuellen Baum Ii

Starte bei Knoten v, der t[j-1 i] = x? in Ii entspricht.Falls t[j-1 i] in einem inneren Knoten vendet, folge Suffix-Link zu s(v)!

WS03/04

Nutzung von Suffix-LinksSonst: Beginne beim kontrahierten Ort v von t[j-1 i], folge Suffix-Link und bestimme von dort aus t[j i], Falls neue innere Knoten erzeugt wurden, setzte Suffix-Links??xs(v)v

WS03/04

BeispielBeispiel: Konstruktion des impliziten Suffixbaums fr acacag.

WS03/04

Beispiel: Nutzung von Suffix-Linksacacgacacc.

WS03/04

AufwandsabschtzungMit der Hilfe von Suffix Links werden die Erweiterungen basierend auf Regel 2 oder Regel 3 vereinfacht.

Jede explizite Erweiterung kann in amortierister Zeit O(1) ausgefhrt werden (Begrndung: Folgt man Suffix-Links, so kann man insgesamt hchstens so oft im Baum hinaufsteigen, wie man hinabsteigen kann; das sind aber nur O(m) Niveaus!)

Weil nur 2m explizite Erweiterungen durchgefhrt werden, betrgt die Gesamtlaufzeit von Ukkonens Algorithmus O(m) (m = |t| ).

WS03/04

Echter Suffix BaumDer echte Suffix-Baum:

Der endgltige implizite Suffix Baum Im kann in einen wirklichen SuffixBaum in Zeit O(m) umgewandelt werden:

(1) Fge ein Terminalsymbol $ ans Ende vom String t ein

(2) Lasse Ukkonens Algorithmus mit diesem Zeichen weiterlaufen

Das Resultat ist der echte Suffix Baum in dem kein Suffix ein Prefixeines anderen Suffix ist und jedes Suffix in einem Blatt endet.

WS03/04