Suchindex
zu einem Text für Suche nach verschiedenen Mustern
Eigenschaften:
1. Teilwortsuche in Zeit O(| |).
2. Anfragen an selbst, z.B.:
Längstes Teilwort von , das an mind. 2 Stellen auftritt.
3. Präfix-Suche: Alle Stellen in mit Präfix .
Eigenschaft von Suffix-Bäume
4. Bereichs-Suche: Alle Stellen in im Intervall [, ] mit lex , z.B.
abrakadabra, acacia [abc, acc],
abacus [abc, acc] .
5. Lineare Komplexität:
Speicherplatzbedarf und Konstruktionszeit O(| |)
Tries
Trie: Baum zur Repräsentation von Schlüsseln.
Alphabet , Menge S von Schlüsseln, S *
Schlüssel Zeichenkette aus *
Kante eines Tries T: Beschriftung mit einzelnen Zeichen aus
benachbarte Kanten: verschiedene Zeichen
Tries
a a a c b b c b b c c c Beispiel:
Tries
Blatt repräsentiert Schlüssel:
Entspricht Beschriftung der Kanten des Weges
von der Wurzel zu Blatt
! Schlüssel werden nicht in Knoten gespeichert !
Suffix-Tries
Trie für alle Suffixe eines Wortes
Beispiel: = ababc
Suffixe: ababc = suf1
babc = suf2
abc = suf3
bc = suf4
c = suf5 a a a c b b c b b c c c
Suffix-Tries
Innere Knoten eines Suffix-Tries = Teilwort von .
Jedes echte Teilwort von ist als innerer Knoten repräsentiert.
Sei = anbn : n2 + 2n + 1 verschied. Teilwörter = innere Knoten
Speicherplatzbedarf O(n2).
Suffix-Tries
a a a c b b c b b c c c 1. Zeichenkettensuche nach : Folge dem Weg
mit Kantenbeschriftung in T in Zeit O(| |).
Blätter des Teilbaumes Vorkommen von
2. Längstes, doppelt auftretendes Wort: Innerer
Knoten mit größter Tiefe, der mind. zwei
Söhne hat.
3. Präfix-Suche: alle Vorkommen von Zeichenketten
mit Präfix finden sich in dem Teilbaum unterhalb
des inneren Knotens von in T. Ein Suffix-Trie T erfüllt bereits einige der geforderten Eigenschaften:
Suffix-Bäume
a a a c b b c b b c c c ab abc abc b c c c Suffix-Baum = kontraktierter Suffix-Trie Suffix-Baum entsteht durch Kontraktion von unären Knoten aus
Suffix-Trie:
Interne Repräsentation von Suffix-Bäumen
ab abc abc b c c c T Beispiel: = ababc Sohn/Bruder-Repräsentation
Teilwort: Zahlenpaar (i,j)
Interne Repräsentation von Suffix-Bäumen
() (1,2) (2,2) (5,$) (3,$) (5,$) (3,$) (5,$) ab abc abc b c c c Beispiel = ababc Knoten v = (v.w, v.o, v.sn, v.br)
Weitere Zeiger (Suffix-Zeiger) kommen später hinzu
Eigenschaften von Suffix-Bäumen
(S1) Kein Suffix ist Präfix eines anderen Suffixes;
gilt, falls (letztes Zeichen von ) = $
Suche:
(T1) Kante nichtleeres Teilwort von .
(T2) Benachbarte Kanten: zugeordnete Teilworte beginnen
mit verschiedenen Zeichen.
Eigenschaften von Suffix-Bäumen
Größe
(T3) Innerer Knoten ( Wurzel): mind. zwei Söhne.
(T4) Blatt (nicht-leeres ) Suffix von .
Sei n = | | 1
Konstruktion von Suffix-Bäumen
ab abc abc b c c c T Definition:
partieller Weg: Weg von der Wurzel zu einem Knoten von T
Weg: Ein partieller Weg, der bei einem Blatt endet.
Ort einer Zeichenkette : Knoten am Ende des mit
beschrifteten partiellen Weges (falls er existiert).
Konstruktion von Suffix-Bäumen
ab abc abc b c c c T Erweiterung einer Zeichenkette : Zeichenkette mit Präfix
erweiterter Ort einer Zeichenkette : Ort der kürzesten Erweiterung
von , deren Ort definiert ist.
kontraktierter Ort einer Zeichenkette : Ort des längsten Präfixes von
, dessen Ort definiert ist.
Konstruktion von Suffix-Bäumen
Definitionen:
sufi: an Position i beginnendes Suffix von , also z.B.
suf1 = , sufn = $.
headi : längstes Präfix von sufi , das auch Präfix von sufj für
ein j < i ist.
Beispiel: = bbabaabc = baa (hat keinen Ort)
suf4 = baabc
head4 = ba
Konstruktion von Suffix-Bäumen
a abc abc c b aabc b baabc a c babaabc c = bbabaabc
Naive Suffix-Baum-Konstruktion
Beginne mit dem leeren Baum T0
Der Baum Ti+1 entsteht aus Ti durch Einfügen des Suffixes sufi+1.
Algorithmus Suffix-Baum
Input: Eine Zeichenkette
Output: Der Suffix-Baum T von
1 n := | |; T0 := ;
2 for i := 0 to n – 1do
3 füge sufi+1 in Ti ein, dies sei Ti+1 ;
4 end for
Comments