Rabin-Karp-algoritme

In deze tutorial leer je wat rabin-karp algoritme is. Ook vindt u werkende voorbeelden van het rabin-karp-algoritme in C, C ++, Java en Python.

Het Rabin-Karp-algoritme is een algoritme dat wordt gebruikt voor het zoeken / matchen van patronen in de tekst met behulp van een hash-functie. In tegenstelling tot het naïeve algoritme voor het matchen van tekenreeksen, reist het niet door elk teken in de beginfase, maar filtert het de tekens die niet overeenkomen en voert het vervolgens de vergelijking uit.

Een hash-functie is een hulpmiddel om een ​​grotere invoerwaarde toe te wijzen aan een kleinere uitvoerwaarde. Deze outputwaarde wordt de hash-waarde genoemd.

Hoe werkt het Rabin-Karp-algoritme?

Een reeks karakters wordt genomen en gecontroleerd op de mogelijkheid van de aanwezigheid van de vereiste string. Als de mogelijkheid wordt gevonden, wordt karaktervergelijking uitgevoerd.

Laten we het algoritme begrijpen met de volgende stappen:

  1. Laat de tekst zijn: Tekst
    En de string die moet worden doorzocht in de bovenstaande tekst is: Patroon
  2. Laten we een a toewijzen numerical value(v)/weightaan de karakters die we in de opgave zullen gebruiken. Hier hebben we alleen de eerste tien alfabetten genomen (dwz A tot J). Tekstgewichten
  3. m is de lengte van het patroon en n is de lengte van de tekst. Hier, m = 10 and n = 3.
    laat d het aantal tekens in de invoerset zijn. Hier hebben we de invoerset genomen (A, B, C,…, J). Dus, d = 10. U kunt elke geschikte waarde aannemen voor d.
  4. Laten we de hash-waarde van het patroon berekenen. Hash-waarde van tekst
hash-waarde voor patroon (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

Kies in de bovenstaande berekening een priemgetal (hier 13) op zo'n manier dat we alle berekeningen kunnen uitvoeren met rekenkundige bewerkingen met één precisie.

De reden voor het berekenen van de modulus wordt hieronder gegeven.

  1. Bereken de hash-waarde voor het tekstvenster van grootte m.
Voor het eerste venster ABC, hash-waarde voor tekst (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Vergelijk de hash-waarde van het patroon met de hash-waarde van de tekst. Als ze dan overeenkomen, wordt karaktervergelijking uitgevoerd.
    In de bovenstaande voorbeelden komt de hash-waarde van het eerste venster (dat wil zeggen t) overeen met p dus, ga voor tekenovereenkomst tussen ABC en CDD. Omdat ze niet overeenkomen, ga je naar het volgende venster.
  2. We berekenen de hash-waarde van het volgende venster door de eerste term af te trekken en de volgende term toe te voegen, zoals hieronder wordt weergegeven.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Om dit proces te optimaliseren, maken we op de volgende manier gebruik van de vorige hashwaarde.

t = ((d * (t - v (teken dat moet worden verwijderd) * h) + v (teken dat moet worden toegevoegd)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 waarbij , h = d m-1 = 10 3-1 = 100.
  1. Voor BCC, t = 12 ( ≠ 6). Ga daarom voor het volgende venster.
    Na een paar zoekacties krijgen we de match voor het venster CDA in de tekst. Hash-waarde van verschillende vensters

Algoritme

 n = t.lengte m = p.lengte h = dm-1 mod qp = 0 t0 = 0 voor i = 1 tot mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q voor s = 0 tot n - m if p = ts if p (1… m) = t (s + 1… s + m) print "patroon gevonden op positie" s If s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Python, Java en C / C ++ voorbeelden

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); )

Beperkingen van het Rabin-Karp-algoritme

Valse treffer

Wanneer de hash-waarde van het patroon overeenkomt met de hash-waarde van een venster van de tekst, maar het venster is niet het werkelijke patroon, dan wordt dit een onechte hit genoemd.

Een onechte hit verhoogt de tijdcomplexiteit van het algoritme. Om valse treffers te minimaliseren, gebruiken we modulus. Het vermindert de onechte treffer aanzienlijk.

Complexiteit van het Rabin-Karp-algoritme

De gemiddelde en beste gevalcomplexiteit van het Rabin-Karp-algoritme is O(m + n)en de complexiteit in het slechtste geval is O (mn).

De worst-case-complexiteit treedt op wanneer onechte treffers een nummer voor alle vensters zijn.

Rabin-Karp-algoritme-toepassingen

  • Voor het matchen van patronen
  • Voor het zoeken van een string in een grotere tekst

Interessante artikelen...