Rabin-Karp algoritme

I denne vejledning lærer du, hvad rabin-karp algoritme er. Du finder også arbejdseksempler på rabin-karp-algoritme i C, C ++, Java og Python.

Rabin-Karp algoritme er en algoritme, der bruges til at søge / matche mønstre i teksten ved hjælp af en hash-funktion. I modsætning til Naive streng matchende algoritme bevæger den sig ikke gennem hvert tegn i den indledende fase, men filtrerer de tegn, der ikke matcher, og udfører derefter sammenligningen.

En hash-funktion er et værktøj til at kortlægge en større inputværdi til en mindre outputværdi. Denne outputværdi kaldes hashværdien.

Hvordan fungerer Rabin-Karp algoritme?

En sekvens af tegn tages og kontrolleres for muligheden for tilstedeværelsen af ​​den krævede streng. Hvis muligheden findes, udføres karaktertilpasning.

Lad os forstå algoritmen med følgende trin:

  1. Lad teksten være: Tekst
    Og den streng, der skal søges i ovenstående tekst, er: Mønster
  2. Lad os tildele a numerical value(v)/weighttil de tegn, vi bruger i problemet. Her har vi kun taget de første ti alfabeter (dvs. A til J). Tekstvægte
  3. m være længden af ​​mønsteret og n være længden af ​​teksten. Her, m = 10 and n = 3.
    Lad d være antallet af tegn i input-sættet. Her har vi taget input-sæt (A, B, C,…, J). Så d = 10. Du kan antage en hvilken som helst passende værdi for d.
  4. Lad os beregne hash-værdien af ​​mønsteret. Hash-værdi af tekst
hash-værdi for mønster (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

I beregningen ovenfor skal du vælge et primtal (her, 13) på en sådan måde, at vi kan udføre alle beregningerne med enkeltpræcisionsberegning.

Årsagen til beregning af modulet er angivet nedenfor.

  1. Beregn hashværdien for tekstvinduet i størrelse m.
For det første vindue ABC, hash-værdi for tekst (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Sammenlign hash-værdien af ​​mønsteret med hash-værdien i teksten. Hvis de stemmer overens, udføres karaktertilpasning.
    I ovenstående eksempler matcher hashværdien af ​​det første vindue (dvs. t) med p, så vælg karaktertilpasning mellem ABC og CDD. Da de ikke stemmer overens, skal du gå til det næste vindue.
  2. Vi beregner hashværdien af ​​det næste vindue ved at trække den første periode og tilføje den næste periode som vist nedenfor.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

For at optimere denne proces bruger vi den forrige hashværdi på følgende måde.

t = ((d * (t - v (tegn skal fjernes) * h) + v (tegn der skal tilføjes)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Hvor , h = d m-1 = 10 3-1 = 100.
  1. For BCC er t = 12 ( ≠ 6). Gå derfor til det næste vindue.
    Efter et par søgninger får vi matchet til vinduet CDA i teksten. Hash-værdi af forskellige vinduer

Algoritme

 n = t. længde m = p. længde h = dm-1 mod qp = 0 t0 = 0 for i = 1 til mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q for s = 0 til n - m hvis p = ts hvis p (1… m) = t (s + 1… s + m) udskrive "mønster fundet ved position" s Hvis s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Python, Java og C / C ++ eksempler

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

Begrænsninger af Rabin-Karp algoritme

Rosende hit

Når mønsterets hashværdi matcher hashværdien af ​​et vindue i teksten, men vinduet ikke er det egentlige mønster, kaldes det et falsk hit.

Rosende hit øger algoritmens tidskompleksitet. For at minimere falsk hit bruger vi modul. Det reducerer det falske hit i høj grad.

Rabin-Karp algoritmekompleksitet

Rabin-Karp-algoritmens gennemsnitlige case og best case-kompleksitet er, O(m + n)og worst case-kompleksiteten er O (mn).

Den værst tænkelige kompleksitet opstår, når falske hits forekommer et tal for alle vinduer.

Rabin-Karp algoritme applikationer

  • Til mønstermatchning
  • Til søgning i en større tekst

Interessante artikler...