Referat zum Bau von Suffix Baeumen

Referat zum Bau von Suffix Baeumen

Autoren:

Hanna Kraeusel

Axel Block

Magnus Brockschmidt

Prozeduraler Algorithmus

Konstruiere T1;

for (i=1; i<m; i++) {

/*Beginn von Phase i+1 */


Konstruiere T1;

for (i=1; i<m; i++) {

/*Beginn von Phase i+1 */

for (j=1; j<=j+1;j++) {

/*Beginn von der j-ten Erweiterung*/


Konstruiere T1;for (i=1; i<m; i++) {/*Beginn von Phase i+1 */ for (j=1; j<=i+1;j++) {

/*Beginn von der j-ten Erweiterung*/Finde das Ende des Pfades mit Label S[j..i];

Falls noetig, erweitere den Pfad durch S[i+1]; }}

Erweiterungsregeln

1. ß endet in einem Blatt. Dann füge [i+1] zum Kantenlabel hinzu.

Erweiterungsregeln


2. Es gibt keinen Pfad am Ende von ß, der mit S[i+1] weitergeht, aber mindestens ein anderer Pfad geht weiter. Dann füge eine neue Kante mit Label S[i+1] ein. Dazu muß ein neuer Knoten erzeugt werden, wenn ß mitten in einer Kante endet. Gib dem neuen Blatt Nummer j.

Erweiterungsregeln


2. Es gibt keinen Pfad am Ende von ß, der mit S[i+1] weitergeht, aber mindestens ein anderer Pfad geht weiter. Dann füge eine neue Kante mit Label S[i+1] ein. Dazu muß ein neuer Knoten erzeugt werden, wenn ß mitten in einer Kante endet. Gib dem neuen Blatt Nummer j.

3. Es gibt einen Pfad am Ende von ß, der mit S[i+1] weitergeht. In diesem Fall ist ßS[i+1] schon im Baum und wir tun nichts.

Beispiel: Wir wollen den Suffix Baum des Strings abcabcabacdba

erzeugen.

Um den Baum zu bilden, muss in der Phase i der Baum Bi

in den Baum Bi+1 umgewandelt werden.

Wir beschreiben jede Phase und zeichnen den Baum immer,wenn die Phase beendet ist.

Einfügen von aGesamter String: a

aEs ist nur a Einzufügen!(Regel 2)

Einfügen von bGesamter String: ab

ab

In der ersten Erweiterung fügen wir ein b an das vorhandene Blatt an. (Regel 1)


a bb

In der ersten Erweiterung fügen wir ein b an das vorhandene Blatt an. (Regel 1) Die zweite Erweiterung konstruiert einen neuen Ast mit der Bezeichnungb. (Regel 2)


a bb

In der ersten Erweiterung fügen wir ein b an das vorhandene Blatt an. (Regel 1) Die zweite Erweiterung konstruiert einen neuen Ast mit der Bezeichnungb. (Regel 2)

Jetzt stehen alle Suffixe des Strings ab im Baum.

Einfügen von cGesamter String: abc

a b cb cc

In den ersten beiden Erweiterungenfügen wir ein c an die vorhandenen Blätter an. Die dritte Erweiterung konstruiert einen neuen Ast mit der Bezeichnungc. Jetzt sind alle Suffixe von abc im Baumenthalten.

Einfügen von aGesamter String: abca

a b cb c ac aa

In den ersten drei Erweiterungen fügen wir ein a an die vorhandenen Blätter an. Die vierte Erweiterung muss keinen neuen Ast kreieren, da a bereits Als Präfix von abca vorhanden ist. (Regel 3) Jetzt sind alle Suffixe von abca im Baumenthalten.

Einfügen von bGesamter String: abcab

a b cb c ac a ba bb

Diese Phase ist synchron zur vorherigenPhase.

Einfügen von cGesamter String: abcabc

a b cb c ac a ba b cb cc

Auch hier ist nichts anderes zu tun.Man erkennt, dass der Suffix Baum keine weiteren Äste hinzufügt, wenn die neuen Character nur Teilstrings des gesamten Strings bilden.

Einfügen von aGesamter String: abcabca

a b cb c ac a ba b cb c ac aa

Nur anhängen von a an die vorhandenen Äste nötig!

Einfügen von bGesamter String: abcabcab

a b cb c ac a ba b cb c ac a ba bb

Jetzt wird noch b an die vorhandenen Äste angefügt!

Einfügen von aGesamter String: abcabcaba

a b cb c ac a ba b cb c ac a ba b ab aa

Erweiterung 1 bis 3: Wie zuvor auch fuegen wir ein aan alle Aeste an.


a b cb c ac a ba b cb c ac a a ba b ab aa

Erweiterung 4: Jetzt muss der String abcaba gefunden werden. Von der Wurzel laufen wir abcab runter und fuegen ein a an.



Erweiterung 4: Jetzt muss der String abcaba gefunden werden. Von der Wurzel laufen wir abcab runter und fuegen ein a an.


a b cb c a ac a a ba b c ab c a ac a a ba b ab aa

Einfügen von cGesamter String: abcabcabac

a b cb c c a ac a a c ba c b c ab c a a cc a a c ba c b ab a ca cc

Einfügen von dGesamter String: abcabcabacd

a b c db c c a a dc a d a c ba c b d c ab d c a a cc a a c b da c b d ab d a ca c dc dd

Einfügen von bGesamter String: abcabcabacdb

a b c db c c a a d bc a d a c b ba c b b d c ab d c a b a cc a b a c b da c b d a bb d a b ca b c dc d bd bb

Einfügen von aGesamter String: abcabcabacdba

a b c db c c a a d bc a d a c b b aa c b b d c a ab d a c a b a cc a b a c a b da c a b d a bb d a b c aa b c a dc a d bd b ab aa

Definition von Suffix Links

• Knoten v hat die Beschriftung x (wobei x ein einzelner Character sei).

ist möglicherweise leer.




• Knoten s(v) hat die Beschriftung




• Knoten s(v) hat die Beschriftung

• Jetzt heißt die Kante v s(v) ein

Suffix-Link.

Gibt es für jeden Knoten v ein Suffix Link zu s(v)?

Beobachtung

Wenn der Knoten v als neuer innerer Knoten während der Verarbeitung von Erweiterung j in Phase i durch den bisherigen Algorithmus eingesetzt wird, und wenn v die Markierung x trägt, dann gilt eine der beiden Aussagen:

1. Der Weg mit Beschriftung endet in einem bereits vorhandenen inneren Knoten w = s(v).

2. Ein neuer Knoten s(v) wird bei der Verarbeitung von Extension j+1 in Phase i angelegt und s(v) hat als Beschriftung.

Beweis

• Das Hinzufügen eines Knoten v kann nur in der Erweiterungsregel 2 passiert sein.

• Dann gibt es, neben der Verbindung zum neuen Blatt, auch einen weiteren von v ausgehenden Weg, der den Buchstaben y als ersten besitzen möge.

Es treten zwei Fälle auf

Fall1:Der gegenwärtige Baum besitzt neben xy einen weiteren Weg von der Wurzel beginnend mit der Beschriftung xz, wobei z ein beliebiger String aus dem Suffix sei, und z y.

• Jetzt gibt es Suffixe mit den Präfixen xy und xz, also auch mit y und z. Deswegen besitzt der Baum einen Knoten s(v) mit der Beschriftung .

• Fall2: Der gegenwärtige Baum besitzt keinen weiteren Weg wie in Fall1, dann wird in der Verarbeitung von S(j+1..i) ein neuer innerer Knoten s(v) angelegt, der die Beschriftung hat, weil es Suffixe mit den Präfixen y und S(i+1) gibt.

Lemma

• Bei Ukkonens Algorithmus hat jeder implizite Suffix Baum für jeden neuen inneren Knoten einen Suffix Link nach dem Ende der nächsten Erweiterung.

Beweis

• Der Beweis dieses Lemmas ist induktiv.

• Sie ist wahr für B1, weil B1 noch keine Knoten

besitzt. • Da in der letzten Erweiterung einer Phase keine

neuen Knoten eingefügt werden, denn in dieser Phase ist der zu behandelnde String nur ein einzelner Character, sind am Ende der Phase i alle Knoten mit Suffix Links belegt und zu Beginn der Phase i+1 gilt ebenfalls die Aussage.

Single extension algorithm (SEA)

Begin

• Finde Knoten v über dem Ende von S[j-1..i].

Laufe eine Kante vom Ende von S[j-1..i] hoch.

Sei nun y der String zwischen dem Ende von S[j-1..i] und v.


Begin

• Finde Knoten v über dem Ende von S[j-1..i].

Laufe eine Kante vom Ende von S[j-1..i] hoch.

Sei nun y der String zwischen dem Ende von S[j-1..i] und v.

• Wenn v nicht die Wurzel ist, gehe den Suffix Link entlang nach s(v). Klettere den Baum herunter an dem Ast des Strings y. Wenn v die Wurzel ist, folge S[j..i] von der Wurzel.


Begin• Finde Knoten v über dem Ende von S[j-1..i]. Laufe eine Kante vom Ende von S[j-1..i] hoch. Sei nun y der String zwischen dem Ende von S[j-1..i] und

v. • Wenn v nicht die Wurzel ist, gehe den Suffix Link entlang

nach s(v). Klettere den Baum herunter an dem Ast des Strings y. Wenn v die Wurzel ist, folge S[j..i] von der Wurzel.

• Sorge gemäss den Erweiterungsregeln dafür, dass der String S[j..i]S(i+1) im Baum enthalten ist.


Begin• Finde Knoten v über dem Ende von S[j-1..i]. Laufe eine Kante vom Ende von S[j-1..i] hoch. Sei nun y der String zwischen dem Ende von S[j-1..i] und v. • Wenn v nicht die Wurzel ist, gehe den Suffix Link entlang nach s(v).

Klettere den Baum herunter an dem Ast des Strings y. Wenn v die Wurzel ist, folge S[j..i] von der Wurzel.

• Sorge gemäss den Erweiterungsregeln dafür, dass der String S[j..i]S(i+1) im Baum enthalten ist.

• Wenn in Erweiterung j-1 ( nach Erweiterungsregel 2) ein Knoten w erzeugt wurde, dann muss der String das Ende des Suffix Links s(w) sein. Erzeuge einen Link (w,s(w)) von w nach s(w).

End.

Beispiel: Wir wollen den Suffix Baum des Strings abcabcabacdb

mit Hilfe von Suffixlinks erzeugen.

Um den Baum zu bilden, muss in der Phase i der Baum Bi

in den Baum Bi+1 umgewandelt werden.

Einfügen von aGesamter String: a

aEs ist nur a Einzufügen!

In den ersten Phasen sind dieSuffix Links noch nicht wichtig, da noch keine Knoten vorhanden Sind.


ab

In der ersten Erweiterung fügen wir ein b an das vorhandene Blatt an.


a bb

In der ersten Erweiterung fügen wir ein b an das vorhandene Blatt an. Die zweite Erweiterung konstruiert einen neuen Ast mit der Bezeichnungb.


a bb

In der ersten Erweiterung fügen wir ein b an das vorhandene Blatt an. Die zweite Erweiterung konstruiert einen neuen Ast mit der Bezeichnungb.

Jetzt stehen alle Suffixe des Strings ab im Baum.

Einfügen von cGesamter String: abc

a b cb cc

In den ersten beiden Erweiterungenfügen wir ein c an die vorhandenen Blätter an. Die dritte Erweiterung konstruiert einen neuen Ast mit der Bezeichnungc. Jetzt sind alle Suffixe von abc im Baumenthalten.

Einfügen von aGesamter String: abca

a b cb c ac aa

In den ersten drei Erweiterungen fügen wir ein a an die vorhandenen Blätter an. Die vierte Erweiterung muss keinen neuen Ast kreieren, da a bereits Als Präfix von abca vorhanden ist. Jetzt sind alle Suffixe von abca im Baumenthalten.

Einfügen von bGesamter String: abcab

a b cb c ac a ba bb

Diese Phase ist synchron zur vorherigenPhase.

Einfügen von cGesamter String: abcabc

a b cb c ac a ba b cb cc

Auch hier ist nichts anderes zu tun.Man erkennt, dass der Suffix Baum keine weiteren Äste hinzufügt, wenn die neuen Character nur Teilstrings des gesamten Strings bilden.

Einfügen von aGesamter String: abcabca

a b cb c ac a ba b cb c ac aa

Nur anhängen von a an die vorhandenen Äste nötig!

Einfügen von bGesamter String: abcabcab

a b cb c ac a ba b cb c ac a ba bb

Jetzt wird noch b an die vorhandenen Äste angefügt!


a b cb c ac a ba b cb c ac a ba b ab aa

Erweiterung 1 bis 3: Wie zuvor auch fuegen wir ein aan alle Aeste an.

In dieser Phasekommen die Suffix Linkserst richtig insSpiel.



Erweiterung 4: Jetzt muss der String abcaba eingefuegt werden. Von der Wurzel laufen wir abcab runter und fuegen ein a an.

Diese Erweiterungerzeugt einen Knoten,der noch keinen Suffix Link hat, aber wir wissen, dass dieser in der naechsten Erweiterunghinzugefuegt wird.


a b cb c ac a ba b cb c a ac a a ba b ab aa

Erweiterung 5: Jetzt muss der String bcaba eingefuegt werden. Von der Wurzel laufen wir bcab runter und fuegen ein a an.

Diese Erweiterungerzeugt einen Suffix Link.

Der neue Knoten ist allerdingsnoch nicht weiterverlinkt,was wieder in der naechstenErweiterung passierenwird.


a b cb c ac a ba b c ab c a ac a a ba b ab aa

Erweiterung 6: Jetzt muss der String caba eingefuegt werden. Von der Wurzel laufen wir cab runter und fuegen ein a an.

Diese Erweiterungerzeugt wie zuvoreinen Suffix Link.


a b cb c ac a a ba b c ab c a ac a a ba b ab aa

Erweiterung 7: Jetzt muss der String aba eingefuegt werden. Von der Wurzel laufen wir ab runter und fuegen ein a an.




Erweiterung 8: Jetzt muss der String ba eingefuegt werden. Von der Wurzel laufen wir b runter und fuegen ein a an.


Der Suffix Link des neuen Knotensfuehrt zur Wurzel,da b nur noch eineinzelner Characterist und α ist in diesem Fall einleerer String.



Erweiterung 9: Jetzt muss lediglich noch der Character a eingefuegt werden. Dieser ist allerdings schon vorhanden.



Unser Baum ist jetzt vollstaendig verlinkt und die Phase ist beendet.


a b cb c a ac a a ba b c ab c a ac a a ba b ab aac

Erweiterung 1: Die erste Erweiterung ist immer speziell. Wir muessen den String abcabcabac einfuegen.

Wir wissen, dass abcabcabader laengste String im Baum ist. Wir laufen diesen runterund fuegen dort ein c an.


a b cb c a ac a a ba b c ab c a ac a a ba b ab aa cc

Erweiterung 2:Wir muessen den String bcabcabac einfuegen. Wir nutzen den Suffix Link.

Wir wissen, dass der ersteKnoten ueber dem laengstenString im Baum ein Suffix linkhat. Wir laufen vom laengstenBlatt hoch bis zum besagten

Suffix Link.Von da gehen wirdie gleiche Bezeichnug

wieder runterund fuegendort ein c an.


a b cb c a ac a a ba b c ab c a ac a a ba b ab a ca cc

Erweiterung 3:Wir muessen den String cabcabac einfuegen. Wir nutzen wieder den Suffix Link.

Wir laufen von der Position,wo wir in Erweiterung 2 das c eingefuegt haben, hoch biszu dem Suffix link.Von da gehen wir die gleiche

Bezeichnug wieder runter, die

wir hochgegangensind, und fuegendort ein c an.


a b cb c a ac a a ba b c ab c a ac a a ba c b ab a ca cc

Erweiterung 4:Wir muessen den String abcabac einfuegen. Wir nutzen den zustaendigen Suffix Link.

Wir laufen von der Position,wo wir in Erweiterung 3 das c eingefuegt haben, hoch biszu dem Suffix link.Von da gehen wir die gleiche

Bezeichnug wieder runter, die

wir hochgegangensind, und fuegendort ein c an.


a b cb c a ac a a ba b c ab c a ac a a c ba c b ab a ca cc

Erweiterung 5: Wir muessen den String bcabac einfuegen.Jetzt nehmen wir den ersten Suffix Link.

Wir laufen von der Position,wo wir in Erweiterung 4 das c eingefuegt haben, hoch biszu dem ersten Suffix link.Von da gehen wir das a

runter, das wir auch hochgegangensind, und fuegendort ein c an.


a b cb c a ac a a ba b c ab c a a cc a a c ba c b ab a ca cc

Erweiterung 6: Wir muessen den String cabac einfuegen.Dies passiert wie in Erweiterung 5.

Wir laufen von der Position,wo wir in Erweiterung 5 das c eingefuegt haben, hoch biszu dem ersten Suffix link.Von da gehen wir das a

runter, das wir auch hochgegangensind, und fuegendort ein c an.


a b cb c a ac a a c ba c b c ab c a a cc a a c ba c b ab a ca cc

Erweiterung 7 und 8: Wir muessen den String abac und bac einfuegen.Diese Vorgaenge sind ebenfalls wie in Erweiterung 5.

Wir laufen von der Position,wo wir in der vorherigen Erweiterung das c eingefuegthaben, hoch bis zu dem ersten Suffix link.

Von da gehen wir das a runter,das wir auch hochgegangensind, und fuegendort ein c an.



Erweiterung 9: Wir muessen den String ac einfuegen.

Wir laufen von der Position,wo wir in der vorherigen Erweiterung das c eingefuegthaben, hoch bis zu dem ersten Suffix link, hier die Wurzel.

Von da gehen wir das a runter,das wir auch hochgegangensind, und fuegendort einen neuenAst fuer das c an.

Es entsteht ein neuer Suffix Link zur Wurzel.



Erweiterung 10: Wir muessen den String c einfuegen. Dieser existiert allerdings bereits als Praefix im Baum.



Phase ist beendet und der Baum ist vollstaendig verlinket.


a b cb c c a ac a a c ba c b c ab c a a cc a a c ba c b ab a ca ccd Erweiterung 1: abcabcabacd muss eingefuegt werden.

Es geht ebenso wie in der Phase zuvor!

Der gesuchte String ist der Laengste. Wir fuegen d einund merken uns die Position.


a b cb c c a ac a a c ba c b c ab c a a cc a a c ba c b ab a ca cc dd Erweiterung 2: bcabcabacd muss eingefuegt werden.

Es geht ebenso wie in der Phase zuvor!

Von der gemerkten Position gehen wir bis zum Suffix Linkhoch, diesen entlang und an derStelle die gleiche Bezeichnung

wieder herunter!


a b cb c c a ac a a c ba c b c ab c a a cc a a c ba c b d ab d a ca c dc dd Erweiterung 3-5: cabcabacd, abcabacd, bcabacd

mussen eingefuegt werden.

Von der gemerkten Position gehen wir jeweils bis zum Suffix Link hoch, diesen entlang und an der Stelle die

gleiche Bezeichnung wieder herunter! Wir nutzen fuer diese drei Schritte die markierten Linksund fuegen die gelben d’s ein.


a b cb c c a ac a d a c ba c b d c ab d c a a cc a a c b da c b d ab d a ca c dc dd Erweiterung 6-9: cabacd, abacd, bacd, acd

mussen eingefuegt werden.

Von der gemerkten Position gehen wir jeweils bis zum Suffix Link hoch, diesen entlang und an der Stelle die

gleiche Bezeichnung wieder herunter! Wir nutzen fuer diese drei Schritte die markierten Linksund fuegen die gelben d’s ein.


a b cb c c a a dc a d a c ba c b d c ab d c a a cc a a c b da c b d ab d a ca c dc dd Erweiterung 9: cd muss eingefuegt werden.

Jetzt gehen wir ueber den Suffixlink zur Wurzel, laufen ein c wieder runter, weil wirdas auch hochgelaufensind, und fuegen einenneuen Ast fuer das d ein.

Es entsteht ein neuerSuffix Link zur Wurzel.


a b c db c c a a dc a d a c ba c b d c ab d c a a cc a a c b da c b d ab d a ca c dc dd Erweiterung 11:d muss eingefuegt werden.

Jetzt gehen wir ueber Den neuen Suffixlink zur Wurzel, laufen ein c wieder runter, weil wirdas auch hochgelaufensind, und fuegen einenneuen Ast fuer das d ein.


a b c db c c a a dc a d a c ba c b d c ab d c a a cc a a c b da c b d ab d a ca c dc dd

Die Phase ist beendet und der Baum vollstaendig verlinkt.

Einfügen von bGesamter String: abcabcabacdb

a b c db c c a a d bc a d a c b ba c b b d c ab d c a b a cc a b a c b da c b d a bb d a b ca b c dc d bd bb Nach der letzten Phase erhalten wir diesen Baum.

Trick Nr. 1 Skip/Count Trick

Wir befinden uns an einem Knoten v, und das nun zu erweiternde Suffix hat ein Praefix, welches auf abcdefgh endet.

Sinn:

In Phase zwei vom Knoten s(v) dem Label y folgen erfordert eine Zeit t ~ Laenge von y |y|.

Der Skip/Count Trick reduziert t auf t ~ Anzahl der Knoten in y.

Trick 1

• Der Trick ist sehr simpel: Wenn am Knoten s(v) angekommen, suche den Weg aus dem Knoten, welcher mit dem Anfangsbuchstaben von y beginnt. Wenn y länger ist als der String an dieser Kante bis zum nächsten Knoten, so springe zum nächsten Knoten. Setze einen Index auf den |String| + 1. Nun schaue, welche Kante aus diesem Knoten mit dem |String| + 1 Buchstaben aus y beginnt und springe zum nächsten Knoten usw. Dieses "Springen" endet, wenn der String an der folgenden Kante länger oder gleich der Länge von y ist. Dann ist nämlich das Ende von y erreicht und nun wird die entsprechende Extension Rule angewendet.

• Also: Man guckt einfach nach dem Weg, zählt und springt einen Knoten weiter oder zum Ende.

• Aber was ist mit dem Worst Case?

Suffix Linka

b

c

d

e

f

g

h

i

j

v S(v)

String y

Dem Suffix Link von v nach s(v) folgen, dann soll es den String y = abcdefgh heruntergehen, um an dessen Ende ein Zeichen anzuhaengen. Der naïve Algorithmus wuerde Zeichen fuer

Zeichen ablaufen. G ist hier die Laenge des restlichen abzulaufenden Teils von y, I der Index des naechsten

Zeichens.

G = |y| = 8,

I = 1,

Suffix Linka

b

c

d

e

f

g

h

i

j

v S(v)

String y

Wir suchen den Buchstaben an diesem Knoten, mit dem y beginnt, also a, gucken, ob an dieser Kante mehr Buchstaben stehen als y lang ist, hier abcd, also kuerzer, somit springen

wir zum naechsten Knoten. Wenn y kuerzer ist als der String an dieser Kante, waere das Ende von y erreicht, und wir koennten anfuegen.

Nun springen wir direkt zu diesem Knoten

x

z

g

G = |y| = 8,

I = 1,

Aktuelle Position

Suffix Linka

b

c

d

e

f

g

h

i

j

v S(v)

String y

Nun sind wir an dem Knoten. Wir haben 4 Zeichen uebersprungen, also wird G auf G-4 gesetzt und I auf 1+4. Dann gehts weiter, nach der Kante mit dem 5ten Zeichen von y

suchen und zum naechsten Knoten springen.

Nun springen wir weiter zu diesem Knoten

x

z

g

G = G-4 = 4,

I = I+4 = 5,

Aktuelle Position

Suffix Linka

b

c

d

e

f

g

h

i

j

v S(v)

String y

Die Laenge des Strings an der naechsten Kante, die mit dem 7ten Zeichen von y beginnt ist groesser als die Laenge des Restes von y. Das Ende von y liegt also an dieser Kante.

Aktuelle Position.

x

z

g

G = G-2 = 2,

I = I+2 = 7

Ende von y

Suffix Linka

b

c

d

e

f

g

h

i

j

v S(v)

String y

Wir haben nun das Ende von y gefunden und koennen das Zeichen, z.B. ein w einfuegen.

Hier findet sich das Ende von y, und das Zeichen kann eingefuegt werden.

x

z

g

Suffix Linka

b

c

d

e

f

g

h

i

j

v S(v)

String y

W eingefuegt, es geht weiter mit der naechsten Extension.

Hier findet sich nun ein neuer Knoten und ein Ast mit Label w.

x

z

g

w

Definition

Die Tiefe (Knotentiefe) eines Knotens ist die Anzahl der Knoten auf dem Pfad von der Wurzel bis zu diesem Knoten.

Lemma

Es sei (v, s(v)) irgendein Suffix Link. Dann ist die Knotentiefe von v hoechstens um 1 groesser als die von s(v).

Beweis

• Jeder interne Vorfahr von v mit Label xbeta hat einen Link zu einem Knoten mit Label beta.

• xbeta ist ein Präfix des Pfades zu v, so ist beta ein Präfix des Pfades zu s(v)

• --> Jeder Link von einem internen Vorfahr von v geht zu einem internen Vorfahr von s(v).

• Und wenn beta nicht leer ist, so ist der Knoten mit dem Label beta ein interner Knoten. Da die Tiefen zweier Vorfahren von v verschieden sein muessen, hat jeder Vorfahr von v einen Link zu einem anderen Vorfahren von s(v).

• -->Die Tiefe von s(v) ist mindestens 1 (Wurzel) + die Anzahl interner Vorfahren von v mit längerer Bezeichnung als einem Zeichen.

• Den einzigen Vorfahren ohne Gegenstück, den v haben kann, ist der mit nur einem Zeichen, und nur dann ist die Tiefe von v auch nur 1 groesser als die von s(v).

D A C F A L B A L D A C T A L D A C F A L B NA

L

D A C F A L B A L D A C T A L D A C F A L B N

C F A L B A L D A C T A L D A C F A L B N

L D A C F A L B A L D A C T A L D A C F A L B N

N

N

N

N

Ausschnitt aus dem Suffixbaum fuer den String ALDACFALBALDACTALDACFALBN, ohne Links.


L




N

N

N

N

Bei diesen Links ist die Tiefe von v um 1 groesser als die Tiefe von s(v).

vv v

S(v) S(v) S(v)


L




N

N

N

N

Bei diesen Links ist die Tiefe von v um 1 kleiner als die Tiefe von s(v).

v v

S(v) S(v)

Definition

• Die aktuelle Knotentiefe ist die des zuletzt besuchten Knotens.

Behauptung

Mit diesem Trick dauert jede Phase des Algorithmus O(m).

Beweis

• Es gibt höchstens m Extensions in einer Phase. In einer davon es geht höchstens einen Knoten hoch zum nächsten Link, den Link entlang, die Knoten herunter und die Regeln ausführen, evtl auch Link setzen. Wir wissen, daß alles ausser dem Knoten abwärts gehen konstante Zeit benoetigt. Dieses untersuchen wir anhand der Tiefeveränderung in einer Phase.

• Einen hoch, der Suffix Link erhöht höchstens weiter um einen, es geht also höchstens zwei rauf, also insgesamt höchstens 2m rauf. Da der Baum aber höchstens m Knoten haben kann, geht es auf die Phase gesehen höchstens 3m herunter. Es gibt also höchstens 3m downwalks, --> O(m)

Corollar

Es gibt m Phasen mit O(m), also insgesamt O(m*m).

Das ist sehr grob gerechnet und sieht schlecht aus, aber mit ein paar kleinen weiteren Details erreichen wir O(m).

Ersetzen der Zeichen durch Indices

Durch die Zeichen an den Kanten nimmt der Baum sehr viel Platz weg. Diese werden nun durch Indices ersetzt, die Anfang und Ende des Teilstrings im Gesamtstring markieren.

Der Auschnitt aus dem Baum, dieses mal mit Indices.

A L D A C F A L B A L D A C T A L D A C F A L B N

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

2 - 2 3 - 5 6 - 10 11 - 25

11 - 25

11 - 25

11 - 25

6 - 10

6 - 10

6 - 10

25 - 25

25 - 25

25 - 25

25 - 25

1-1

2-2

3 - 3

3 - 5

Single Phase Algorithm(SPA)

1. Setze e auf i+1.

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

3. Setze ji+1 auf j*-1 und gehe zur nächsten Phase.

Documents

Referat zum Bau von Suffix Baeumen