Welcher exakte String-Matching-Algorithmus ist der schnellste?

Dies hängt von der Eingabe ab. Knuth-Morris-Pratt garantiert eine lineare Worst-Case-Laufzeit; Boyer-Moore ist in der Praxis bei natürlichem Text oft am schnellsten, da er Zeichen überspringt und im Durchschnitt sublinear läuft; Rabin-Karp glänzt bei der Suche nach vielen Mustern oder bei Fingerabdruckvergleichen. Es gibt keinen einzigen universellen Gewinner.

Wie vermeidet Rabin-Karp den Vergleich jedes Zeichens an jeder Position?

Es hasht das Muster und jedes Textfenster derselben Länge unter Verwendung eines Rolling Hash, der sich in konstanter Zeit aktualisiert, wenn das Fenster verschoben wird. Nur wenn die Hashes übereinstimmen, werden die tatsächlichen Zeichen überprüft, sodass die meisten nicht übereinstimmenden Positionen durch einen einzigen kostengünstigen Vergleich abgelehnt werden.

String-Matching

String-Matching findet alle Vorkommen eines Musters innerhalb eines Textes; klassische Algorithmen verarbeiten das Muster vor, um redundante Vergleiche zu überspringen und eine lineare oder sublineare Suchzeit zu erreichen.

Thema finden mit PaperMindDemnächstFind papers & topics

Tools & resources

Folien herunterladen

Learn & explore

VideoDemnächst

Definition

String-Matching ist das Problem, alle Positionen in einem Text zu finden, an denen eine gegebene Musterzeichenkette vorkommt; ein exakter String-Matching-Algorithmus meldet jeden Offset, an dem das Muster identisch mit einem Teilstring des Textes übereinstimmt.

Scope

Dieses Thema behandelt exakte Algorithmen zum Abgleich einzelner Muster – die naive Methode, Knuth-Morris-Pratt, Boyer-Moore und den Hashing-basierten Rabin-Karp-Algorithmus – zusammen mit der Vorverarbeitung (Fehlerfunktionen, Verschiebetabellen, Rolling Hashes), die sie effizient macht, und die Erweiterung auf den Abgleich mehrerer Muster mittels des Aho-Corasick-Automaten. Approximatives Matching und indexbasierte Suche werden in verwandten Themen behandelt.

Core questions

Warum benötigt naives Matching eine Zeit, die proportional zum Produkt der Muster- und Textlängen ist?
Wie vermeidet die Vorverarbeitung des Musters eine erneute Untersuchung von Textzeichen?
Wie funktionieren die Knuth-Morris-Pratt-Fehlerfunktion und die Boyer-Moore-Verschiebungsregeln?
Wie verwendet Rabin-Karp Hashing, um Ausrichtungen schnell zu testen?
Wie wird das Matching auf viele Muster gleichzeitig erweitert?

Key concepts

naives Matching
Knuth-Morris-Pratt-Algorithmus
Fehlerfunktion
Boyer-Moore-Algorithmus
Bad-Character- und Good-Suffix-Regeln
Rabin-Karp-Algorithmus
Rolling Hash
Aho-Corasick-Automat

Key theories

Knuth-Morris-Pratt-Fehlerfunktion: Durch die Vorberechnung des längsten echten Präfixes, das auch ein Suffix ist, für jedes Musterpräfix, verschiebt der Knuth-Morris-Pratt-Algorithmus das Muster nach einer Nichtübereinstimmung intelligent und untersucht Textzeichen niemals erneut, was ein Matching in linearer Zeit ermöglicht.
Boyer-Moore-Rechts-nach-links-Scan: Boyer-Moore vergleicht das Muster vom letzten Zeichen rückwärts und verwendet Bad-Character- und Good-Suffix-Regeln, um große Teile des Textes zu überspringen, wodurch eine sublineare durchschnittliche Leistung bei typischen Eingaben erreicht wird.

Clinical relevance

String-Matching ist die Grundlage alltäglicher Werkzeuge und Infrastrukturen: die Suche in Texteditoren und Kommandozeilenprogrammen, Inhaltsfilterung und Signaturscans zur Intrusion Detection, Plagiatserkennung und die Lokalisierung von Motiven in biologischen Sequenzen. Der Abgleich mehrerer Muster skaliert diese auf Dictionaries vieler Muster gleichzeitig.

History

Der Knuth-Morris-Pratt-Algorithmus (1977 veröffentlicht, früher entwickelt) lieferte den ersten weithin bekannten exakten Matcher mit linearer Laufzeit, und Boyer und Moore (1977) führten im selben Jahr das sublineare Matching im Durchschnittsfall ein. Rabins und Karps Hashing-Ansatz und der Aho-Corasick-Multi-Muster-Automat (1975) erweiterten das Feld zusätzlich.

Key figures

Donald Knuth
James H. Morris
Vaughan Pratt
Robert Boyer
J Strother Moore
Michael Rabin
Richard Karp

Seminal works

knuth1977
boyer1977
cormen2009

Frequently asked questions

Welcher exakte String-Matching-Algorithmus ist der schnellste?: Dies hängt von der Eingabe ab. Knuth-Morris-Pratt garantiert eine lineare Worst-Case-Laufzeit; Boyer-Moore ist in der Praxis bei natürlichem Text oft am schnellsten, da er Zeichen überspringt und im Durchschnitt sublinear läuft; Rabin-Karp glänzt bei der Suche nach vielen Mustern oder bei Fingerabdruckvergleichen. Es gibt keinen einzigen universellen Gewinner.
Wie vermeidet Rabin-Karp den Vergleich jedes Zeichens an jeder Position?: Es hasht das Muster und jedes Textfenster derselben Länge unter Verwendung eines Rolling Hash, der sich in konstanter Zeit aktualisiert, wenn das Fenster verschoben wird. Nur wenn die Hashes übereinstimmen, werden die tatsächlichen Zeichen überprüft, sodass die meisten nicht übereinstimmenden Positionen durch einen einzigen kostengünstigen Vergleich abgelehnt werden.