Suche in Texten: Suffix-Bäume Prof. Dr. S. Albers
Prof. Dr. Th. Ottmann
Naive Suffix-Baum-Konstruktion
In Ti haben alle Suffixe sufj , j < i bereits einen Ort.
headi = längstes Präfix von sufi, dessen erweiterter Ort in Ti-1 existiert.
Definition:
taili := sufi – headi, d.h. also sufi = headitaili.
taili .
x = erweiterter Ort
von headi+1 x v headi+1 taili+1 Ti+1 kann aus Ti wie folgt konstruiert werden:
1. Man bestimmt den erweiterten Ort von headi+1 in Ti und teilt die
letzte zu diesem Ort führende Kante in zwei neue Kanten auf durch Einfügen eines neuen Knotens.
2. Man schaffe ein neues Blatt als Ort für sufi+1
Naive Suffix-Baum-Konstruktion
Beispiel: = ababc babc c babc ababc abc ab T3 T2 head3 = ab
tail3 = c
Naive Suffix-Baum-Konstruktion
Algorithmus Suffix-Einfügen
Input: Der Baum Ti und der Suffix sufi+1
Output: Der Baum Ti+1
1 v := Wurzel von Ti
2 j := i
3 repeat
4 finde Sohn w von v mit w.u = j+1
5 k := w.u – 1;
6 while k < w.o and k+1 = j+1 do
7 k := k +1; j := j + 1
end while
Naive Suffix-Baum-Konstruktion
8 if k = w.o then v := w
9 until k
Der Algorithmus M
(Mc Creight, 1976)
Falls erweiterter Ort von headi+1 in Ti gefunden: Erzeugen eines neuen
Knotens und Aufspalten einer Kante O(1) Zeit.+
Idee: Erweiterter Ort von headi+1 wird in konstanter amortisierter Zeit in Ti bestimmt. (Zusatzinformation erforderlich!)
Analyse des Algorithmus M
Theorem 1
Algorithmus M liefert in Zeit O(| |) einen Suffix-Baum für
mit | | Blättern und höchstens | | - 1 inneren Knoten.
Suffix-Baum Anwendung
Verwendung von Suffix-Baum T:
1 Suche nach Zeichenkette : Folge dem Weg
mit Kantenbeschriftung in T in Zeit O(| |).
Blätter des Teilbaumes Vorkommen von
2 Suche längstes, doppelt auftretendes Wort:
Finde Ort eines Wortes mit größter gewichteter Tiefe,
der innerer Knoten ist.
3 Suche nach Präfix: Alle Vorkommen von Zeichenketten
mit Präfix finden sich in dem Teilbaum unterhalb
des „Ortes“ von in T.
Comments