- Knuth-Morris-Pratt-Algorithmus
-
Der Knuth-Morris-Pratt-Algorithmus wurde nach Donald Ervin Knuth, James Hiram Morris und Vaughan Ronald 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.
Inhaltsverzeichnis
Beschreibung
Der 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 ab der Position 1 auf Zeichenfolgen analysiert werden, die ein möglichst langes Präfix des Musters selbst sind.
So sind zum Beispiel im Muster „ababcabab“ die Zeichenketten „ab“ ab Position 2 und „abab“ ab Position 5 Präfixe des Musters.
Position: 0 1 2 3 4 5 6 7 8 Muster: a b a b c a b a b 1. Präfix: a 2. Präfix: a b 3. Präfix: a ... letztes Präfix: a b a b
Bei jeder teilweisen Übereinstimmung, etwa der ersten k Symbole, ist nun 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 dann 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. Allerdings steht an der Position 2 bis 3 im Muster das Präfix „ab“ des Musters. Da dieses auch gerade im Text gefunden wurde, wird das Muster so weit nach rechts verschoben, dass es sich mit dem gefundenen Präfix passend überlappt:
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 bei Position 4, also genau dort wo zuvor ein Fehler gefunden wurde, mit dem Vergleichen fort. Insbesondere wird das gefundene Präfix „ab“ nicht nochmal ü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 auf. Allerdings steht direkt vor dieser Stelle kein Präfix des Musters außer „ababc“ selbst. Deshalb kann das Muster bis unter die Stelle 7 im Text geschoben werden:
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, und der Algorithmus fährt an der nächsten Stelle im Text (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.
Präfix-Tabelle für „ababcabab“ 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:
Position: 0 1 2 3 4 5 6 7 8 Muster: a b a b c a b a b 1. Präfix: a 2. Präfix: a b 3. Präfix: a ... letztes Präfix: a b a b Implementierung
Der Algorithmus 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.
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. | | | done | | # 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. | doneSuche
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.
Beispiel für i=5 und j=3: 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. | done | | 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. | | | endif | done
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 Θ(n).
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 Θ(m).
Zusammen
Da Präfix-Analyse und Suche nacheinander ausgeführt werden, ist die Laufzeit des gesamten Algorithmus in Θ(n+m). Insgesamt werden höchstens 2(n+m) 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 O(m*n).
Allerdings kann Boyer-Moore eine Suche unter bestimmten Umständen in O(n/m) durchführen, Knuth-Morris-Pratt benötigt immer linear viele Vergleiche.
Literatur
- D. E. Knuth, J. H. Morris, V. R. Pratt: Fast Pattern Matching in Strings. In: SIAM Journal of Computing. 6, 2, 323-350 (1977)
Weblinks
- http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/kmp.htm
- http://www-igm.univ-mlv.fr/~lecroq/string/node8.html
- http://j-algo.binaervarianz.de/download.php Programm zur anschaulichen Visualisierung
Siehe auch
Wikimedia Foundation.
