Der Rabin-Karp-Algorithmus erklärt

Der Rabin-Karp-Algorithmus ist ein von Michael O. Rabin und Richard M. Karp entwickelter String Matching / Search-Algorithmus. Es verwendet Hashing- Technik und Brute Force zum Vergleich und ist ein guter Kandidat für die Erkennung von Plagiaten.

Wichtige Begriffe

  • Muster ist die zu durchsuchende Zeichenfolge. Betrachten Sie die Länge des Musters als M Zeichen.
  • Text ist der gesamte Text, aus dem das Muster durchsucht werden soll. Betrachten Sie die Textlänge als N Zeichen.

Was ist Brute-Force-Vergleich?

Beim Brute-Force-Vergleich wird jedes Zeichen des Musters mit jedem Zeichen des Textes verglichen, bis Zeichen gefunden werden, die nicht übereinstimmen.

Wie der Rabin-Karp-Algorithmus funktioniert

  1. Berechnen Sie den Hashwert des Musters
  2. Berechnen Hashwert ersten M Zeichen von Text
  3. Vergleichen Sie beide Hashwerte
  4. Wenn sie ungleich sind, berechnen Hash - Wert für die nächste M Zeichen von Text und vergleichen Sie es erneut.
  5. Wenn sie gleich sind, führen Sie einen Brute-Force-Vergleich durch.
hash_p = hash value of pattern hash_t = hash value of first M letters in body of text do if (hash_p == hash_t) brute force comparison of pattern and selected section of text hash_t= hash value of next section of text, one character over while (end of text or brute force comparison == true)

Vorteil gegenüber dem naiven String-Matching-Algorithmus

Diese Technik führt nur zu einem Vergleich pro Textuntersequenz, und Brute Force ist nur erforderlich, wenn die Hashwerte übereinstimmen.