Startroutine des Knuth-Morris-Pratt

Ansporn für den folgenden Text war das Buch Algorithmen in C“von Robert
”
Sedgewick.
Ziel von String-Matching-Algorithmen oder dem Suchen in Zeichenfolgen“ist
”
es, in einer längeren Zeichenkette eine kürzere Zeichenkette, mit derselben Folge
von Zeichen zu finden. Dafür gibt es einen naiven Algorithmus. Das bedeutet:
Wir gehen in Text jedes Zeichen zeichen für Zeichen durch (Text ist die längere
Zeichenkette) und suchen nach dem Muster bzw. der Zeichenfolge, die zu finden
ist. Generell funktioniert dieser naive Algorithmus so: Wenn wir an einer Stelle
im Text eine Überstimmung des ersten Zeichens im Muster mit der aktuellen
Stelle haben, vergleichen wir weiter. Wenn das zweite Zeichen im Muster wieder
mit dem nächsten Zeichen im Text übereinstimmt, vergleichen wir auch weiter.
Wir vergleichen solange weiter, bis die Zeichenkette entweder eine vollkommen
Übereinstimmung oder Überdeckung hat, kurz und gut, die gesuchte Zeichenkette im Text gefunden ist, oder wir suchen nach dem nächsten Zeichen im Text,
wo wir vorher mit dem ersten Zeichen im Muster eine Übereinstimmung hatten
weiter.
Dieser Algorithmus hat einen großen Nachteil. Man denke daran: Auf der Festplatte sind die Daten in Sektoren gespeichert. Was ist nun wenn wir eine Zeichenkette in einer Datei suchen, die sich über mehrere Sektoren hin erstreckt
und nun die Zeichenkette kurz vor dem Ende eines Sektors gefunden wurde, sie
aber über die Sektorgrenze hinaus reicht? Nun haben wir im zweiten Sektor den
Fall, dass die Zeichenkette nicht übereinstimmt, nun müssen wir den vorherigen
Sektor auf der Festplatte neu laden. Kurz und gut, dieses Szenario lässt sich
noch weiter aufbauen, was ist wenn die Zeichenkette die wir suchen, selber so
groß ist wie ein Sektor? Das führt zu Programmiertechnischen Schwierigkeiten.
Schauen Sie selbst nach dem naiven Algorithmus für das Suchen von Zeichenketten in Texten nach. Den Fall, dass man eine Zeichenkette keine Übereinstimmung brachte, nennt man übrigens Miss-Match.
Nun ich verwende jetzt ein Beispiel einer Zeichenkette, nämlich ababcabab, die
wir in einem Text finden wollen. Das Beispiel ababcabab stammt nicht von mir,
sondern von wikipedia, nämlich de.wikipedia.org/wiki/Knuth-Morris-Pratt-Algorithmus.
Aber es ist ausdrücklich betont, dass die Zeichenfolge ababcabab von dieser Seite stammt.
Nun: Wenn wir eine Zeichenkette in einem Text suchen, dann tauchen in der
Zeichenkette eventuell Wiederholungen vom Anfang der Zeichenkette auf. So ist
in ababcabab am Schluss das ...abab eine Widerholung vom Anfang abab....
Wenn es nun einen Missmatch gibt, während wir das Muster mit dem Text
vergleichen, wäre es manchmal klug zu wissen, in wie weit an der Stelle, an
der wir gerade kein Erfolgserlebnis hatten, in wie weit diese Stelle, bereits am
Anfang des Musters auftauchte. Aber ich betone: Am Anfang! Es nutzt nichts,
wenn wir eine Folge wie xyzabababab haben. Auf diesen Gedanken muss man
erst gar nicht kommen, oder man muss auf ihn kommen. Verglichen, und nun
kommt der Knuth-Morris-Pratt-Algorithmus wird nur der Anfang. Wenn wir als
eine Zeichenkette haben, wie xyzklmababuvwpppabab nutzt und das Wiederauftauchen des Hinteren abab mit dem in der Mitte des Muster stehenden abab’s
1
nichts! Es muss etwas dastehen, wie abab012378abab. Nur wenn zum Beispiel
in diesem Beispiel das abab am Ende auftaucht, wie das abab am Anfang, ist
die Sache relevant.
Was ist denn wenn wir das Muster abab01237ababc haben. Wir vergleichen es
mit dem Text. Der Text lautet ...abab01237abab0.... Wenn wir abab01237ababc
haben, dann erleiden wir bei der letzten 0 des Textes mit dem letzten Endes
des Musters, nämlichababc bei c einen Missmatch. Trotzdem könnte an genau
dieser Stelle abab01237abab01237ababc stehen und wir würden das Muster etwas später finden.
Wir verfügen nun über zwei Funktionen: Die erste Funktion ist die Suchfunktion
im Muster, die zweite Funktion, analysiert, in wie weit der Anfang des Musters,
weiterhin in dem Muster überhaupt auftaucht.
a b
a
b
c
a
b
a
b
a
b
c
a
b
a
b
-1 a b
0
a
b
a
b
c
a
b
a
b
1
(a)
b
a
b
c
a
b
a b
2
(a) (b) a
b
c
a
b
a b
0
a
b
a
b
c
a
b a b
Das heißt:
0
a
b
a
b
c
a b a b
1
(a)
b
a
b
c a b a b
2
(a) (b)
a
b
c a b a b
(a) (b) (a)
b
c a b a b
3
4
(a) (b) (a) (b) c a b a b
Wenn das Muster vom Anfang an betrachtet, an irgendeiner Stelle im Muster
selber wieder auftaucht, gilt die Stelle, an der es auftaucht, als eine Stelle über
die man sagen kann: Hier haben wir das Muster schon so oder so weit verglichen.
Wenn der Anfang des Musters in dem Muster auftaucht, dann ist an der Stelle,
wo es auftaucht, das Muster schon so weit verglichen an dieser Stelle, wie viele
Zeichen von seinem Anfang vom Anfang an gezählt schon auftauchen. Wenn
also die ersten vier Zeichen im Muster den Anfang darstellen und diese ersten
vier Zeichen in der selben Reihenfolge im Muster wieder auftauchen, gilt: Wir
haben an der Stelle, wo wir dieses Wiederauftauchen haben, schon vier Zeichen
verglichen, oder diese vier Zeichen, entsprechen dem Anfang.
Wir benutzen nun eine Tabelle next um uns zu merken, für jedes Zeichen im
Muster, wie weit darin der Anfang schon auftauchte.
Beim Vergleichen benutzen wir diese Tabelle. Die Tabelle wird zunächst durch
eine Funktion initnext aufgefüllt.
Nun zu der Funktion des Knuth-Morris-Pratt-Algorithmus:
Diese Funktion kann ich leider nicht veröffentlichen, denn sie steht in Robert
Sedgewicks Algorithmen in C“. Dort ist aber auch eine besonders komplizierte
”
Variante von initnext() vorgestellt. Und um die geht es. Die folgende Funktion
2
könnte die Aufgabe auch erfüllen:
int initnext(char *p, int next[]) {
int n, m;
int i, j;
int flag;
next[0] = -1;
for(n = 1; n < strlen(p); n++) {
next[n] = 0;
for(m = 1; m <= n; m++) {
for(i = m, j = 0, flag = 1;
if(p[i] != p[j]) {
flag = 0;
break;
}
}
if(flag == 1) {
next[n] = j;
break;
}
}
}
return;
}
(i <= n);
i++, j++) {
Für jedes n durchsuchen wir zunächst vom Index 1 wie, ob das Muster auftaucht.
Das heißt es muss von 1 bis n der Anfang vorhanden sein. Wenn an dieser Position, d.h. bei 1 es irgendwo keine Übereinstimmung gab, probieren wir es an
der 2. Position, dann an der 3. Das mit for(n = 1; n < strlen(p; n++)
hat schon seine Richtigkeit. Denn wir wollen für jedes n die Tabelle aufstellen.
Wir müssen ja für jedes Zeichen auch angeben und zwar müssen wir für jedes
Zeichen angeben, wie weit die Position mit dem Anfang übereinstimmt.
Noch eine kleine Trockenübung:
Wenn wir in einem Muster ab einer bestimmten Stelle, das Muster ab einer
anderen bestimmten Stelle miteinander vergleichen:
for(i = m, j = n; (i <= k) && (j <= k);
if(p[i] != p[j]) {
...
...
}
}
3
i++, j++) {

Download Report