Karp-Rabin-Algorithmus

Der Rabin-Karp-Algorithmus ist ein Suchalgorithmus für Texte, der von Michael O. Rabin und Richard M. Karp entwickelt wurde. 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. Ein Professor 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.

Andere Algorithmen zur Suche nach Teil-Zeichenketten

Das Grundproblem, auf das sich der Algorithmus bezieht, ist das Finden einer festen Zeichenkette der Länge m, Muster genannt, innerhalb einer Zeichenkette der Länge n. Ein Beispiel wäre das Finden des Wortes „Sonne“ in dem Satz „Hallo Sonnenschein im Tal der Tränen.“ Ein sehr einfacher Algorithmus (siehe nachfolgendes Listing) für diesen Fall würde einfach nach der Zeichenkette an allen möglichen Positionen suchen:

 1 function NaiveSuche(string s[1..n], string sub[1..m])
 2     for i from 1 to n
 3         for j from 1 to m
 4             if s[i+j-1] ≠ sub[j]
 5                 springe zur nächsten Iteration der äußeren Schleife
 6         return i
 7     return nicht gefunden

Dieser Algorithmus funktioniert gut in vielen praktischen Fällen, schlägt allerdings an einigen Beispielen fehl. Als typisches Beispiel sei folgender Fall genannt: Suche eines Musters, bestehend aus 10.000 „a“s gefolgt von einem „b“, in einer Zeichenkette, die aus 10 Millionen „a“s besteht. In diesem Falle würde der Algorithmus seinen schlechtesten Fall Θ(mn) erreichen.

Der Knuth-Morris-Pratt-Algorithmus reduziert dieses zu Θ(n), indem er durch Vorberechnungen jeden einzelnen Buchstaben nur einmal vergleicht. Der Boyer-Moore-Algorithmus springt nicht nur um einen Buchstaben nach vorne, sondern um so viele Buchstaben wie möglich, um die Suche erfolgreich verlaufen zu lassen. Er verringert so effektiv die Zahl der Iterationen der äußeren Schleife, sodass die Zahl der Buchstaben, die untersucht werden, klein wird. Im besten Falle kann sie dann n/m sein. Der Rabin-Karp-Algorithmus legt das Augenmerk allerdings auf das Beschleunigen der Zeilen 3 bis 6 des obigen Beispiels.

Beschleunigen der Suche mittels Hash-Werten

Statt die Anzahl Vergleiche durch ausgeklügeltere Verfahren zu verringern, beschleunigt der Rabin-Karp-Algorithmus den Vergleich zwischen Muster und Teil-Zeichenketten durch Verwendung einer Hash-Funktion. Rabin-Karp nutzt die Überlegung aus, dass gleiche Textstücke auch gleiche Hash-Werte haben. Die Idee ist also, den Hash-Wert der gesuchten Zeichenkette zu errechnen und dann eine Teil-Zeichenkette mit gleichem Hash-Wert zu suchen.

Dabei sind zwei Punkte zu beachten. Erstens: Gleiche Hash-Werte stammen nicht unbedingt von identischen Zeichenketten. Bei Übereinstimmung müssen die Zeichenketten selbst also noch verglichen werden, was für lange Zeichenketten eine gewisse Zeit in Anspruch nehmen kann. Glücklicherweise gewährleistet eine gute Hash-Funktion für unterschiedliche sinnvolle Eingaben auch weitgehend unterschiedliche Hash-Werte, sodass die durchschnittliche Suchzeit durch diesen Umstand nicht signifikant steigt.

Der Algorithmus sähe wie folgt aus:

 1 function RabinKarp(string s[1..n], string sub[1..m])
 2     hsub := hash(sub[1..m])
 3     hs := hash(s[1..m])
 4     for i from 1 to n - m + 1
 5         if hs = hsub
 6             if s[i..i+m-1] = sub
 7                 return i
 8         hs := hash(s[i+1..i+m])
 9     return nicht gefunden

Die Zeilen 2, 3 und 6 laufen jeweils in Ω(m). Die Zeilen 2 und 3 werden nur einmal ausgeführt. Zeile 6 wird nur ausgeführt wird, wenn der Hash-Wert passt. Gewöhnlich wird dies nur wenige Male auftreten. Zeile 5 wird n Mal ausgeführt, benötigt aber nur eine konstante Zeit.

Jetzt kommt der zweite Punkt: Die Zeile 8. Wenn einfach der Hash-Wert für jeden Teiltext s[i+1..i+m] berechnet würde, dann wäre der Zeitbedarf dafür Ω(m). Da dies in jedem Schleifendurchlauf notwendig ist, würde der Algorithmus Ω(mn) benötigen, genau wie der oben aufgeführte einfachste Suchalgorithmus NaiveSuche.

Eine Optimierung basiert darauf, dass die Variable hs bereits den Hash-Wert von s[i..i+m-1] enthält. Bei Auswahl einer passenden Hash-Funktion (rolling hash) kann daraus der nächste Hash-Wert in konstanter Zeit berechnet werden. Im einfachsten Fall werden die einzelnen Zeichenwerte des Teiltextes addiert. Dann gilt:

s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

Im schlechtesten Fall bzw. bei einer schlechten Hash-Funktion, die zum Beispiel eine Konstante ergibt, wird Zeile 6 bis zu n-mal in jeder Iteration der Schleife ausgeführt. Da dies Ω(m) Zeit braucht, benötigt der gesamte Algorithmus immer noch die Worst-Case-Laufzeit Ω(mn).

Benutzte Hash-Funktionen

Der Schlüssel zu Rabin-Karp Ausführung ist die effiziente Berechnung der Hash-Werte der aufeinanderfolgenden Teiltexte des Textes. Eine beliebte und effektive Rollende Hash-Funktion bearbeitet jeden Teiltext als eine Zahl zu einer Basis. Diese Basis ist normalerweise eine große Primzahl. Zum Beispiel, wenn ein Teiltext „hi“ und die Basis 101 ist, wäre der Hash-Wert 104 × 101¹ + 105 × 101⁰ = 10609 (ASCII von „h“ ist 104 und von „i“ ist 105).

Zum Beispiel, wenn wir einen Text „abracadabra“ haben und nach einem Muster der Länge 3 suchen, können wir den Hash-Wert von „bra“ aus dem Hash-Wert von „abr“ (dem vorhergehenden Textteil) berechnen, indem wir die Zahl, die für das erste „a“ von „abr“ hinzugefügt wurde abziehen, z. B. 97 × 101² (97 ist ASCII für ’a’ und 101 ist die Basis die wir benutzen), multiplizieren mit der Basis und fügen für das letzte a von „bra“, z. B. 97 × 101⁰ = 97, hinzu. Wenn die Zeichenketten lang sind, wird dieser Algorithmus großen Gewinn erzielen im Vergleich zu vielen anderen Hash-Schemata.

Theoretisch existieren andere Algorithmen die geeignete Berechnungen, zum Beispiel das Multiplizieren der ASCII Werte von allen Buchstaben, so dass das Verschieben der Zeichenkette nur das Teilen durch den ersten Buchstaben und das Multiplizieren mit dem letzten Buchstaben bedingen würde. Die Grenze hierfür wäre die maximale Größe eines Integers und die Bedingung modulo-Berechnungen zu benutzen um die Hash-Werte klein zu halten.

Rabin-Karp und mehrfache Mustersuche

Rabin-Karp ist Knuth-Morris-Pratt, Boyer-Moore und anderen schnelleren Einzelmuster Textsuchalgorithmen wegen seines langsamen worst-case Verhalten in der Einzel-Mustersuche unterlegen. Trotzdem ist Rabin-Karp ein guter Algorithmus für die mehrfache Mustersuche.

Wenn wir jedes Vorkommen einer großen Anzahl fester Musterlängen in einem Text, z. B. k, suchen, können wir eine einfache Variante des Rabin-Karp, welcher eine Hash-Tabelle benutzt oder jede andere geeignete Datenstruktur erstellen. Diese überprüft ob ein Hash-Wert einer gegebenen Textfolge zu einer Sammlung von Hash-Werten von Mustern nach denen wir suchen passt.

 function RabinKarpSet(string s[1..n], set of string subs, m) {
     set hsubs := emptySet
     for each sub in subs
         insert hash(sub[1..m]) into hsubs
     hs := hash(s[1..m])
     for i from 1 to n
         if hs ∈ hsubs
             if s[i..i+m-1] = a substring mit hash hs
                     return i
         hs := hash(s[i+1..i+m])
     return nicht gefunden
 }

Wir nehmen an, dass alle Zeichenketten eine feste Länge m haben. Diese Annahme kann allerdings eliminiert werden, indem wir einfach den aktuellen Hash-Wert mit den Hash-Werten von allen Zeichenketten vergleichen. Gleichzeitig führen wir einen schnellen Lookup in unserer Datenstruktur durch, und überprüfen dann jeden Treffer den wir finden mit allen Zeichenketten mit diesem Hash-Wert.

Andere Algorithmen können nach einem einzelnen Muster in O(n) suchen, daher werden sie nach k Mustern in O(nk) suchen. Die oben angegebene Rabin-Karp Variante wird weiterhin in O(n) im Besten- und im Durchschnittsfall, da es eine Hash-Tabelle in O(1) erlaubt nachzuschauen ob ein Teiltext-Hash einem Muster-Hash gleicht oder nicht. Wir können des Weiteren von O(mnlogk) im worst-case ausgehen, wenn m die Länge des längsten der k-Texte ist, indem die Hash-Werte in einem AVL-Baum gespeichert werden, anstatt in einer Hash-Tabelle.

Referenzen

• 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.