Algoritmul Rabin-Karp

În acest tutorial, veți afla ce este algoritmul rabin-karp. De asemenea, veți găsi exemple de lucru ale algoritmului rabin-karp în C, C ++, Java și Python.

Algoritmul Rabin-Karp este un algoritm utilizat pentru căutarea / potrivirea tiparelor din text folosind o funcție hash. Spre deosebire de algoritmul de potrivire a șirurilor naive, acesta nu parcurge fiecare caracter din faza inițială, ci filtrează caracterele care nu se potrivesc și apoi efectuează comparația.

O funcție hash este un instrument pentru maparea unei valori de intrare mai mari la o valoare de ieșire mai mică. Această valoare de ieșire se numește valoarea hash.

Cum funcționează algoritmul Rabin-Karp?

O secvență de caractere este luată și verificată pentru posibilitatea prezenței șirului necesar. Dacă se găsește posibilitatea, se efectuează potrivirea caracterelor.

Să înțelegem algoritmul cu următorii pași:

  1. Lăsați textul să fie: Text
    Și șirul care trebuie căutat în textul de mai sus să fie: Model
  2. Permiteți-ne să atribuim un numerical value(v)/weightpentru caracterele pe care le vom folosi în problemă. Aici, am luat doar primele zece alfabete (adică de la A la J). Text Greutăți
  3. m fi lungimea modelului și n lungimea textului. Aici, m = 10 and n = 3.
    Fie d numărul de caractere din setul de intrare. Aici, am luat setul de intrare (A, B, C, …, J). Deci d = 10. Puteți asuma orice valoare adecvată pentru d.
  4. Să calculăm valoarea hash a modelului. Valoarea hash a textului
valoare hash pentru model (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

În calculul de mai sus, alegeți un număr prim (aici, 13) în așa fel încât să putem efectua toate calculele cu aritmetică cu o singură precizie.

Motivul pentru calcularea modulului este dat mai jos.

  1. Calculați valoarea hash pentru fereastra de text de dimensiunea m.
Pentru prima fereastră ABC, valoarea hash pentru text (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Comparați valoarea hash a modelului cu valoarea hash a textului. Dacă se potrivesc atunci, se efectuează potrivirea caracterelor.
    În exemplele de mai sus, valoarea hash a primei ferestre (adică t) se potrivește cu p, deci mergeți la potrivirea caracterelor între ABC și CDD. Deoarece nu se potrivesc, mergeți la următoarea fereastră.
  2. Calculăm valoarea hash a ferestrei următoare scăzând primul termen și adăugând următorul termen așa cum se arată mai jos.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Pentru a optimiza acest proces, folosim valoarea hash anterioară în felul următor.

t = ((d * (t - v (caracter de eliminat) * h) + v (caracter de adăugat)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Unde , h = d m-1 = 10 3-1 = 100.
  1. Pentru BCC, t = 12 ( ≠ 6). Prin urmare, mergeți la următoarea fereastră.
    După câteva căutări, vom obține potrivirea pentru fereastra CDA din text. Valoarea hash a diferitelor ferestre

Algoritm

 n = t.lungime m = p.lungime h = dm-1 mod qp = 0 t0 = 0 pentru i = 1 la mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q pentru s = 0 la n - m dacă p = ts dacă p (1 … m) = t (s + 1 … s + m) tipăriți "model găsit în poziția" s Dacă s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Exemple Python, Java și 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); )

Limitările algoritmului Rabin-Karp

Hit Spurious

Când valoarea hash a modelului se potrivește cu valoarea hash a unei ferestre a textului, dar fereastra nu este modelul real, atunci se numește o lovitură falsă.

Lovirea falsă crește complexitatea timpului algoritmului. Pentru a minimiza lovirea falsă, folosim modulul. Reduce foarte mult lovitura falsă.

Complexitatea algoritmului Rabin-Karp

Complexitatea cazului mediu și a celui mai bun caz al algoritmului Rabin-Karp este, O(m + n)iar complexitatea cazului cel mai rău este O (mn).

Cea mai rea situație de complexitate apare atunci când loviturile false apar un număr pentru toate ferestrele.

Aplicații pentru algoritmul Rabin-Karp

  • Pentru potrivirea modelelor
  • Pentru căutarea șirului într-un text mai mare

Articole interesante...