Suffix Tree

Question 1

Was ist die String-Tiefe und was die Baum-Tiefe?

Answer 1

String-Tiefe

• Anzahl Buchstaben bis zum Knoten

Baum-Tiefe

• Anzahl der Kanten bis zum Knoten

Question 2

Was ist ein Generalisierter Suffix-Baum?

Answer 2

Ein Suffix-Baum über mehrere Strings

Question 3

Was ist das Suffix Array SA[s] Was kann man damit machen?

Answer 3

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

Question 4

Was ist das LCP?

Answer 4

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

Question 5

Wie kann Pattern matching erfolgen? Wieviele Möglichkeiten gibt es?

Wie kann man das Patternmatching mit dem Suffix Array verkürzen?

Answer 5

2 Möglichkeiten:

1. Über Suffix-Tree:
   
   1. –> gib das Pattern oben in den Baum (aka die Wurzel) –>
   2. Hast du es gefunden, dann gehe zu den darunter liegenden Blättern (ggf. nur ein Blatt) des darunter liegenden Teilbaums –>
   3. Die Indexe der Blätter geben die Anfangsposition der Matches an!
2. Suffix Array und LCP (Binäre Suche) https://www.youtube.com/watch?v=x6j44AtzFmU
   
   1. Idee: Da das Suffix-Array lexikographisch sortiert, stehen die Positionen aller Matches darin unmittelbar hintereinander. Pattern soll in String vorkommen
   2. -> S1: Also Grenzen des Intervalls des Strings setzten _ 1. und letzter Buchsabe/ $ fällt weg, da nicht von Interesse!
   3. 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
   4. F39 https://www.youtube.com/watch?v=UrmjCSM7wDw https://youtu.be/RNtLxlLFtvk?t=1h12m50s
3. 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.)

Question 6

[mP] Wie viele Blätter hat ein Suffix-Baum über einem String s? und was sind innere knoten?

Answer 6

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

Question 7

[mP] Welche Komplexität hat McCreight-Algorithmus zum Aufbau eines Suffix-Baumes über einem String s?

Answer 7

O(n²)

Question 8

[mP] Wie läßt sich die Komplexität des McCreight-Algorithmus senken?

Answer 8

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)

Question 9

[mP] Zeigen Sie: In einem Suffix-Array benachbarte Suffix-Paare haben ein längeres gemeinsames Präfix als alle anderen denkbaren Suffix-Paare.

Answer 9

ad

Question 10

[mP] Konstruieren Sie den Suffix-Baum über einem String, z. B. ananas$

Answer 10

ad

Question 11

Wie sind die Suchkosten beim Interval Matching vom Suffix Array

Wie lassen sich die Suchkosten reduzieren?

Answer 11

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.

Question 12

Was ist ein Suffix-tree? und wozu braut man sie?

Answer 12

• 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.

Question 13

Was ist rechts-maximalität? (Suffix-tree)

Answer 13

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.

Question 14

Wie ist der Aufbau des Suffix Baumes mit dem MCCreight Algorithmus?

Answer 14

• 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

Question 15

Wie funktioniert das Pattern matching mit dem Suffix Array und LCP (schnelle Variante)?

Answer 15

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

Question 16

Wie können Bereichsanfragen/Intervallanfragen gemacht werden?

Wie wird das mit einem “Regulären Ausdruck” gemacht?

Mit dem Suffix Array und mit dem Suffix tree!!!

Answer 16

https://opencast.informatik.kit.edu/engage/theodul/ui/core.html?id=f983950f-9e6f-4582-8295-e86d0374f7bf

Suffix tree

• Nach unten im Baum steigen und dann nach rechts (min 45)

und beim Regulären Ausdruck folgendes

• Regulären Ausdruck durch Automaten ersetzen.
• Tiefensuche durch den Automaten. Gleichzeitig im Baum nach unten steigen.
• Backtracking im Automat (und entsprechend auch im Baum), wenn es im Automat nicht mehr ‚weitergeht‘.
• Wenn Zielzustand des Automaten erreicht: Alle Blätter des aktuellen Teilbaums als Resultate ausgeben.

Question 17

Warum fängt man beim MCCreight Algorithmus mit dem längesten Suffix an? Wäre es nicht geschickter mit dem kürzesten anzufangen?

Answer 17

da