Rabin-Karp-Algorithmus

In diesem Tutorial erfahren Sie, was Rabin-Karp-Algorithmus ist. Außerdem finden Sie Arbeitsbeispiele für den Rabin-Karp-Algorithmus in C, C ++, Java und Python.

Der Rabin-Karp-Algorithmus ist ein Algorithmus zum Suchen / Abgleichen von Mustern im Text unter Verwendung einer Hash-Funktion. Im Gegensatz zum naiven String-Matching-Algorithmus durchläuft er nicht jedes Zeichen in der Anfangsphase, sondern filtert die nicht übereinstimmenden Zeichen und führt dann den Vergleich durch.

Eine Hash-Funktion ist ein Werkzeug, um einen größeren Eingabewert einem kleineren Ausgabewert zuzuordnen. Dieser Ausgabewert wird als Hashwert bezeichnet.

Wie funktioniert der Rabin-Karp-Algorithmus?

Eine Folge von Zeichen wird genommen und auf die Möglichkeit des Vorhandenseins der erforderlichen Zeichenfolge überprüft. Wenn die Möglichkeit gefunden wird, wird eine Zeichenübereinstimmung durchgeführt.

Lassen Sie uns den Algorithmus mit den folgenden Schritten verstehen:

  1. Der Text sei: Text
    Und die im obigen Text zu suchende Zeichenfolge sei: Muster
  2. Weisen wir numerical value(v)/weightden Zeichen, die wir in dem Problem verwenden werden, ein zu. Hier haben wir nur die ersten zehn Alphabete genommen (dh A bis J). Textgewichte
  3. m ist die Länge des Musters und n ist die Länge des Textes. Hier m = 10 and n = 3.
    sei d die Anzahl der Zeichen im Eingabesatz. Hier haben wir den Eingabesatz (A, B, C,…, J) genommen. Also , d = 10. Sie können jeden geeigneten Wert für d annehmen.
  4. Berechnen wir den Hash-Wert des Musters. Hash-Wert von Text
Hash-Wert für Muster (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

Wählen Sie in der obigen Berechnung eine Primzahl (hier 13) so, dass wir alle Berechnungen mit Arithmetik mit einfacher Genauigkeit durchführen können.

Der Grund für die Berechnung des Moduls ist unten angegeben.

  1. Berechnen Sie den Hashwert für das Textfenster der Größe m.
Für das erste Fenster ABC ist der Hashwert für Text (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Vergleichen Sie den Hash-Wert des Musters mit dem Hash-Wert des Textes. Wenn sie dann übereinstimmen, wird eine Zeichenübereinstimmung durchgeführt.
    In den obigen Beispielen stimmt der Hash-Wert des ersten Fensters (dh t) mit p überein. Wählen Sie daher die Zeichenübereinstimmung zwischen ABC und CDD. Da sie nicht übereinstimmen, gehen Sie zum nächsten Fenster.
  2. Wir berechnen den Hashwert des nächsten Fensters, indem wir den ersten Term subtrahieren und den nächsten Term wie unten gezeigt addieren.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Um diesen Prozess zu optimieren, verwenden wir den vorherigen Hash-Wert folgendermaßen.

t = ((d * (t - v (zu entfernendes Zeichen) * h) + v (hinzuzufügendes Zeichen)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Wobei , h = d m-1 = 10 3-1 = 100.
  1. Für BCC ist t = 12 ( ≠ 6). Gehen Sie daher zum nächsten Fenster.
    Nach einigen Suchen erhalten wir die Übereinstimmung für das Fenster CDA im Text. Hash-Wert verschiedener Fenster

Algorithmus

 n = t.Länge m = p.Länge h = dm-1 mod qp = 0 t0 = 0 für i = 1 bis mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q für s = 0 bis n - m, wenn p = ts, wenn p (1… m) = t (s + 1… s + m) "Muster an Position gefunden" drucken s Wenn s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Beispiele für Python, Java und C / C ++

Python Java C C ++ 
 # Rabin-Karp algorithm in python d = 10 def search(pattern, text, q): m = len(pattern) n = len(text) p = 0 t = 0 h = 1 i = 0 j = 0 for i in range(m-1): h = (h*d) % q # Calculate hash value for pattern and text for i in range(m): p = (d*p + ord(pattern(i))) % q t = (d*t + ord(text(i))) % q # Find the match for i in range(n-m+1): if p == t: for j in range(m): if text(i+j) != pattern(j): break j += 1 if j == m: print("Pattern is found at position: " + str(i+1)) if i < n-m: t = (d*(t-ord(text(i))*h) + ord(text(i+m))) % q if t < 0: t = t+q text = "ABCCDDAEFG" pattern = "CDD" q = 13 search(pattern, text, q)
 // Rabin-Karp algorithm in Java public class RabinKarp ( public final static int d = 10; static void search(String pattern, String txt, int q) ( int m = pattern.length(); int n = txt.length(); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern.charAt(i)) % q; t = (d * t + txt.charAt(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (txt.charAt(i + j) != pattern.charAt(j)) break; ) if (j == m) System.out.println("Pattern is found at position: " + (i + 1)); ) if (i < n - m) ( t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + m)) % q; if (t < 0) t = (t + q); ) ) ) public static void main(String() args) ( String txt = "ABCCDDAEFG"; String pattern = "CDD"; int q = 13; search(pattern, txt, q); ) )
 // Rabin-Karp algorithm in C #include #include #define d 10 void rabinKarp(char pattern(), char text(), int q) ( int m = strlen(pattern); int n = strlen(text); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern(i)) % q; t = (d * t + text(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (text(i + j) != pattern(j)) break; ) if (j == m) printf("Pattern is found at position: %d ", i + 1); ) if (i < n - m) ( t = (d * (t - text(i) * h) + text(i + m)) % q; if (t < 0) t = (t + q); ) ) ) int main() ( char text() = "ABCCDDAEFG"; char pattern() = "CDD"; int q = 13; rabinKarp(pattern, text, q); )
 // Rabin-Karp algorithm in C++ #include #include using namespace std; #define d 10 void rabinKarp(char pattern(), char text(), int q) ( int m = strlen(pattern); int n = strlen(text); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern(i)) % q; t = (d * t + text(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (text(i + j) != pattern(j)) break; ) if (j == m) cout << "Pattern is found at position: " << i + 1 << endl; ) if (i < n - m) ( t = (d * (t - text(i) * h) + text(i + m)) % q; if (t < 0) t = (t + q); ) ) ) int main() ( char text() = "ABCCDDAEFG"; char pattern() = "CDD"; int q = 13; rabinKarp(pattern, text, q); )

Einschränkungen des Rabin-Karp-Algorithmus

Falscher Treffer

Wenn der Hash-Wert des Musters mit dem Hash-Wert eines Textfensters übereinstimmt, das Fenster jedoch nicht das tatsächliche Muster ist, wird dies als falscher Treffer bezeichnet.

Ein falscher Treffer erhöht die zeitliche Komplexität des Algorithmus. Um Störschläge zu minimieren, verwenden wir den Modul. Es reduziert den falschen Treffer erheblich.

Komplexität des Rabin-Karp-Algorithmus

Die durchschnittliche Fall- und Best-Case-Komplexität des Rabin-Karp-Algorithmus ist O(m + n)und die Worst-Case-Komplexität ist O (mn).

Die Komplexität im schlimmsten Fall tritt auf, wenn für alle Fenster falsche Treffer auftreten.

Rabin-Karp-Algorithmus-Anwendungen

  • Für den Mustervergleich
  • Zum Suchen von Zeichenfolgen in einem größeren Text

Interessante Beiträge...