Benutzer:Mikyra/ Gemeinfrei/ KMP-Algorithmus

Der Inhalt des Dokuments ist zusätzlich freigegeben unter WTFPL.

Problemstellung

Bevor es daran geht, nach konkreten Alternativen für das Suchen von Strings Ausschau zu halten, ist es eine gute Idee, das gestellte Problem erst einmal genau zu beschreiben.

Gesucht ist ein Algorithmus, der die folgenden Forderungen erfüllt.

Eingabe:

eine Zeichenkette pattern der Länge m
eine Zeichenkette text der Länge n

Ausgabe:

falls die Zeichenkette text den Teilstring pattern enthält:
der kleinste Index $i\in 0\ldots n-1$ mit der Eigenschaft: text[i+j] == pattern[j] für $j=0\ldots m-1$
sonst -1

Beobachtung

Solange alle Zeichen des Musters mit dem Text übereinstimmen, gibt es im Vergleich zum naiven Algorithmus keine Verbesserungsmöglichkeit. Muster und Text müssen an jeder Stelle Zeichen für Zeichen verglichen werden.

Betrachten wir deshalb die Situation, an der ein Zeichen des Musters nicht mehr mit dem Text übereinstimmt. Um besser über die Situation sprechen zu können, wählen wir dabei folgende Bezeichnungen:

Das Muster wurde an der Stelle P angelegt.
Von dort aus haben j Zeichen des Musters mit dem Text übereingestimmt.
Erst an der Stelle T stimmen Text und Muster nicht mehr überein.

			$P$					$T$
text	...	b	a	n	a	n	a	n	a	s	...
pattern			a	n	a	n	a	s
			$\longleftarrow j\longrightarrow$

Die naive Implementierung legt das Muster an der Stelle P+1 an und setzt die Suche von dort aus fort. Die Information, dass bis hierhin bereits j Zeichen des Musters mit dem Text übereingestimmt haben, wird dabei nicht genutzt. Genau an diesem Punkt setzt die Idee des KMP-Algorithmus an. Von zentraler Bedeutung ist dabei die folgende Beobachtung:

Wenn das Muster noch vor der Stelle T passt, dann müssen sich Anfang und Ende der ersten j Zeichen des Musters, die bereits gepasst haben "überlappen". Formal formuliert müssen die ersten j Zeichen des Musters ein echtes Suffix enthalten, dass zugleich Präfix des Musters ist.

		Suffix
a	n	a	n	a
		a	n	a	n	a
		Präfix

Die erste Stelle, an der das Muster frühestens passen kann, ist somit durch die Länge des längsten echten Suffix gegeben, das zugleich Präfix des Musters ist. Diese Länge hängt nicht vom durchsuchten Text ab, sondern nur vom Muster.

Für jedes $j\in 1\ldots n$ kann die Länge $\pi (j)$ des längsten echten Suffix, das zugleich Präfix ist, also vorberechnet werden. Ein Beispiel für das Muster "ananas":

j	1	2	3	4	5	6
π(j)	0	0	1	2	3	0

Um die Berechnung der Tabelle werden wir uns später kümmern. Zunächst wird es darum gehen, einen Suchalgorithmus zu schreiben, der mit einer solchen Tabelle arbeitet.

KMP Algorithmus

Der KMP Algorithmus wurde erstmals 1977 von Donald E. Knuth, James H. Morris Jr. und Vaughan R. Pratt veröffentlicht.^[1] Er kann auf verschiedene Weise implementiert werden.

Bei der Arbeit mit entsprechender Fachliteratur ist darauf zu achten, dass die Indizes von Arrays in der Programmiersprache C bei 0 beginnen. Die Literatur arbeitet häufig mit Arrays, bei denen die Zählung erst mit dem Wert 1 beginnt.

Algorithmus: Suche mit Präfix-Tabelle

Als Eingabe stehen dem Algorithmus folgende Daten zur Verfügung:

Der Text liegt im Array text der Länge n vor.
Das Muster liegt im Array pattern der Länge m vor.
Zudem steht die Tabelle pi zur Verfügung.

Für die Formulierung des Algorithmus werden zwei weitere Variablen verwendet:

Die Variable i gibt die Position im Text an.
Die Variable j gibt die Anzahl Zeichen an, in denen Text und Muster vor der Position i übereinstimmen

		$i$
text
pattern
	$\longleftarrow j\longrightarrow$

Es folgt die Beschreibung der Arbeitsschritte des Algorithmus:

Zu Beginn wurde noch kein Zeichen des Musters mit dem Text verglichen. Der Zähler j wird mit dem Wert 0 initialisiert. Der Text wird nun beginnend vom Anfang bis zum Ende von links nach rechts durchlaufen.

int j = 0
for (int i=0; i<n; ++i) {

In jedem Schritt: Prüfe ob text[i] != pattern[j] ist. Solange es noch Zeichen gibt, die zwischen Text und Muster übereinstimmen, also j > 0, gibt es eine Chance, ein echtes Suffix zu finden. Der jeweils nächste Kandidat kann der Tabelle pi entnommen werden. Bei einem Treffer brechen wir ab:

   while ( (j > 0) && (text[i] != pattern[j]) )
      j = pi[j];

Nun sind entweder text[i] und pattern[j] identisch, oder es wurden alle Möglichkeiten erschöpft. Falls text[i] und pattern[j] identisch sind, so hat sich die Zahl der Zeichen, die zwischen Muster und Text übereinstimmen, um eins erhöht.

   if (text[i] == pattern[j])
      j += 1;

Eventuell haben wir damit bereits das letzte fehlende Zeichen für einen vollständigen Treffer erreicht. Der Index, ab dem Text und Muster übereinstimmen, kann dann berechnet und ausgegeben werden.

   if (j==m)
      return i - (j-1)

Falls kein vollständiger Treffer erzielt wurde, setzten wir die Suche im nächsten Schleifendurchlauf fort.

Quellcode

Zwecks besser Übersicht hier der vollständige Quelltext des Algorithmus in einem Stück:

int kmp_find(char pattern[], int m, char text[], int n, int pi[]) {

   int j = 0; // passende Zeichen bisher

   for (int i=0; i<n; ++i) {                         // Schleife {1}
      while ( (j > 0) && (text[i] != pattern[j]) )   // Schleife {2}
         j = pi[j];
      if (text[i] == pattern[j])
         j += 1;
      if (j == m) {
         return i - (j-1);
      }
   }
   return -1 // kein Treffer gefunden
}

Laufzeitanlyse

Auf den ersten Blick scheint nicht klar, ob im Vergleich zum naiven Algorithmus tatsächlich eine Verbesserung erzielt wurde. Die äußere Schleife {1} durchläuft den Text zwar in n Schritten. In jedem Durchlauf von Schleife {1} wird aber zudem auch die Schleife {2} einmal durchlaufen.

Hier ist es hilfreich, die Durchläufe von Schleife {2} nicht je Durchlauf der äußeren Scheife {1} zu betrachten, sondern in Summe über alle Durchläufe der äußeren Schleife {1}. Die Position, an der das Muster an den Text angelegt wird, wird in jedem Durchlauf der Schleife {2} um mindestens eine Position nach rechts verschoben. Maximal kann sie dabei an n Positionen des Texts angelegt werden.

Die Bilanz aus äußerer Schleife {1} und innerer Schleife {2} liefert somit maximal $2\cdot n$ Operationen. Die Laufzeit des Algorithmus liegt somit bei $O(n)$ . Eine Antwort auf die Frage, ob wir im Vergleich zum naiven Algorithmus etwas gewonnen haben, oder nicht, steht und fällt mit der Frage, wie teuer uns die Vorberechnung der Tabelle pi zu stehen kommt.

Präfix-Tabelle

Es bleibt zu zeigen, dass die benötigten Werte $\pi (i)$ der Präfix-Tabelle für $i=1\ldots m$ in "vernünftiger" Zeit berechnet werden können:

Die "Berechnung" von $\pi (1)$ ist trivial. Eine Zeichenkette der Länge 1 hat kein echtes Suffix. Es ist also immer $\pi (1)=0$ Die restlichen Werte können wir sukzessive berechnen, indem wir in jedem Schritt $i\rightarrow i+1$ versuchen das längste echte Suffix des Präfix der Länge $i$ um ein Zeichen zu verlängern.

	$\longleftarrow \;\;\;i\;\;\;\longrightarrow$
pattern
pattern
		$\leftarrow \pi (i)\rightarrow$

Stimmen die Zeichen $pattern[i]$ und $pattern[\pi (i)]$ nicht überein, so kann das Suffix nicht verlängert werden. Wir müssen versuchen, das Muster an einer anderen Stelle anzulegen.

Weiter links passen kann es nicht, denn $\pi (i)$ war bereits maximal gewählt. Wenn es noch vor der aktuell untersuchten Stelle passt, dann müssen sich Anfang und Ende des Präfix der Länge $\pi (i)$ überlappen. Wir können also analog zum Such-Algorithmus verfahren. Die dafür benötigten Werte von $\pi (k)$ für alle $k=1\ldots i$ haben wir bereits berechnet.

Algorithmus: Berechnung Präfix-Tabelle

Als Eingabe steht dem Algorithmus zur Verfügung:

Das Muster liegt im Array pattern der Länge m vor.
Ein Array pi der Länge m+1, in dem die berechneten Werte gespeichert werden können.

Für die Formulierung des Algorithmus werden zwei weitere Variablen verwendet:

Die Variable i gibt die Länge des längsten Teilstrings des Musters an, dessen Wert pi[i] bereits bestimmt wurde.
Die Variable j gibt die aktuelle Länge des Suffix an, für das wir überprüfen, ob es fortgesetzt werden kann.

	$\longleftarrow \;\;\;i\;\;\;\longrightarrow$
pattern
pattern
		$\longleftarrow j\longrightarrow$

Der Algorithmus selbst kann analog zum Such-Algorithmus implementiert werden. Als einzige Besonderheit müssen wir darauf achten, am Ende jedes Durchlaufs der äußeren Schleife den berechneten Wert für $\pi (i+1)$ an entsprechender Stelle im Array pi abzulegen.

Quellcode

void kmp_prepare(char pattern[], int m, int pi[]) {
   
   int j = 0;
   pi[1] = 0; // String der Länge 1 hat kein echtes Suffix
   
   for (int i=1; i<m; ++i) {                        // Schleife {1}
      while ( (j>0) && (pattern[i] != pattern[j]) ) // Schleife {2}
         j = pi[j];
      if (pattern[i] == pattern[j])
         j += 1;
      pi[i+1] = j;
   }
}

Laufzeitanalyse

Die äußere Schleife {1} durchläuft das Muster in m Schritten. Analog zum Such-Algorithmus kann das Muster nur an m Positionen angelegt werden. Jeder Durchlauf der inneren Schleife {2} verschiebt die Position mindestens um eine Position nach rechts. Die Bilanz der Laufzeit aus äußerer Schleife {1} und innerer Schleife {2} liefert somit eine $O(m)$

Laufzeit

Die komplette Laufzeit für die Suche eines Musters der Länge $m$ in einem Text der Länge $n$ ergibt sich aus der Summe der Laufzeit für die Berechnung der Präfix-Tabelle und der Laufzeit der Suche mit der berechneten Präfix-Tabelle. Berechnung der Präfix-Tabelle benötigt eine Laufzeit von $O(m)$ . Suche mit der berechneten Tabelle benötigt eine Laufzeit von $O(n)$ . Die Laufzeit des KMP-Algorithmus liegt somit bei $O(m+n)$ .

Quellcode

Mit zwei Hilfsfunktionen dump_pi() und print_match() können wir die Arbeitsweise des Algorithmus überprüfen. Der zugehörige Quellcode findet sich hier:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void dump_pi(char pattern[], int m, int pi[]) {
   printf("\n\"%s\"\n", pattern);

   printf("j     ");
   for (int i=1; i<=m; ++i) {
      printf("%2d ", i);
   }
   printf("\n");
   
   printf("pi(j) ");
   for (int i=1; i<=m; ++i) {
      printf("%2d ", pi[i]);
   }
   printf("\n\n");
}

void kmp_prepare(char pattern[], int m, int pi[]) {
   
   int j = 0;
   pi[1] = 0; // String der Länge 1 hat kein echtes Suffix
   
   for (int i=1; i<m; ++i) {
      while ( (j>0) && (pattern[i] != pattern[j]) )
         j = pi[j];
      if (pattern[i] == pattern[j])
         j += 1;
      pi[i+1] = j;
   }
}

void print_match(char pattern[], char text[], int i) {
   printf("%s\n", text);
   printf("%*s%s\n", i, "", pattern);
}

void kmp_find(char pattern[], int m, char text[], int n, int pi[]) {

   int j = 0; // übereinstimmende Zeichen bisher

   for(int i=0; i<n; ++i) {
      while ( (j>0) && (text[i] != pattern[j]) )
         j = pi[j];
      if (text[i] == pattern[j])
         j += 1;
      if (j == m) {
         print_match(pattern, text, i-(j-1));
         j = pi[j];
      }
   }
}

int main(int argc, char* argv[]) {
   char pattern[] = "ababcabab";
   int m          = strlen(pattern);

   char text[]    = "abababcbababcababcabbababcababcab";
   int n          = strlen(text);

   int *pi        = malloc((m+1) * sizeof(int));
   
   kmp_prepare(pattern, m, pi);
   dump_pi(pattern, m, pi);

   kmp_find(pattern, m, text, n, pi);

   free(pi);
   return 0;
}

Nach dem Übersetzten liefert das Programm folgende Ausgabe:

 "ababcabab"
 j      1  2  3  4  5  6  7  8  9 
 pi(j)  0  0  1  2  0  1  2  3  4 
 
 abababcbababcababcabbababcababcab
         ababcabab
 abababcbababcababcabbababcababcab
                      ababcabab

Wir haben also tatsächlich alle Treffer im Text gefunden.

Fußnoten

↑ siehe: Donald E. Knuth, James H. Morris Jr., Vaughan R. Pratt: Fast Pattern Matching in Strings. In: SIAM Journal on Computing. Vol 6, Nr. 2, Juni 1977.

[1] siehe: Donald E. Knuth, James H. Morris Jr., Vaughan R. Pratt: Fast Pattern Matching in Strings. In: SIAM Journal on Computing. Vol 6, Nr. 2, Juni 1977.

[1]