Suffix Tree Flashcards
Was ist die String-Tiefe und was die Baum-Tiefe?
String-Tiefe
- Anzahl Buchstaben bis zum Knoten
Baum-Tiefe
- Anzahl der Kanten bis zum Knoten
Was ist ein Generalisierter Suffix-Baum?
Ein Suffix-Baum über mehrere Strings
Was ist das Suffix Array SA[s] Was kann man damit machen?
SA(s) bezeiche das Suffix-Array für den String s. SA(s) hat genau |s| Einträge, je einen für jedes Suffix von s Die Einträge in SA(s) sind in lexikographischer Reihenfolge der Suffixe geordnet.
ALSO: Sortiere die Suffixe in lexigraphischer Reihenfolge –> erst anfangs Buchstaben alphabetisch dann 2 Buchstaben alphabetisch bis neuer 1. Anfangsbuchstabe usw. https://www.youtube.com/watch?v=uxA__b23t2w + https://www.youtube.com/watch?v=x6j44AtzFmU
Pattern Matching -> Binäre suche!
Suffix-tree aufstellen
Was ist das LCP?
Longest Common Prefix:
Das LCP-Array gibt an wie viel Übereinstimmung (von vorne kommend in Buchstaben gemessen) 2 aufeinanderfolgende Suffixe haben!
LCP-Array enthält Stringtiefe des tiefsten gemeinsamen Vorgängers
Wie kann Pattern matching erfolgen? Wieviele Möglichkeiten gibt es?
Wie kann man das Patternmatching mit dem Suffix Array verkürzen?
2 Möglichkeiten:
- Über Suffix-Tree:
- –> gib das Pattern oben in den Baum (aka die Wurzel) –>
- Hast du es gefunden, dann gehe zu den darunter liegenden Blättern (ggf. nur ein Blatt) des darunter liegenden Teilbaums –>
- Die Indexe der Blätter geben die Anfangsposition der Matches an!
- Suffix Array und LCP (Binäre Suche) https://www.youtube.com/watch?v=x6j44AtzFmU
- Idee: Da das Suffix-Array lexikographisch sortiert, stehen die Positionen aller Matches darin unmittelbar hintereinander. Pattern soll in String vorkommen
- -> S1: Also Grenzen des Intervalls des Strings setzten _ 1. und letzter Buchsabe/ $ fällt weg, da nicht von Interesse!
- Wenn kein Treffer: Mitte nehmen und checken,
- wenn Mitte kein Treffer, dann neue Grenze auf Mitte setzen (Ob linker Rand oder rechter Rand entscheiden, wo unser Pattern gemäß den vorherigen angescheuten strings einzuordnen ist)
- wenn Treffer: dann die Nachbarn absuchen
- F39 https://www.youtube.com/watch?v=UrmjCSM7wDw https://youtu.be/RNtLxlLFtvk?t=1h12m50s
- Verkürzen mit dem LCP-Array Nachbessern
Algorithmus zum Pattern Matching mit Suffix-Array: Laufzeit bisher: O(|P|·log |s|), log |s| Vergleiche von Präfixen für binäre Suche, mit jeweils maximal |P| Zeichen-Vergleichen. (P ist das Pattern.)
Idee: Reduktion der Zeichen-Vergleiche durch Verwendung von LCP-Informationen, so dass Vergleich von Präfixen nicht mit erstem Zeichen beginnen muss.
LCP-Array enthält Stringtiefe des tiefsten gemeinsamen Vorgängers
Laufzeit lässt sich so auf O(|P| + log |s|) reduzieren. (Auf Beweis wird hier verzichtet.)
[mP] Wie viele Blätter hat ein Suffix-Baum über einem String s? und was sind innere knoten?
Er hat so viele Blattknoten wie eben Suffixe im dokument vorhanden sind!
Innere Knoten treten immer dann auf, wenn es eben 2 suffixe gibt, die gleich beginnen, aber dann unterschiedlich weitergeht
[mP] Welche Komplexität hat McCreight-Algorithmus zum Aufbau eines Suffix-Baumes über einem String s?
O(n2)
[mP] Wie läßt sich die Komplexität des McCreight-Algorithmus senken?
Mit Verweisen glaub ich! (korrekt)
Laufzeit: O(n²)
Laufzeit mit Suffixverweisen O(n) hier nicht behandelt
https://youtu.be/RNtLxlLFtvk?t=1h20m57s –> mit Patternmatching über Suffix Array + LCP?!
Laufzeit bisher: O(|P|·log |s|), log |s| Vergleiche von Präfixen für binäre Suche, mit jeweils maximal |P| Zeichen-Vergleichen. (P ist das Pattern.)
Idee: Reduktion der Zeichen-Vergleiche durch Verwendung von LCP-Informationen, so dass Vergleich von Präfixen nicht mit erstem Zeichen beginnen muss. Laufzeit lässt sich so auf O(|P| + log |s|) reduzieren. Also auf Länge des Patterns (P)und Tiefe des Suchverfahrens (log s)
[mP] Zeigen Sie: In einem Suffix-Array benachbarte Suffix-Paare haben ein längeres gemeinsames Präfix als alle anderen denkbaren Suffix-Paare.
ad
[mP] Konstruieren Sie den Suffix-Baum über einem String, z. B. ananas$
ad
Wie sind die Suchkosten beim Interval Matching vom Suffix Array
Wie lassen sich die Suchkosten reduzieren?
O( |P| * log |s|) –> Kosten fürs nach unten steigen mit log|s| und an jeder Stelle maximal |P| Vergleiche (Zahl der Vergleiche, die wir machen müssen bei Binärer Suche ist logarithmisch)
|P| = Länge des Patterns ⇒ Anzahl der Zeichenvergleiche
|s| = Anzahl der Suffixe im Dokument (wie oft wir nach unten steigen müssen = länge des Suchverfahrens)
Idee: Reduktion der Zeichen-Vergleiche durch Verwendung von LCP-Informationen, so dass Vergleich von Präfixen nicht mit erstem Zeichen beginnen muss.
Laufzeit lässt sich so auf O(|P| + log |s|) reduzieren.
Was ist ein Suffix-tree? und wozu braut man sie?
- ST(s) bezeichne den Suffix-Baum für den String s.
- ST(s) hat genau |s| Blätter, beschriftet mit 1…|s|, je eines für jedes Suffix von s.
- Jeder innere Knoten von ST hat mindestens zwei Kinder.
- Jede Kante in ST ist mit einem Teilstring =(Infix) von s beschriftet .
- Die Verkettung der Kantenbeschriftungen von der Wurzel zu einem Blatt i entspricht suffi.
- Die Beschriftungen der ausgehenden Kanten eines Knotens beginnen mit paarweise verschiedenen Buchstaben.
- Teilsuffixe nennt man Infixe
- kanten sind stehts alphabetisch sortiert ⇒ erleichtert die Suche!
Wür was braucht man sie:
Suffixe von Strings spielen eine wichtige Rolle für eine große Zahl von Anwendungen,
- z. B. Suche von Zeichenfolgen in einem Text,
- Indizierung,
- Auswertung regulärer Ausdrücke.
Effiziente Speicherung von Suffixen erfordert
- geringen Speicherbedarf,
- geringe Zugriffszeit.
Was ist rechts-maximalität? (Suffix-tree)
Ein wiederholter Teilstring t von String s ist rechts-maximal, wenn es
- mindestens zwei Vorkommen von t in s gibt, denen
- unterschiedliche Zeichen folgen.
Beispiel: t=mat, s=mathematik(h und i verschieden ⇒ also ok) , nicht aber t=ma. (t und t = gleich)
Die Pfad-Beschriftung jedes inneren Knotens im Suffix-Baum ST(s) entspricht solch einem rechts-maximalen Teilstring von s.
Wie ist der Aufbau des Suffix Baumes mit dem MCCreight Algorithmus?
- Einfügen der Suffixe der Reihe nach mit 1 angefangen
- Wenn die Zeichenfolgen übereinstimmen, dann Abstieg bis kein Match mehr und inneren Knoten einfügen
- Nummerierung Blattknoten gibt die Reihenfolge der Erzeugung an und um welches Suffix es sich handelt
Laufzeit: O(n²)
Laufzeit mit Suffixverweisen O(n) hier nicht behandelt
Kanten sind stets alphabetisch sortiert. Reihenfolge der Blätter deshalb = Sortierreihenfolge der Suffixe. ⇒ schnellere Suche
Wie funktioniert das Pattern matching mit dem Suffix Array und LCP (schnelle Variante)?
Pattern Matching ⇒ Binäre Suche auf dem Suffix Array
- Wenn Trerffer, dann mit Hilfe des LCP-Array Grenzen finden
- indem man Länge des Pattern mit entsprechendem LCP-Eintrag vergleicht?!
(wie index?)
https://opencast.informatik.kit.edu/engage/theodul/ui/core.html?id=f983950f-9e6f-4582-8295-e86d0374f7bfda
