EMZETT.
Login

Emzett Wiki

Textsuche-Algorithmen: naiv, KMP, Boyer-Moore und Rabin-Karp

Properties1
tagsglossar, algorithmen, strings

2 Min. Lesezeit

Textsuche-Algorithmen: naiv, KMP, Boyer-Moore und Rabin-Karp

Kurz: Um ein Muster in einem Text zu finden, vergleicht die naive Suche Stelle für Stelle; KMP, Boyer-Moore und Rabin-Karp nutzen Vorwissen über das Muster, um Vergleiche zu überspringen.

Genauer: Strg+F, grep, Editoren, Plagiatsprüfung, DNA-Suche: Überall wird ein Muster (Pattern, Länge m) in einem Text (Länge n) gesucht. Die richtige Methode hängt von Länge, Alphabet und Anzahl der Suchen ab.

Im Detail

Naiv

Muster an jeder Stelle des Textes anlegen und Zeichen vergleichen; bei Mismatch um eins verschieben.

def suche(text, muster):
    n, m = len(text), len(muster)
    return [i for i in range(n - m + 1) if text[i:i + m] == muster]

Worst Case O(n·m) (Text aaaa…a, Muster aaab); im Mittel bei natürlichem Text oft nahe O(n) und praktisch ausreichend (Pythons in, str.find nutzt optimierte Varianten).

Knuth-Morris-Pratt (KMP)

Berechnet vorher eine Tabelle (Präfix-/Fehlerfunktion): Wie lang ist der längste echte Präfix des Musters, der auch Suffix des bisher Gelesenen ist? Bei einem Mismatch springt man im Muster zurück, ohne den Text zurückzulesen. O(n + m), kein Zurückgehen im Text (gut für Datenströme). Beispiel Muster ABABC: Tabelle [0,0,1,2,0].

Boyer-Moore und Rabin-Karp

  • Boyer-Moore: vergleicht das Muster von hinten; mit Bad-Character- und Good-Suffix-Regel überspringt es oft ganze Stücke (im Mittel sublinear, besonders bei langen Mustern/großem Alphabet). Grundlage von grep und vielen Editoren (Horspool-Variante).
  • Rabin-Karp: berechnet Hashwerte (Rolling Hash) des Musters und jedes Textfensters; nur bei gleichem Hash wird verglichen. Mehrere Muster gleichzeitig, gut für Plagiatserkennung. Erwartet O(n + m), Worst Case O(n·m) bei vielen Hash-Kollisionen.
  • Aho-Corasick: sucht viele Muster parallel (Virenscanner, Wortfilter).
  • Suffixbäume/-arrays: viele Suchen im gleichen Text (Bioinformatik).

Praxis und Verwandtes

  • Reguläre Ausdrücke (siehe Regex) erweitern auf Muster mit Platzhaltern/Wiederholungen: realisiert über endliche Automaten.
  • Unscharfe Suche: Editierdistanz (Levenshtein), n-Gramme, Phonetik (Kölner Phonetik) für Tippfehler/Namen; Suchmaschinen (invertierter Index, Elasticsearch) für Dokumente.
  • Unicode/Groß-Kleinschreibung: Normalisieren (NFC), casefold.
  • Wahl: einmaliges Suchen → eingebaute Funktion; viele Suchen im selben Text → Index; viele Muster → Aho-Corasick; Streaming → KMP.
  • Prüfung: Ablauf von Hand an kleinem Beispiel zeigen, Laufzeiten vergleichen.

Siehe auch: Regex, Big-O-Notation, Hashmap, Bloom-Filter und Trie

Backlinks