String matching WS13-14
Inhaltsverzeichnis |
Autor: Yevgeniy Oliynyk
Allgemeines und Festlegungen
String matching befasst sich allgemein mit dem Finden eines Wortes in einem Text.
Beim Text handelt es sich um eine endliche Folge von Zeichen (bestehend aus dem Alphabet \Sigma der Groß- und Kleinbuchstaben, Zahlen und Satzzeichen) und wird mit t abgekürzt. Das Wort setzt sich ebenfalls aus denselben Zeichen zusammen und wird abgekürzt als w dargestellt. Obwohl es aus mehreren Wörtern bestehen kann, wird es im Folgenden als "Wort" bezeichnet.
Sowohl der Text, als auch das Wort, weisen eine bestimmte Länge auf. Dies bezieht sich auf die Anzahl der Zeichen des Textes bzw. des Wortes. Beim Text wird die Länge mit n (bzw. |t|) bezeichnet und beim Wort mit m (bzw. |w|). Dabei gilt für jedes Text- und Wortpaar in den Beispielen der Seite folgende Vereinbarung: m \leq n.
Um nun festzustellen, ob sich ein Wort in einem Text befindet, müssen einzelne Zeichen verglichen werden. Deren Positionen werden folgedermaßen beschrieben:
- das i-te Zeichen von t heißt t[i], wobei 1\leq i \leq n gilt
- das j-te Zeichen von w heißt w[j], wobei 1\leq j \leq m gilt.
Somit ist eine präzise Positionsangabe möglich.
Der Standardtext für alle hier aufgeführten Beispiele lautet: Das ist das Haus vom Nikolaus mit n=29.
Ein naiver Algorithmus
Vorüberlegung
Um zu erfahren, ob sich das gesuchte Wort an einer beliebigen Stelle t[pos] (1 \leq pos \leq n-m+1) im Text befindet, muss ein Vergleich zwischen den Zeichen an der Stelle t[pos] und w[1] unternommen werden. Falls diese übereinstimmen, so wird weiter verglichen. Im nächsten Schritt wären es dann die Zeichen der Positionen t[pos+1] und w[2]. In der Art und Weise geht es weiter, bis entweder irgendwann 2 ungleiche Zeichen miteinander verglichen werden oder der Fall eintritt, dass auch die Zeichen an der Stelle t[pos+m-1] und w[m] überein stimmen. Das erstere bedeutet, dass das Wort nicht im Text an der gegebenen Position vorkommt. Das letztere hingegen würde eine Erfolgsmeldung nach sich ziehen.
Beispiele
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Beispiel 1 | Beispiel 2 |
Programmbeispiel
Bisher wird aber nur eine Stelle im Text betrachtet. Um aber festzustellen, ob sich das Wort nicht nur an einer bestimmten Stelle befindet, sondern ob es an einer beliebigen Position vorkommt, ist eine Schleife nötig. Dadurch geht man Zeichen für Zeichen den Text durch und Vergleicht diesen mit dem Wort. Da es eine naive Methode ist, kann man ganz genau sagen, wie viele Schleifendurchläufe nötig sind, nämlich n-m+1. Als Ergebnis einer solchen Funktion, würde man alle Vorkommen des Wortes im Text und dessen Position als Ergebnis zurückbekommen. Sollte sich das Wort nicht im Text befinden, so bekommt man eine dementsprechende Antwort.
Ein passender Algorithmus dazu könnte wie folgt aussehen:
Aufgabe 1
Ergänze das Programmbeispiel so, dass nach der Abarbeitung angezeigt wird, wie viele Stellen im Text untersucht wurden.
Laufzeitanalyse
Durch die Einfachheit des Algorithmus lässt sich eine Laufzeitanalyse wunderbar durchführen.
Im Best-Case würde offensichtlich so aussehen, dass bei jedem Schleifendurchgang nur eine Vergleichsoperation durchgeführt wird. Dies wäre der Fall, wenn m=1 ist oder wenn das Zeichen w[1] nicht in t vorkommt. Somit ist die Laufzeit \mathcal{O}(n-m+1).
Im Worst-Case gibt es den Fall, dass bei jeder Stelle des Textes, alle Zeichen des Wortes mit dem jeweiligen Zeichen des Textes verglichen werden müssen. Ein Beispiel für so einen Fall wäre
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Schritt 1 | Schritt 2 | Schritt 3 |
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Beispiel 1: verschieben um 4 Stellen | Beispiel 2: verschieben um 3 Stellen |
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||
| Beispiel 1: w = Katze | Beispiel 2: w = stets | Beispiel 2: w = Schneeleopard |
1 m ← länge[w] 2 for q ← 0 to m 3 do for jedes Zeichen a \in \Sigma 4 do k ← min(m+1,q+2) 5 repeate k ← k - 1 6 until w_k \sqsupset w_q a 7 \delta (q,a) ← k 8 return \delta |
Bemerkung
Die Schleifen, die in Zeile 2 und 3 beginnen, betrachten alle Zustände in Kombination mit allen Zeichen. Ziel der Funktion ist es den Folgezustand k zu ermitteln, der in Zeile 7 in eine Übergangstabelle \delta(q,a) in das jeweilige Feld eingetragen wird. w_k steht für das Wort, das aber nur bis zur k-ten Stelle betrachtet wird und w_q a ist das selbe wie a an w_{k-1} angehängt.
Beispiel
M = (Q,\Sigma , q_0 , E, \delta ), mit
- Q = \{ 0,1,2,3,4,5,6,7\}
- \Sigma = \{ a,b,c\}
- q_0 = 0
- E = \{ 7\}
- \delta
Aufgabe 3
Entwickle mit Hilfe von AtoCC einen (deterministischen) endlichen Automaten für das Wort w=cbccbacb mit \Sigma = \{ a,b,c\} mit Hilfe der gegebenen Vorschrift. Wende es danach auf die Texte t_1=abbacbacbccbacb und t_2=cbccbacba an. Analysiere, wieso der Automat für t_2 kein Signal gibt, dass er das Wort gefunden hat, obwohl w in t_2 offensichtlich vorkommt. Wie müsste man den Automaten ändern, damit das Wort trotzdem gefunden wird?
Der Knuth-Morris-Pratt-Algorithmus
Obwohl die Suche beim endlichen Automaten eine akzeptable Laufzeit ausweist, stellt die Vorverarbeitung und damit die Berechnung der Überführungsfunktion mit einem Aufwand in \Theta(m |\Sigma|) ein Hindernis dar. Eine vielversprechende Lösung bietet der KMP Algorithmus. Statt der \delta kommt eine Hilfsfunktion \pi (auch Feld genannt) zum Einsatz für die Vorberechnung. Deren Aufwand liegt in nur \Theta(m). Das Matching selber ist vom Aufwand her derselbe, wie schon mit endlichen Automaten.
KMP-Matching-Algorithmus
KMP-Matcher(t,w)
1 n ← länge[t] 2 m ← länge[w] 3 \pi ←Compute-Prefix-Function(w) 4 q ← 0 5 for i ← 1 to n 6 do while q > 0 und w[q+1] ≠ t[i] 7 do q ← \pi[q] 8 if w[q+1] = t[i] 9 then q ← q+1 10 if q=m 11 then print "Das Wort tritt mit der Verschiebung" i-m "auf" 12 q ← \pi[q] |
Compute-Prefix-Function(w)
1 m ← länge[w] 2 \pi[1] ← 0 3 k ← 0 4 for q ← 2 to m 5 do while k>0 und w[k+1] ≠ w[q] 6 do k ← \pi[k] 7 if w[k+1] = w[q] 8 then k ← k+1 9 \pi[q] ← k 10 return \pi |
Das Ziel der Präfixfunktion ist es, für jedes Zeichen von w einen Wert \pi zu berechnen, der beim Matching aussagt, was die nächste Position ist, auf die das Wort verschoben werden soll. Die Demonstration geschieht an einem Beispiel.
Zuerst wird die Tabelle \pi für das Wort w=ababababca berechnet.
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| w[i] | a | b | a | b | a | b | a | b | c | a |
| \pi[i] | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 0 | 1 |
Jeder Wert \pi[i] gibt darüber Auskunft, um wie viele Stellen das Wort beim Suchen verschoben werden kann für den Fall, dass w[i+1] nicht mit t[j] (wobei 0<j<n) übereinstimmt oder w[m] = w[j] ist. Dabei berechnet sich die Verschiebung aus i-\pi[i]. Die Funktion gibt außerdem eine Auskunft über die Präfixeigenschaften des Wortes (wodurch sie auch zustande kommt). So ist w_{\pi[i]} ein Präfix von w_i.
Bemerkung
Falls \pi[i]=0 und somit w_{\pi[i]} = w_0, ergibt sich ein Wort der Länge 0, also ein Wort ohne Zeichen. Dieses Wort ist automatisch ein Präfix von allen beliebigen Wörtern. Somit ist die Aussage, dass w_{pi[i]} ein Präfix von w_i ist, in dem Bezug allgemeingültig.
Aufgabe 4
Berechne \pi für w=bcbccbcbca.
Beispiel
Für die Suche des Wortes w im Text t=abababababcbababababca sehen die entscheidenden Schritte folgendermaßen aus:
| Position: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | a | b | a | b | c | b | a | b | a | b | a | b | a | b | c | a |
| Wort: | a | b | a | b | a | b | a | b | c | a |
| Position: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | a | b | a | b | c | b | a | b | a | b | a | b | a | b | c | a |
| Wort: | a | b | a | b | a | b | a | b | c | a |
| Position: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | a | b | a | b | c | b | a | b | a | b | a | b | a | b | c | a |
| Wort: | a | b | a | b | a | b | a | b | c | a |
| Position: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | a | b | a | b | c | b | a | b | a | b | a | b | a | b | c | a |
| Wort: | a | b | a | b | a | b | a | b | c | a |
| Position: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | a | b | a | b | c | b | a | b | a | b | a | b | a | b | c | a |
| Wort: | a | b | a | b | a | b | a | b | c | a |
| Position: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | a | b | a | b | c | b | a | b | a | b | a | b | a | b | c | a |
| Wort: | a | b | a | b | a | b | a | b | c | a |
| Position: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | a | b | a | b | c | b | a | b | a | b | a | b | a | b | c | a |
| Wort: | a | b | a | b | a | b | a | b | c | a |
Überblick aller Laufzeiten
| Algorithmus | Vorverarbeitungszeit | Matchingzeit |
|---|---|---|
| naiv | 0 | \mathcal{O}((n-m+1)m) |
| BMH | \Theta(m) | \mathcal{O}((n-m+1)m) |
| endlicher Automat | \mathcal{O}(m|\Sigma |) | \Theta(n) |
| KMP | \Theta(m) | \Theta(n) |
Lösungen
Aufgabe 1
Aufgabe 2
Aufgabe 3
Übergangsfunktion in Form einer Tabelle:
| \delta | a | b | c |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 1 | 0 | 2 | 1 |
| 2 | 0 | 0 | 3 |
| 3 | 0 | 2 | 4 |
| 4 | 0 | 5 | 1 |
| 5 | 6 | 0 | 3 |
| 6 | 0 | 0 | 7 |
| 7 | 0 | 8 | 1 |
| 8 | 0 | 0 | 3 |
Analyse: ein DEA akzeptiert nur vollständig gelesene Wörter und nur dann, wenn der Zustand nach dem vollständigen Lesen ein Endzustand ist. Somit ist er nicht in der Lage mehrere Vorkommen eines Wortes in einem Text zu finden bzw. nur wenn das Wort an der Stelle n-m+1 im Text steht.
Änderung: DEA in NEA umwandeln und die Übergänge für alle \Sigma von q_m nach q_m ergänzen.
Aufgabe 4
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| w[i] | b | c | b | c | c | b | c | b | c | a |
| \pi[i] | 0 | 0 | 1 | 1 | 2 | 3 | 2 | 3 | 0 | 0 |
Quellen
- Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford: Algorithmen, eine Einführung,Oldenbourg Verlag, 2007
- Vöcking, Berthold: Taschenbuch der Algorithmen, Springer-Verlag, 2008