Algorithmus von Knuth-Morris-Pratt

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

Im Gegensatz zum Naiven Algorithmus wird das Muster, vor Beginn der eigentlichen Suche, ab der Position 1 auf Zeichenfolgen untersucht, 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

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

  1. die Präfix-Analyse, die das Muster selbst analysiert, und
  2. 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

  1. Der Text wird genau einmal durchlaufen.
  2. Der Algorithmus bewegt sich entweder im Text weiter nach rechts, oder er bleibt im Text stehen und verschiebt das Muster.
  3. 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.
|
done

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.

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

Siehe auch


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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,… …   Deutsch Wikipedia

  • String-Matching-Algorithmus — Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf… …   Deutsch Wikipedia

  • Karp-Rabin-Algorithmus — Der Rabin Karp Algorithmus ist ein Suchalgorithmus für Texte, der von Michael O. Rabin und Richard M. Karp entwickelt wurde. Der Algorithmus sucht nach einem Muster, z. B. einer Zeichenkette, innerhalb einer anderen Zeichenkette mit Hilfe von… …   Deutsch Wikipedia

  • Don Knuth — Donald Knuth Donald Ervin Knuth [kəˈnuːθ][1] (* 10. Januar 1938 in Milwaukee, Wisconsin) ist emeritierter Professor für Informatik an der Stanford University u …   Deutsch Wikipedia

  • Donald E. Knuth — Donald Knuth Donald Ervin Knuth [kəˈnuːθ][1] (* 10. Januar 1938 in Milwaukee, Wisconsin) ist emeritierter Professor für Informatik an der Stanford University u …   Deutsch Wikipedia

  • Donald Knuth — Donald Ervin Knuth [kəˈnuːθ][1] (* 10. Januar 1938 in Milwaukee, Wisconsin) ist emeritierter Professor für Informatik an der Stanford University u …   Deutsch Wikipedia

  • Donald Ervin Knuth — [kəˈnuːθ][1] (* 10. Januar 1938 in Milwaukee, Wisconsin) ist emeritierter Professor für Informatik an der Stanford University, Autor des Standardwerkes The Art of Computer Programming und Urvater des Textsatzsystems TeX …   Deutsch Wikipedia

  • Rabin-Karp-Algorithmus — Der Rabin Karp Algorithmus ist ein Suchalgorithmus für Texte, der von Michael O. Rabin und Richard M. Karp entwickelt wurde. Der Algorithmus sucht nach einem Muster, z. B. einer Zeichenkette, innerhalb einer anderen Zeichenkette mit Hilfe von… …   Deutsch Wikipedia

  • Liste von Algorithmen — Dies ist eine Liste von Artikeln zu Algorithmen in der deutschsprachigen Wikipedia. Siehe auch unter Datenstruktur für eine Liste von Datenstrukturen. Inhaltsverzeichnis 1 Klassen von Algorithmen nach Komplexität 2 Klassen von Algorithmen nach… …   Deutsch Wikipedia

  • Boyer-Moore-Algorithmus — Der Boyer Moore Algorithmus ist ein String Matching Algorithmus. Der Algorithmus wird dazu genutzt, um in einem Text T einen bestimmten Teiltext (Muster M) zu finden und wurde 1977 von Robert S. Boyer und J Strother Moore entwickelt.… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”