Die Folien sind teilweise inspiriert von oder basierend auf Lehrmaterial von Prof. Dr. Ritterbusch
Texte können als unsortierte Arrays von Zeichen verstanden werden. Eine typische Frage ist hier das Finden von Textsequenzen im Text.
1function NaiveTextSearch(text,needle)2n := length(text)3m := length(needle)4for i := 1,...,n-m + 1 do5j := 06while text[i + j] == needle[j + 1] do7j := j + 18if j == m then9return i // Found at i10return nil
Beispiel bei einfacher Suche nach aaab in aaaaaaaab:
a a a a a a a a b
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
a a a b̶
a a a b̶
a a a b̶
a a a b̶
a a a b̶
a a a b
Sind so viele Vergleiche notwendig?
Das Verfahren von Knuth-Morris-Pratt vermeidet unnötige Vergleiche, da es zunächst die Suchwortteile auf den größten Rand, also das größte Prefix, das auch Postfix ist, untersucht.
Beispiel/Idee
Text 010110101 Gesucht/Muster 010101 Übereinstimmung ✓✓✓✓✗
Beobachtungen:
Wir haben an Stelle 5 ein Mismatch.
Wenn wir im Text das Muster um eine Stelle nach rechts verschoben suchen, so haben wir garantiert wieder ein Mismatch.
Beispiel/Idee
1. 2. Text 01101100 0102111 Gesucht/Muster 01100 010201 Übereinstimmungen ✓✓✓✓✗ ✓✓✓✓✗
Beobachtungen bzgl.:
Beim Mismatch an Stelle 5 kann das Muster „nur“ um 3 Stellen nach rechts verschoben werden.
Beim Mismatch an Stelle 5 kann das Muster um 4 Stellen nach rechts verschoben werden.
Wie weit wir das Muster verschieben können, hängt also vom Rand des Teils des Musters ab, der bereits übereinstimmt.
Beispiel
Das Wort \(aufkauf\) hat die echten Präfixe und Postfixe:
\(\{p^{(k)} : 0 \leq k <n\}=\{\varepsilon ,a,au,auf,aufk,aufka,aufkau\}\)
\(\{q^{(k)} : 0 \leq k <n\}=\{\varepsilon ,f,uf,auf,kauf,fkauf,ufkauf\}\)
und die Ränder:
\(\{r^{(k)} : 0 \leq k <n\}= \{\varepsilon ,auf\}\).
Das bedeutet, dass wenn \(aufkauf\) erkannt wurde, die letzten drei Buchstaben schon den nächsten Treffer einleiten können, wie beispielsweise in \(aufkaufkauf\).
Das KMP-Verfahren fängt nicht immer von vorne an, sondern prüft, ob ein Rand eines Präfixes \(- \varepsilon \) ausgenutzt werden kann. Dazu werden die entsprechenden größten Ränder bestimmt.
Beispiel: ananas
Präfixe \(\setminus \{\varepsilon \}\) |
Größter Rand |
Länge des Randes |
|---|---|---|
a |
ε |
0 |
an |
ε |
0 |
a̲na̅ |
a |
1 |
a̲n̲a̅n̅ |
an |
2 |
a̲n̲a̲̅n̅a̅ |
ana |
3 |
ananas |
ε |
0 |
Beispiel: axaaxax
Präfixe \(\setminus \{\varepsilon \}\) |
Größter Rand |
Länge des Randes |
|---|---|---|
a |
ε |
0 |
ax |
ε |
0 |
a̲xa̅ |
a |
1 |
a̲xaa̅ |
a |
1 |
a̲x̲aa̅x̅ |
ax |
2 |
a̲x̲a̲a̅x̅a̅ |
axa |
3 |
a̲x̲aaxa̅x̅ |
ax |
2 |
Die Idee ist also, dass wir beim Musterabgleich nach einem Mismatch, wenn der übereinstimmende Teil einen Rand hat, beim Abgleich des Musters an einer späteren Stelle - basierend auf der Größe des Randes - weitermachen können. Wir müssen also nicht immer das ganze Muster von vorne anfangen zu vergleichen.
Ränder und Randlängen bestimmen
Bestimmen Sie die Ränder und die Längen der \(Präfixe - \varepsilon \) für die Worte:
\(tultatul\)
\(eikleike\)
\(okokorok\)
\(trattrad\)
1function ComputePrefixFunction(needle)2m := length(needle)3sei B[1...m] ein Array // Array für die Längen der Ränder der Teilworte4B[1] := 05j := 0 // j ist die Länge des Randess6for i := 2,...,m do7j := j + 18while j > 0 and needle[j] ≠ needle[i] do9if j > 1 then10j := B[j-1] + 111else12j := 013B[i] := j14return B
Komplexität: \(O(m)\)
1function KMP(text,needle)2n := length(text), m := length(needle)3B := ComputePrefixFunction(needle)4q := 0 // Anzahl der übereinstimmenden Zeichen5R := [] // Ergebnisliste der Indizes der Übereinstimmungen6for i := 1,...,n do7while q > 0 and needle[q + 1] ≠ text[i] do8q := B[q] // ... die nächsten Zeichen stimmen nicht überein9if needle[q + 1] == text[i] then10q := q + 1 // Übereinstimmung11if q == m then12R append (i - m + 1)13q := B[q] // Suche nach nächster Übereinstimmung14return R
Komplexität: \(O(n+m)\)
Details ComputePrefixFunction
Die Funktion \(ComputePrefixFunction\) berechnet die größten Werte der Präfixe für das Suchwort \(needle\) der Länge \(m\) und gibt diese als Array (\(B\)) zurück. Das Array \(B\) enthält somit die größten Ränder der Präfixe \(needle[1,...,i]\). (Der Wert von \(B[1]\) ist immer 0, da es keinen Rand gibt.)
Gesucht wird ananas in saansanananas
s a a n s a n a n a n a s i ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ 1 a̶ ... 3 a n̶ ... 5 a n a̶ ... 11 a n a n a s̶ Beim Auftreten des Mismatch (ln 7) ist ... q=5 und wird auf p[5]=3 (ln 8) gesetzt 13 a n a n a s
KMP-Algorithmus
Bestimmen Sie die Randlängen der Muster und stellen Sie die Teilschritte bei der Durchführung des KMP-Algorithmus zur Suche des Wortes/Muster im Text dar.
Stellen Sie insbesondere die Fälle dar in denen ein Mismatch auftritt.
Muster |
Text |
|---|---|
aaab |
aaaaaaaab |
barbara |
abbabarabarbarbara |
Der Algorithmus vergleicht das Muster (Pattern) von rechts nach links mit dem Text.
Viele andere Algorithmen führen die Vergleiche von links nach rechts durch.
Der Boyer-Moore-Algorithmus nutzt dies aus, indem er die Verschiebung des Musters anhand des letzten Zeichens des Musters und des Textes vornimmt.
Wird beispielsweise das Wort Banane im Text Orangen,␣Ananas␣und␣Bananen gesucht, so wird zunächst die Sprungtabelle für das verwendete Alphabet in Bezug auf das Suchwort (Banane mit Länge 6) bestimmt:
Zeichen im Text |
␣ |
, |
A |
B |
O |
a |
d |
e |
g |
n |
r |
s |
u |
Sprung |
6 |
6 |
6 |
5 |
6 |
2 |
6 |
0 |
6 |
1 |
6 |
6 |
6 |
O r a n g̲ e̲ n , ␣ A n̲ a̲ n a̲ s ␣̲ u n d ␣ B̲ a̲ n̲ a̲ n̲ e̲ n̲
B a n a n̶̲ e̶̲
B a n a n e̶̲
B a n a n e̶̲
B a n a n e̶̲
B a n a n e̶̲
B a n a n e̶̲
B a n a n e̶̲
B̲ a̲ n̲ a̲ n̲ e̲
B a n a n e̶̲
Komplexität
Im guten und häufigen Fall erreicht das Verfahren \(O(\frac{n}{m})\), aber in speziellen Fällen ist auch \(O(n·m)\) möglich.
Bei der Sprungtabelle handelt es sich um eine Tabelle, die für jedes Zeichen des Alphabets des Textes die Verschiebung des Musters angibt, wenn das Zeichen im Text mit dem Muster nicht übereinstimmt. Die Zeichen A, O, d, g, r, s, u, , und das Leerzeichen haben die größte Verschiebung, da sie nicht im Muster vorkommen. Das Zeichen e hat die kleinste Verschiebung, da es das letzte Zeichen des Musters ist. Das Zeichen n hat eine Verschiebung von 1, da es im Muster als vorletztes Zeichen vorkommt, das Zeichen a hat eine Verschiebung von 2, da das späteste Vorkommen an drittletzer Stelle ist, und das Zeichen B hat eine Verschiebung von 5, da es nur einmal vorkommt und das erste Zeichen des Musters ist.
„belli“
Suchen Sie das Wort
belli
im Text
It is a dark time for the Rebellion.
"barbara"
Suchen Sie das Wort
barbara
im Text
abbabarabarbarbara