Was ist der KMP-Algorithmus?

Der Knuth-Morris-Pratt-Algorithmus findet alle Vorkommen eines Musters in einem Text in linearer O(n+m)-Zeit, indem er eine Fehlerfunktion vorab berechnet, sodass sich der Textzeiger nie rückwärts bewegt.

Warum bewegt sich der Textzeiger nie zurück?

Bei einer Fehlanpassung sagt die Fehlerfunktion KMP, wie viel des Musters bereits als Präfix übereinstimmte, sodass das Muster verschoben statt der Text zurückgespult wird. Jedes Textzeichen wird höchstens eine konstante Anzahl von Malen untersucht.

Wie ist KMP schneller als die naive Suche?

Die naive Suche kann Zeichen nach jeder Verschiebung erneut vergleichen, was im schlechtesten Fall O(n*m) ergibt. KMP nutzt Informationen aus vorherigen Vergleichen wieder und erreicht O(n+m).

Wie wird die Fehlerfunktion berechnet?

Sie wird aufgebaut, indem das Muster mit sich selbst abgeglichen wird: Ein Zeiger verfolgt die aktuelle Präfixlänge, verlängert sie bei einer Übereinstimmung und fällt bei einer Fehlanpassung auf frühere Fehlerwerte zurück — alles in O(m) Zeit.

Wie hoch ist die Zeit- und Platzkomplexität?

KMP läuft in O(n+m) Zeit, wobei n die Textlänge und m die Musterlänge ist, und benötigt O(m) zusätzlichen Speicher für die Fehlertabelle.

Kann KMP überlappende Treffer finden?

Ja. Nach einer vollständigen Übereinstimmung nutzt es den Fehlerwert der letzten Musterposition, um fortzufahren, sodass überlappende Vorkommen wie AA in AAAA alle gemeldet werden.

Wo wird KMP eingesetzt?

Texteditoren, grep-artige Suche, Einbruchserkennung, Bioinformatik und Netzwerkpaketprüfung nutzen KMP oder verwandte linearzeitige Suchalgorithmen.

Wie schneidet KMP im Vergleich zu Boyer-Moore ab?

Boyer-Moore durchsucht das Muster von rechts nach links und kann große Abschnitte überspringen, was in der Praxis oft schneller ist, während KMP eine strikte lineare Grenze garantiert und den Textzeiger nie rückwärts bewegt.

Was passiert, wenn das Muster leer ist?

Ein leeres Muster passt per Konvention an jeder Position. Diese Simulation erwartet ein nicht leeres Muster, das kürzer oder gleich lang wie der Text ist, für eine sinnvolle Suche.

Startseite▸Algorithmen & KI▸KMP-Zeichenkettensuche — Fehlerfunktion

🔎 KMP-Zeichenkettensuche — Fehlerfunktion

Knuth-Morris-Pratt durchsucht Text in O(n+m): Eine Präfix-Fehlerfunktion lässt das Muster vorwärts gleiten, ohne bereits abgeglichene Zeichen erneut zu prüfen. Beobachten Sie, wie der Zeiger nie zurückspringt.

Algorithmen & KI3DMittel60 FPS

Über die KMP-Zeichenkettensuche

Der Knuth-Morris-Pratt-Algorithmus (KMP) löst das Problem der Zeichenkettensuche — das Finden aller Vorkommen eines Musters P der Länge m innerhalb eines Textes T der Länge n — in O(n + m) Zeit, verglichen mit dem naiven Worst-Case von O(mn). Die zentrale Erkenntnis, veröffentlicht 1977 von Donald Knuth, Vaughan Pratt und James Morris, ist die Fehlerfunktion (auch Präfixfunktion genannt): eine vorab berechnete Tabelle, die für jede Position im Muster die Länge des längsten echten Präfixes codiert, das auch ein Suffix ist. Tritt eine Fehlanpassung auf, nutzt der Algorithmus diese Tabelle, um das Muster vorwärts zu verschieben, ohne ein bereits verarbeitetes Textzeichen erneut zu untersuchen.

Die Simulation animiert zwei Zeiger — einen über dem Text und einen über dem Muster — und hebt übereinstimmende Zeichen grün und Fehlanpassungen rot hervor. Sie können sehen, wie die Fehlerfunktionstabelle aufgebaut wird, beobachten, wie das Muster bei einer Fehlanpassung vorwärts gleitet, und die Gesamtzahl der Zeichenvergleiche mit einem daneben angezeigten naiven Brute-Force-Zähler vergleichen.

Häufig gestellte Fragen

Warum ist KMP schneller als die naive Zeichenkettensuche?

Die naive Suche kann dieselben Textzeichen mehrfach untersuchen: Bei einem Text wie „AAAAAAB" mit Muster „AAAB" führt sie im schlechtesten Fall O(nm) Vergleiche durch. KMP vermeidet dies, indem der Textzeiger nie rückwärts bewegt wird; jedes Zeichen wird höchstens zweimal untersucht (einmal beim Aufbau der Fehlerfunktion, einmal bei der Suche), was eine feste O(n + m)-Garantie unabhängig von der Eingabe ergibt.

Was ist die Fehlerfunktion (Präfixfunktion)?

Für ein Muster P gibt die Fehlerfunktion π[i] die Länge des längsten echten Präfixes von P[0..i] an, das auch ein Suffix von P[0..i] ist. Zum Beispiel ist für das Muster „ABAB" π = [0, 0, 1, 2]. Tritt an Position i im Muster eine Fehlanpassung auf, setzt der Algorithmus i = π[i−1] statt auf 0 zurückzusetzen, sodass bereits abgeglichene Zeichen nicht erneut verglichen werden.

Wie hoch ist die Zeitkomplexität beim Aufbau der Fehlerfunktion?

Der Aufbau der Fehlertabelle benötigt O(m) Zeit und O(m) Speicher mittels eines Zwei-Zeiger-Durchlaufs des Musters selbst. Zusammen mit der O(n)-Suchphase ergibt sich eine Gesamtkomplexität von O(n + m). Der Beweis nutzt ein amortisiertes Argument: Obwohl die innere Schleife mehrfach durchlaufen kann, kann die Variable, die die Übereinstimmungslänge verfolgt, über die gesamte Suche hinweg nur n-mal ansteigen.

Wie geht KMP mit überlappenden Treffern um?

Wird an Position i im Text eine vollständige Übereinstimmung gefunden, setzt der Algorithmus den Musterzeiger auf π[m−1] statt auf 0, sodass sofort nach dem nächsten überlappenden Treffer gesucht werden kann. Zum Beispiel findet die Suche nach „ABA" in „ABABA" korrekt Treffer an den Positionen 0 und 2.

Ist KMP in der Praxis der schnellste Zeichenkettensuchalgorithmus?

Nicht immer. Während KMP die theoretische Grenze von O(n + m) erreicht, übertreffen Algorithmen wie Boyer-Moore-Horspool ihn in der Praxis oft, da sie mithilfe von Bad-Character- und Good-Suffix-Heuristiken viele Zeichen auf einmal überspringen können, was zu sublinearem Verhalten im Durchschnittsfall bei typischem englischem Text führt. KMP wird bevorzugt, wenn das Alphabet klein ist (z. B. DNA-Basen A/C/G/T) oder wenn ein Streaming-Eingabestrom kein Vorausschauen zulässt.

Wo wird KMP in echter Software eingesetzt?

KMP und verwandte Algorithmen werden in grep, Texteditoren, Bioinformatik-Tools (DNA-Sequenzabgleich), Systemen zur Netzwerk-Einbruchserkennung (Mustersuche in Paket-Nutzdaten) und beim Scannen von Antiviren-Signaturen eingesetzt. Der Linux-Kernel verwendet eine Variante zur Zeichenkettensuche in Kernelmodulen.

Was ist der Unterschied zwischen KMP und dem Aho-Corasick-Algorithmus?

KMP sucht ein einzelnes Muster in linearer Zeit. Aho-Corasick verallgemeinert dies, um gleichzeitig nach k Mustern in O(n + m₁ + … + mₖ + z) Zeit zu suchen (z = Gesamtzahl der Treffer), mithilfe eines aus allen Mustern aufgebauten endlichen Automaten. Es ist der Algorithmus hinter Werkzeugen wie fgrep und Systemen zur Netzwerkinhaltsprüfung.

Kann KMP Unicode-Text verarbeiten?

Ja, sofern Zeichen korrekt verglichen werden. KMP arbeitet auf Sequenzen von Tokens (Codepunkten oder Bytes), funktioniert also mit jedem Alphabet. Bei UTF-8-codiertem Text ist es üblich, mit Bytes zu arbeiten, doch in der Nähe von Mehrbyte-Zeichengrenzen ist Vorsicht geboten, um zu vermeiden, dass ein Codepunkt mitten in einem Treffer aufgeteilt wird.

Was ist der Z-Algorithmus, und wie hängt er mit KMP zusammen?

Der Z-Algorithmus berechnet für jede Position i in einer Zeichenkette die Länge des längsten bei i beginnenden Teilstrings, der auch ein Präfix der Zeichenkette ist. Er löst dasselbe Mustersuchproblem in O(n + m) Zeit, verwendet aber einen anderen Ansatz: Er verkettet P + $ + T und berechnet das Z-Array, dann findet er Treffer dort, wo Z[i] ≥ m ist. Viele Wettbewerbsprogrammierer bevorzugen Z-Arrays wegen ihrer konzeptionellen Einfachheit.

Warum bewegt sich der Textzeiger in KMP nie rückwärts?

Dies ist die zentrale Invariante des Algorithmus. Die Fehlerfunktion garantiert, dass bei einer Fehlanpassung an Musterposition i alle Informationen über die bereits gescannten Textzeichen in π[i−1] codiert sind. Es besteht daher nie die Notwendigkeit, ein bereits abgeglichenes Textzeichen erneut zu untersuchen, was die lineare Zeitgrenze ergibt.

⚙ Unter der Haube

KMPZeichenkettensucheFehlerfunktionPräfixtabelleCanvas 2D

3D · Three.js / WebGL-Renderer · 60 FPS-Ziel · läuft vollständig clientseitig, keine Installation nötig