Knuth-Morris-Pratt-Algorithmus
Der Knuth-Morris-Pratt-Algorithmus wurde nach Donald Ervin Knuth, James Hiram Morris und Vaughan Pratt benannt und ist ein String-Matching-Algorithmus. Seine asymptotische Laufzeit ist linear in der Länge des Musters (auch Suchbegriff, Suchmaske), nach dem gesucht wird, plus der Länge des durchsuchten Textes.
Pratt entwickelte 1970 die Grundidee unabhängig von Knuth (der etwas später darauf stieß), und Pratt und Morris veröffentlichten 1970 einen Technischen Bericht dazu.[1] Schließlich veröffentlichten alle drei 1977 einen Aufsatz dazu.[2]
Beschreibung
Der Knuth-Morris-Pratt-Algorithmus baut auf dem Naiven Suchalgorithmus auf. Wesentlicher Unterschied ist, dass das Vergleichsfenster nicht immer um nur eine Position weitergerückt wird, sondern eventuell um mehr als eine Position.
Dazu muss zu Anfang die Suchmaske auf Zeichenfolgen analysiert werden, die ein möglichst langes Präfix des Musters selbst sind. Es wird vom Algorithmus dann eine Tabelle erstellt, die zu jedem Präfix der Länge j die Länge des echten Randes des Präfixes enthält, also die maximale Anzahl von Zeichen innerhalb des Präfixes des Suchmusters, die gleichzeitig Suffix und Präfix desselben sind. Es ist definiert, dass außerdem die Länge des echten Randes für ein Präfix der Länge Null gleich −1 ist. Dies wird später im Algorithmus beim Suchen hilfreich sein.
Folgendes Beispiel veranschaulicht das Gesagte bildlich:
| Länge | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| Muster: | a | b | a | b | c | a | b | a | b | 9 |
| Präfix (0..0): | 0 | |||||||||
| Präfix (0..1): | 0 | |||||||||
| Präfix (0..2): | a | a | 1 | |||||||
| Präfix (0..3): | a | b | a | b | 2 | |||||
| Präfix (0..4): | 0 | |||||||||
| Präfix (0..5): | a | a | 1 | |||||||
| Präfix (0..6): | a | b | a | b | 2 | |||||
| Präfix (0..7): | a | b | a | a | b | a | 3 | |||
| Präfix (0..8): | a | b | a | b | a | b | a | b | 4 |
Während der Suche wird nun zunächst so vorgegangen, wie bei der naiven Suche: Es wird an Position 0 begonnen, die Zeichen von Text und Suchmaske zu vergleichen, so lange, bis zwei Zeichen nicht mehr übereinstimmen oder die Suchmaske gefunden wurde. Wurde die Suchmaske gefunden, ist der Algorithmus abgeschlossen. Stimmen die Zeichen vor einem vollständigen Treffer nicht überein, so wird die Suchmaske um die Differenz zwischen der Anzahl der übereinstimmenden Zeichen und der Länge des Randes des Präfixes nach rechts verschoben. Hier kommt die vorherige Definition der Länge des Randes eines Präfixes der Länge Null ins Spiel: die Differenz zwischen 0 und −1 ist 1, folglich wird also bei einem nicht übereinstimmenden Zeichen an erster Stelle um eins nach rechts verschoben. Außerdem wird dann mit der Suche um die Länge des Randes des Präfixes oder Null, falls der Rand kürzer als Null ist, weiter rechts begonnen.
Bei jeder teilweisen Übereinstimmung, etwa der ersten k Symbole, ist nun also bekannt, ob der Anfang der Suchmaske mit dem Ende der letzten übereinstimmenden Teilmaske übereinstimmt. Die Verschiebung der Suchmaske erfolgt nach der überlappenden Übereinstimmung; zusätzlicher Vorteil ist, dass die schon verglichenen Symbole nicht noch einmal verglichen werden müssen.
Die so gewonnene Information wird so während der Suche verwendet, um wiederholte Vergleiche zu vermeiden.
Folglich gliedert sich der Algorithmus in zwei Phasen, nämlich
- die Präfix-Analyse, die das Muster selbst analysiert, und
- die eigentliche Suche.
Suche
Als Beispiel suchen wir im Text „abababcbababcababcab…“ nach dem Muster „ababcabab“.
Wie beim Naiven Algorithmus wird das Muster linksbündig unter den Text geschrieben und die Buchstabenpaare werden von links nach rechts verglichen, bis Muster und Text nicht mehr übereinstimmen (Auftreten eines Fehlers):
| Position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | … |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | c | b | a | b | a | b | c | a | b | a | b | c | a | b | … |
| Muster: | a | b | a | b | c | a | b | a | b |
Der erste Fehler wird an Position 4 im Text festgestellt. Betrachten wir die zuvor berechnete Tabelle mit der Länge der Ränder eines Präfixes an der Stelle „Präfix (0..3)“, so sehen wir, dass hier die Länge 2 hinterlegt ist. Das Muster wird also um 2 Zeichen nach rechts verschoben, sodass es sich mit dem Suffix (also dem „zweiten Teil“ des Randes) passend überlappt; außerdem wird mit der Suche direkt nach dem Rand fortgefahren, da wir ja bereits wissen, dass die beiden Teile übereinstimmen (dies ist die große Stärke des KMP-Algorithmus):
| Position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | … |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | c | b | a | b | a | b | c | a | b | a | b | c | a | b | … |
| Muster: | a | b | a | b | c | a | b | a | b |
Der Algorithmus fährt also bei Position 4, also genau dort wo zuvor ein Fehler gefunden wurde, mit dem Vergleichen fort. Insbesondere wird der Rand „ab“ nicht nochmals überprüft.
| Position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | … |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | c | b | a | b | a | b | c | a | b | a | b | c | a | b | … |
| Muster: | a | b | a | b | c | a | b | a | b |
Der nächste Fehler tritt bei Position 7 im Text, und damit bei Position 5 im Suchmuster auf. Wir betrachten wieder unsere Tabelle bei „Präfix (0..4)“, sie besagt, dass es hier keine Zeichen gibt, die einen Rand bilden (Länge Null). Wir können jetzt also sicher sein, dass es keine Treffer gibt, durchsuchten wir die Zeichen bis Position 7 durch naives Schieben nach rechts um ein Zeichen. Deshalb kann das Muster bis unter die Stelle 7 im Text geschoben werden, das Ergebnis von Suchtextposition + (Anzahl der Übereinstimmenden Zeichen – Randlänge(Präfixlänge)), also 2 + (5 – 0) = 7:
| Position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | … |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | c | b | a | b | a | b | c | a | b | a | b | c | a | b | … |
| Muster: | a | b | a | b | c | a | b | a | b |
Der Algorithmus fährt dann wieder bei Position 7 mit dem Vergleichen fort.
| Position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | … |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | c | b | a | b | a | b | c | a | b | a | b | c | a | b | … |
| Muster: | a | b | a | b | c | a | b | a | b |
Manchmal tritt, wie hier, bereits an der ersten Stelle des Musters ein Fehler auf. In diesem Fall wird das Muster um 1 nach rechts geschoben; Suchtextposition + (Anzahl der Übereinstimmenden Zeichen − Randlänge(Präfixlänge)), also 7 + (0 − (−1)) = 8, und der Algorithmus fährt hier an der nächsten Stelle im Text (also 8) mit Vergleichen fort.
| Position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | … |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | c | b | a | b | a | b | c | a | b | a | b | c | a | b | … |
| Muster: | a | b | a | b | c | a | b | a | b |
Wurden alle Zeichen des Musters im Text gefunden, so wird ein Treffer ausgegeben.
Da die zuletzt überprüften vier Zeichen „abab“ an Position 13 bis 16 ein Präfix der Länge 4 sind, wird das Muster an Stelle 13 verschoben. Das Vergleichen wird wieder an Stelle 17 (=13+4) fortgesetzt:
| Position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | … |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | c | b | a | b | a | b | c | a | b | a | b | c | a | b | … |
| Muster: | a | b | a | b | c | a | b | … |
Der Algorithmus endet, sobald das Muster nicht weiter nach rechts verschoben werden kann, ohne über das Ende des Textes hinaus zu ragen, oder sobald das Ende des Textes erreicht ist.
Beobachtungen
- Der Text wird genau einmal durchlaufen.
- Der Algorithmus bewegt sich entweder im Text weiter nach rechts, oder er bleibt im Text stehen und verschiebt das Muster.
- Soll das Muster verschoben werden, und steht vor dem gerade überprüften Zeichen ein Präfix der Länge k, so wird das Muster so weit verschoben, dass die ersten k Zeichen nicht nochmals überprüft werden.
Präfix-Analyse
Um alle längsten Präfixe im Muster zu finden, wird vor der eigentlichen Suche das Muster analysiert.
Dazu schreibt man unter das erste Zeichen im Muster −1, und unter jedes weitere Zeichen die Anzahl der direkt vorangegangenen Zeichen, die ein Präfix des Musters bilden, ohne am Anfang des Musters zu beginnen.
Wir bearbeiten als Beispiel wieder das Muster „ababcabab“:
| Muster | Wert | Bemerkung |
|---|---|---|
| a | −1 | Sonderfall am Anfang des Musters. |
| b | 0 | Ohne am Anfang des Musters zu beginnen, gibt es keine vorangehenden Zeichen. |
| a | 0 | Die vorangehenden Zeichen, ohne am Anfang des Musters zu beginnen, sind „b“. Dies ist kein Präfix des Musters. |
| b | 1 | Die vorangehenden Zeichen, ohne am Anfang des Musters zu beginnen, sind „ba“. Nur das „a“ ist auch Präfix des Musters. |
| c | 2 | Die vorangehenden Zeichen, ohne am Anfang des Musters zu beginnen, sind „bab“. Nur das „ab“ ist auch Präfix des Musters. |
| a | 0 | Die vorangehenden Zeichen, ohne am Anfang des Musters zu beginnen, sind „babc“. Das Präfix „ab“ ist zwar enthalten, steht jedoch wegen des „c“s nicht direkt vor diesem „a“. |
| b | 1 | Die vorangehenden Zeichen, ohne am Anfang des Musters zu beginnen, sind „babca“. Nur das „a“ ist auch Präfix des Musters. |
| a | 2 | Die vorangehenden Zeichen, ohne am Anfang des Musters zu beginnen, sind „babcab“. Nur das „ab“ ist auch Präfix des Musters. |
| b | 3 | Die vorangehenden Zeichen, ohne am Anfang des Musters zu beginnen, sind „babcaba“. Nur das „aba“ ist auch Präfix des Musters. |
| 4 | Die letzten Zeichen des Musters, ohne am Anfang zu beginnen, sind „babcabab“. Nur das „abab“ ist auch Präfix des Musters. |
So ergibt sich für das Muster „ababcabab“ die folgende Präfix-Tabelle. Beachte, dass die letzte Zeile der Tabelle um ein Feld länger ist als das Muster.
| Position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Muster: | a | b | a | b | c | a | b | a | b | |
| Wert: | −1 | 0 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 4 |
Zum Vergleich obige Tabelle:
| Länge | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| Muster: | a | b | a | b | c | a | b | a | b | 9 |
| Präfix (0..0): | 0 | |||||||||
| Präfix (0..1): | 0 | |||||||||
| Präfix (0..2): | a | a | 1 | |||||||
| Präfix (0..3): | a | b | a | b | 2 | |||||
| Präfix (0..4): | 0 | |||||||||
| Präfix (0..5): | a | a | 1 | |||||||
| Präfix (0..6): | a | b | a | b | 2 | |||||
| Präfix (0..7): | a | b | a | a | b | a | 3 | |||
| Präfix (0..8): | a | b | a | b | a | b | a | b | 4 |
Implementierung
Es folgt der Algorithmus beschrieben in Pseudocode.
Eingabe seien
- ein Text t der Länge m, und
- ein Muster w der Länge n.
Für jedes Vorkommen des Musters w im Text t soll die Anfangsposition des Wortes im Text ausgegeben werden.
Wir fassen Muster und Text als Array auf, die beginnend mit Null nummeriert sind. Also ist z. B. w[0] das erste Zeichen des Musters, und t[8] das neunte Zeichen des Textes. Es ist übliche Praxis, die Nummerierung mit 0 zu beginnen.
Präfix-Analyse
Zunächst wird die Präfix-Analyse durchgeführt. Sie erstellt die oben besprochene Präfix-Tabelle, hier nur die letzte Zeile als Array N, die für jedes Zeichen des Musters die Länge des direkt vorhergehenden Präfixes enthält.
Eingabe ist
- ein Muster w der Länge n.
Ausgabe ist
- das Array N der Länge n+1.
in Pseudocode:
i := 0 // Variable i zeigt immer auf die aktuelle Position
j := -1 // im Muster, Variable j gibt die Länge des gefun-
// denen Präfixes an.
N[i] := j // Der erste Wert ist immer -1
while i < n // solange das Ende des Musters nicht erreicht ist
|
| while j >= 0 and w[j] != w[i] // Falls sich ein gefundenes
| | // Präfix nicht verlängern lässt,
| | j := N[j] // nach einem kürzeren suchen.
| |
| end
|
| // an dieser Stelle ist j=-1 oder w[i]=w[j]
|
| i := i+1 // Unter dem nächsten Zeichen im Muster
| j := j+1 // den gefundenen Wert (mindestens 0)
| N[i] := j // in die Präfix-Tabelle eintragen.
|
end
Derselbe Code in Python:
def prefix(muster, laenge):
# Laenge des gefundenen Prefix
laengePrefix = -1
# Der erste Wert ist immer -1
prefixTabelle = [laengePrefix]
# solange das Ende des Musters nicht erreicht ist
for positionImMuster in range(0, laenge):
# solange sich ein gefundenes Prefix nicht verlaengern laesst, nach einem kuerzeren suchen
while laengePrefix >= 0 and muster[laengePrefix] != muster[positionImMuster]:
laengePrefix = prefixTabelle[laengePrefix]
# an dieser Stelle ist laengePrefix == -1 oder muster[positionImMuster] == muster[leangePrefix]
laengePrefix = laengePrefix + 1
# den gefundenen Wert an die prefixTabelle anhaengen
prefixTabelle.append(laengePrefix)
return prefixTabelle
Suche
Die zweite Phase ist die Suche. Da das Muster natürlich nicht wirklich unter den Text geschrieben und dann verschoben wird, werden zwei Variablen i und j eingesetzt. Dabei gibt i die aktuelle Position im Text, und j die aktuelle Position im Muster an. Die Bedeutung ist, dass immer Stelle j des Musters „unter“ Stelle i des Textes steht.
| i: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | … |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text: | a | b | a | b | a | b | c | b | a | b | a | b | c | a | b | a | b | c | a | b | … |
| Muster: | a | b | a | b | c | a | b | a | b | ||||||||||||
| j: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Eingabe sind
- das Muster w der Länge n,
- das Array N der Länge n+1 aus der ersten Phase, und
- ein Text t der Länge m.
Ausgabe sind
- alle Positionen an denen w in t vorkommt.
i := 0 // Variable i zeigt immer auf die aktuelle Position im Text.
j := 0 // Variable j auf die aktuelle Position im Muster.
while i < m // also Textende nicht erreicht
|
| while j >= 0 and t[i] != w[j] // Muster verschieben, bis
| | // Text und Muster an Stelle
| | j := N[j] // i,j übereinstimmen. Dabei
| | // Array N benutzen.
| end
|
| i := i + 1 // In Text und Muster je eine
| j := j + 1 // Stelle weitergehen.
|
| if j == n then /// Ist das Ende des Musters erreicht
| | // einen Treffer melden. Dieser begann
| | print i - n // bereits n Zeichen früher.
| |
| | j := N[j] // Muster verschieben.
| |
| end if
|
end
Derselbe Code in Python:
def suche(muster, prefixTabelle, text):
positionImMuster = 0
musterLaenge = len(muster)
# solange das Ende des Textes nicht erreicht ist
for positionImText in range(0, len(text)):
# Muster verschieben bis Text und Muster an Stelle (positionImText, positionImMuster) uebereinstimmen
while positionImMuster >= 0 and text[positionImText] != muster[positionImMuster]:
# Dazu wird die Prefix-Tabelle verwendet
positionImMuster = prefixTabelle[positionImMuster]
positionImMuster = positionImMuster + 1
# falls das Ende des Musters erreicht ist
if positionImMuster == musterLaenge:
# einen Treffer melden. Der Treffer beginnt bereits musterLaenge-1 Zeichen frueher.
print(positionImText - musterLaenge + 1)
# Muster verschieben
positionImMuster = prefixTabelle[positionImMuster]
Laufzeitanalyse
Die Laufzeit wird, wie üblich, in der Landau-Notation angegeben.
Laufzeit der Präfix-Analyse
Die äußere while-Schleife wird höchstens n-mal durchlaufen, da am Anfang i=0 gilt und i bei jedem Schritt um 1 erhöht wird.
In der inneren while-Schleife wird bei jedem Durchlauf j auf einen zuvor berechneten, kleineren Wert von j, gespeichert in N[j], gesetzt. Diese Schleife wird also insgesamt höchstens so oft durchlaufen wie j erhöht wurde. Da j nur in der äußeren Schleife erhöht wird, wird die innere Schleife insgesamt höchstens n-mal durchlaufen.
Allerdings muss auch das ganze Muster durchlaufen werden. Deshalb ist die Laufzeit der Präfix-Analyse also in .
Laufzeit der Suche
Die äußere while-Schleife wird höchstens m-mal durchlaufen, da am Anfang i=0 gilt, und i bei jedem Schritt um 1 erhöht wird.
Analog zur Phase der Präfix-Analyse, wird auch die innere while-Schleife insgesamt höchstens m-mal durchlaufen.
Da auch hier der gesamte Text durchlaufen wird, ist die Laufzeit in .
Zusammen
Da Präfix-Analyse und Suche nacheinander ausgeführt werden, ist die Laufzeit des gesamten Algorithmus in . Insgesamt werden höchstens Vergleiche zwischen Zeichen des Musters und des Textes durchgeführt.
Damit kann der Algorithmus von Knuth, Morris und Pratt eine bessere worst-case-Laufzeit garantieren als der Algorithmus von Boyer und Moore mit .
Allerdings kann Boyer-Moore eine Suche unter bestimmten Umständen in durchführen, Knuth-Morris-Pratt benötigt immer linear viele Vergleiche.
Siehe auch
Literatur
- D. E. Knuth, J. H. Morris, V. R. Pratt (1977): Fast Pattern Matching in Strings. In: SIAM Journal of Computing. 6 (2): 323–350. doi:10.1137/0206024
- Yu. V. Matiyasevich: Real-time recognition of the inclusion relation. In: Journal of Soviet Mathematics. Band 1, Nr. 1, 1973, S. 64–70, doi:10.1007/BF01117471.
Weblinks
- Eine ausführlichere Erklärung bei der Hochschule Flensburg
- Christian Charras, Thierry Lecroq: Knuth-Morris-Pratt algorithm, Université de Rouen auf der Webseite www-igm.univ-mlv.fr (englisch)
- University of British Columbia: Knuth-Morris-Pratt String Search, Webseite zur Visualisierung von Knuth-Morris-Pratt (englisch)
- Download auf SourceForge: j-Algo - Programm zur anschaulichen Visualisierung
