Knuth-Morris-Pratt (Algorithmus 5.6)

So geht’s: Beim Öffnen läuft der Testlauf aus dem Buch: Muster AACAA im Text AABRAACADABRAACAADABRA. Teil 1, der Konstruktor: Spalte für Spalte entsteht die Tabelle dfa[c][j]. Hellblau sind die aus Spalte X kopierten Einträge (Nichtübereinstimmung), orange ist der neu gesetzte Übereinstimmungsfall, X selbst ist gestrichelt umrandet. Darüber wächst der Automat mit. Gerade Pfeile führen einen Zustand weiter, Bögen und Schleifen springen zurück, Übergänge nach 0 sind weggelassen. Teil 2, die Suche: Jedes Textzeichen schickt den Automaten in einen neuen Zustand. Der benutzte Übergang leuchtet blau, und unter dem Text stehen die Musterzeichen, die gerade passen. Am Ende wird das gefundene Stück grün. „ABABAC“ baut den Automaten aus Abbildung 5.39 und sucht damit in BCBAABACAABABACAA. Eigene Muster (bis 10 Zeichen) und Texte (bis 40) gibst du oben ein, „↺ Neu starten“ springt zurück zum Testlauf.

Erklärung

Knuth-Morris-Pratt-Teilstringsuche (Algorithmus 5.6), Klasse KMP. Abschnitt 5.3. Aufgabe: Ein Muster der Länge M in einem Text der Länge N finden, wie Strg+F.

Ausgangspunkt Brute Force: Muster an jeder Position anlegen und Zeichen für Zeichen vergleichen. Bei einem Fehlschlag eine Stelle weiter im Text und von vorn. Im schlimmsten Fall etwa N · M Vergleiche, und man muss im Text zurückspringen.

KMP-Idee: Bei einem Fehlschlag weiß man schon, welche Zeichen zuletzt im Text standen, nämlich die passenden Musterzeichen. Daraus lässt sich vorab berechnen, wie weit das Muster schon „angefangen“ sein kann. Der Text wird dadurch nie zurückgelesen, jedes Textzeichen genau einmal.

Umgesetzt als DEA (deterministischer endlicher Automat):

• Zustände 0 bis M. Zustand j heißt: Die ersten j Musterzeichen passen gerade.
• dfa[c][j]: In welchen Zustand geht es, wenn im Zustand j das Zeichen c gelesen wird?
• Zustand M erreicht → Muster gefunden.

Konstruktion im Konstruktor:

• dfa[pat.charAt(0)][0] = 1: Im Startzustand führt nur das erste Musterzeichen weiter.
• X ist der Neustartzustand: der Zustand, in dem der Automat wäre, wenn er das Muster ohne sein erstes Zeichen gelesen hätte (pat[1..j-1]).
• Für jede Position j:
  • Nichtübereinstimmung: alle Übergänge aus Spalte X kopieren. Bei einem falschen Zeichen verhält man sich so, als wäre man im Zustand X.
  • Übereinstimmung: dfa[pat[j]][j] = j + 1.
  • X weiterschalten: X = dfa[pat[j]][X].
• Kleines Beispiel für AACAA: Im Zustand 2 (AA gelesen) führt C zu 3. Ein weiteres A führt zu 2, weil von „AAA“ die letzten beiden A wieder als Anfang taugen. B führt zurück auf 0.

search(txt): Text Zeichen für Zeichen durch den Automaten schicken. Erreicht j den Wert M, ist das Muster bei i − M gefunden. Sonst wird N zurückgegeben (nicht gefunden).

Testlauf: Muster AACAA im Text AABRAACADABRAACAADABRA. Bei Position 4 steht AACAD, das scheitert am letzten Zeichen. Gefunden wird es bei Position 12. Der Automat musste dazu nie im Text zurück.

Satz N: KMP greift auf höchstens M + N Zeichen zu. Der Aufbau des Automaten kostet Zeit und Speicher proportional zu R · M. Den Faktor R kann man mit einer Variante ohne vollständige Tabelle loswerden (Übung).

Praxis:

• Theoretisch wichtig wegen der linearen Garantie im schlimmsten Fall.
• In der Praxis selten schneller als Brute Force, weil normale Texte und Muster kaum Selbstwiederholungen haben und Brute Force meist nach einem Zeichen abbricht.
• Echter Vorteil: kein Zurücksetzen im Text. Damit geht Suchen in einem Datenstrom, den man nicht puffern will oder kann.

Als Nächstes Boyer-Moore (Algorithmus 5.7), der das Muster von rechts nach links vergleicht und in der Praxis oft große Sprünge macht.

Kapitel 5 bisher:

• Algorithmus 5.1: LSD-Sortierverfahren [43]
• Algorithmus 5.2: MSD-Sortierverfahren [44]
• Algorithmus 5.3: 3-Wege-Quicksort für Strings [45]
• Algorithmus 5.4: Trie-Symboltabelle [46]
• Algorithmus 5.5: TST-Symboltabelle [47]
• Algorithmus 5.6: Knuth-Morris-Pratt [48]