Rabin-Karp-Algorithmus

Der Rabin-Karp-Algorithmus ist ein Suchalgorithmus für Texte, der von Michael O. Rabin und Richard M. Karp entwickelt wurde.^[1] Der Algorithmus sucht nach einem Muster, z. B. einer Zeichenkette, innerhalb einer anderen Zeichenkette mit Hilfe von Hash-Werten. In der Einzelmustererkennung ist der Algorithmus nicht weit verbreitet, allerdings ist er von beachtlicher theoretischer Bedeutung und sehr effektiv, um ein Muster mehrfach in einem Text zu suchen. Für einen Text der Länge n und ein Muster der Länge m ist seine durchschnittliche und beste Laufzeit O(n), die (sehr untypische) Laufzeit im schlechtesten Fall (Worst-Case-Laufzeit) beträgt allerdings O(nm). Dies ist einer der Gründe, weshalb der Algorithmus nicht oft benutzt wird. Trotzdem hat er den einzigartigen Vorteil, beliebig viele Zeichenketten in einem Durchlauf im Durchschnitt in O(n) oder weniger zu finden.

Eine der einfachsten praktischen Anwendungen von Rabin-Karp ist die Erkennung von Plagiaten: Nehmen wir als Beispiel einen Studenten, der ein Referat über Moby Dick schreibt. Eine Professorin könnte aus verschiedenen Quellen zum Thema Moby Dick automatisiert eine Liste aller Sätze erstellen. Rabin-Karp könnte nun schnell das abgegebene Schriftstück durchsuchen und jedes Vorkommen eines der Sätze des Quellmaterials finden. Um das einfache Ausbremsen des Systems mit kleinen Änderungen an den Originalquellen zu vermeiden, können Details, wie z. B. die Zeichensetzung, vorher entfernt und damit ignoriert werden. Aufgrund der Anzahl der gesuchten Zeichenketten wären in diesem Fall Einzel-Zeichenketten-Such-Algorithmen unpraktisch.

1. ↑ Karp and Rabin’s original paper: Karp, Richard M.; Rabin, Michael O. (March 1987). „Efficient randomized pattern-matching algorithms“. IBM Journal of Research and Development 31 (2), 249–260 doi:10.1147/rd.312.0249.