Rabin-Karpov algoritmus

V tomto tutoriáli sa dozviete, čo je rabínsko-karpský algoroitmus. Nájdete tiež pracovné príklady algoritmu rabin-karp v jazykoch C, C ++, Java a Python.

Algoritmus Rabin-Karp je algoritmus používaný na vyhľadávanie / porovnávanie vzorov v texte pomocou hashovacej funkcie. Na rozdiel od naivného algoritmu na porovnávanie reťazcov neprechádza v úvodnej fáze každým znakom, skôr filtruje znaky, ktoré sa nezhodujú, a potom vykoná porovnanie.

Hašovacia funkcia je nástroj na mapovanie väčšej vstupnej hodnoty na menšiu výstupnú hodnotu. Táto výstupná hodnota sa nazýva hash hodnota.

Ako funguje Rabin-Karpov algoritmus?

Zoberie sa postupnosť znakov a skontroluje sa možnosť prítomnosti požadovaného reťazca. Ak sa nájde možnosť, vykoná sa zhoda znakov.

Pochopme algoritmus pomocou nasledujúcich krokov:

  1. Text nechajte byť: Text
    A reťazec, ktorý sa má vyhľadať vo vyššie uvedenom texte, byť: Vzor
  2. Priraďme numerical value(v)/weightznakom, ktoré použijeme v úlohe. Tu sme zobrali iba prvých desať abeced (tj. A až J). Váhy textu
  3. m je dĺžka vzoru an je dĺžka textu. Tu m = 10 and n = 3.
    Nech d je počet znakov vo vstupnej sade. Tu sme vzali vstupnú množinu (A, B, C, …, J). Takže d = 10. Môžete predpokladať akúkoľvek vhodnú hodnotu pre d.
  4. Vypočítajme hodnotu hash vzoru. Hodnota hash textu
hodnota hash pre vzor (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

Vo vyššie uvedenom výpočte vyberte prvočíslo (tu 13) tak, aby sme mohli všetky výpočty vykonávať pomocou aritmetiky s jednou presnosťou.

Dôvod výpočtu modulu je uvedený nižšie.

  1. Vypočítajte hodnotu hash pre textové okno veľkosti m.
Pre prvé okno ABC hodnota hash pre text (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Porovnajte hodnotu hash vzoru s hodnotou hash textu. Ak sa potom zhodujú, vykoná sa zhoda znakov.
    Vo vyššie uvedených príkladoch sa hodnota hash prvého okna (tj. T) zhoduje s parametrom p, takže vyhľadajte znakovú zhodu medzi ABC a CDD. Pretože sa nezhodujú, prejdite na ďalšie okno.
  2. Hodnotu hash nasledujúceho okna vypočítame odčítaním prvého výrazu a pridaním nasledujúceho výrazu, ako je uvedené nižšie.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

S cieľom optimalizovať tento proces využívame predchádzajúcu hodnotu hash nasledujúcim spôsobom.

t = ((d * (t - v (znak, ktorý sa má odstrániť) * h) + v (znak, ktorý sa má pridať)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Kde , h = dm -1 = 10 3-1 = 100.
  1. Pre BCC t = 12 ( ≠ 6). Preto choďte na ďalšie okno.
    Po niekoľkých vyhľadávaniach dostaneme v texte zhodu pre okno CDA. Hodnota hash rôznych okien

Algoritmus

 n = t.length m = p.length h = dm-1 mod qp = 0 t0 = 0 pre i = 1 až mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q for s = 0 až n - m if p = ts if p (1 … m) = t (s + 1 … s + m) print "pattern found at position" s If s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Príklady jazyka Python, Java a 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); )

Obmedzenia Rabin-Karpovho algoritmu

Falošný zásah

Ak sa hodnota hash vzoru zhoduje s hodnotou hash okna textu, ale okno nie je skutočným vzorom, potom sa nazýva falošný zásah.

Falošný zásah zvyšuje časovú zložitosť algoritmu. Aby sme minimalizovali falošné zásahy, používame modulus. Veľmi to znižuje falošný zásah.

Zložitosť algoritmu Rabin-Karp

Priemerná a najlepšia zložitosť Rabin-Karpovho algoritmu je O(m + n)a najhoršia zložitosť je O (mn).

Najhoršia zložitosť nastáva, keď sa vo všetkých oknách vyskytnú rušivé zásahy.

Aplikácie Rabin-Karpovho algoritmu

  • Na zosúladenie vzorov
  • Na hľadanie reťazca vo väčšom texte

Zaujímavé články...