Rabin-Karp algoritme

I denne opplæringen vil du lære hva rabin-karp algoritme er. I tillegg finner du arbeidseksempler på Rabin-Karp-algoritme i C, C ++, Java og Python.

Rabin-Karp algoritme er en algoritme som brukes til å søke / matche mønstre i teksten ved hjelp av en hash-funksjon. I motsetning til Naive string matching algoritme, beveger den seg ikke gjennom alle tegn i den innledende fasen, men filtrerer tegnene som ikke stemmer overens, og utfører deretter sammenligningen.

En hash-funksjon er et verktøy for å kartlegge en større inngangsverdi til en mindre utgangsverdi. Denne utgangsverdien kalles hash-verdien.

Hvordan fungerer Rabin-Karp-algoritmen?

En sekvens av tegn tas og kontrolleres for muligheten for tilstedeværelsen av den nødvendige strengen. Hvis muligheten blir funnet, utføres karaktertilpasning.

La oss forstå algoritmen med følgende trinn:

  1. La teksten være: Tekst
    Og strengen som skal søkes i teksten ovenfor være: Mønster
  2. La oss tildele a numerical value(v)/weightfor tegnene vi skal bruke i problemet. Her har vi bare tatt de ti første alfabeter (dvs. A til J). Tekstvekter
  3. m være lengden på mønsteret og n være lengden på teksten. Her, m = 10 and n = 3.
    la d være antall tegn i inngangssettet. Her har vi tatt inngangssett (A, B, C, …, J). Så d = 10. Du kan anta hvilken som helst passende verdi for d.
  4. La oss beregne hashverdien til mønsteret. Hash-verdi av tekst
hash-verdi 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 velger du et primtall (her, 13) på en slik måte at vi kan utføre alle beregningene med enkeltpresisjonsregning.

Årsaken til å beregne modulen er gitt nedenfor.

  1. Beregn hashverdien for tekstvinduet i størrelse m.
For det første vinduet ABC, hash-verdi 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-verdien til mønsteret med hash-verdien i teksten. Hvis de stemmer overens, utføres karaktertilpasning.
    I eksemplene ovenfor samsvarer hashverdien til det første vinduet (dvs. t) med p så, gå for tegnsamsvar mellom ABC og CDD. Siden de ikke stemmer overens, går du til neste vindu.
  2. Vi beregner hashverdien til neste vindu ved å trekke den første termen og legge til den neste termen som vist nedenfor.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

For å optimalisere denne prosessen, bruker vi den forrige hashverdien på følgende måte.

t = ((d * (t - v (tegn skal fjernes) * h) + v (tegn som skal legges til)) 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 neste vindu.
    Etter noen søk vil vi få matchet for vinduet CDA i teksten. Hash-verdi av forskjellige vinduer

Algoritme

 n = t. lengde m = p. lengde 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) skriv ut "mønster funnet i posisjon" 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); )

Begrensninger av Rabin-Karp algoritme

Spurious Hit

Når hashverdien til mønsteret samsvarer med hashverdien til et vindu i teksten, men vinduet ikke er det egentlige mønsteret, kalles det en falsk hit.

Spurende hit øker algoritmens tidskompleksitet. For å minimere falske treff bruker vi modul. Det reduserer den falske treffet sterkt.

Rabin-Karp algoritmekompleksitet

Gjennomsnittlig tilfelle og best case kompleksitet av Rabin-Karp algoritme er O(m + n)og worst case kompleksitet er O (mn).

I verste fall oppstår kompleksiteten når falske treff forekommer et tall for alle vinduene.

Rabin-Karp algoritmeapplikasjoner

  • For mønstermatching
  • For å søke i en større tekst

Interessante artikler...