Rabin-Karpov algoritem

V tej vadnici boste izvedeli, kaj je algoritem rabin-karp. Prav tako boste našli delovne primere algoritma rabin-karp v C, C ++, Java in Python.

Rabin-Karpov algoritem je algoritem, ki se uporablja za iskanje / ujemanje vzorcev v besedilu z uporabo zgoščevalne funkcije. Za razliko od algoritma za ujemanje nizov Naive v začetni fazi ne potuje skozi vse znake, temveč filtrira znake, ki se ne ujemajo, in nato izvede primerjavo.

Razpršilna funkcija je orodje za preslikavo večje vhodne vrednosti v manjšo izhodno vrednost. Ta izhodna vrednost se imenuje zgoščena vrednost.

Kako deluje algoritem Rabin-Karp?

Zapiše se zaporedje znakov in preveri, ali obstaja prisotnost zahtevanega niza. Če je takrat mogoče najti možnost, se izvede ujemanje znakov.

Dovolite nam, da razumemo algoritem z naslednjimi koraki:

  1. Besedilo naj bo: Besedilo
    In niz, ki ga želite iskati v zgornjem besedilu, je: Vzorec
  2. Določimo a numerical value(v)/weightza znake, ki jih bomo uporabili v problemu. Tu smo vzeli samo prvih deset abeced (tj. A do J). Uteži besedila
  3. m je dolžina vzorca in n dolžina besedila. Tu m = 10 and n = 3.
    naj je d število znakov v vhodnem nizu. Tukaj smo vzeli vhodni niz (A, B, C,…, J). Torej, d = 10. Za d lahko vzamete katero koli primerno vrednost.
  4. Izračunajmo zgoščeno vrednost vzorca. Razpršena vrednost besedila
hash vrednost za vzorec (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

V zgornjem izračunu izberite praštevilo (tukaj, 13) tako, da bomo lahko vse izračune izvedli z aritmetiko z eno natančnostjo.

Razlog za izračun modula je naveden spodaj.

  1. Izračunajte zgoščeno vrednost za besedilno okno velikosti m.
Za prvo okno ABC je zgoščena vrednost za besedilo (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Primerjaj zgoščeno vrednost vzorca z zgoščeno vrednostjo besedila. Če se potem ujemata, se izvede ujemanje znakov.
    V zgornjih primerih se zgoščena vrednost prvega okna (tj. T) ujema s p, zato poiščite ujemanje znakov med ABC in CDD. Ker se ne ujemata, pojdite na naslednje okno.
  2. Hash vrednost naslednjega okna izračunamo tako, da odštejemo prvi člen in dodamo naslednji člen, kot je prikazano spodaj.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Da bi optimizirali ta postopek, uporabimo prejšnjo zgoščeno vrednost na naslednji način.

t = ((d * (t - v (znak, ki ga je treba odstraniti) * h) + v (znak, ki ga je treba dodati)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Kjer , h = d m-1 = 10 3-1 = 100.
  1. Za BCC je t = 12 ( ≠ 6). Zato pojdite na naslednje okno.
    Po nekaj poizvedbah bomo v besedilu dobili ujemanje za okenski CDA. Razpršena vrednost različnih oken

Algoritem

 n = t.dolžina m = p.dolžina h = dm-1 mod qp = 0 t0 = 0 za i = 1 do mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q za s = 0 do n - m, če je p = ts, če je p (1 … m) = t (s + 1 … s + m) print "vzorec najden na položaju" s Če je s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Primeri Python, Java in 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); )

Omejitve algoritma Rabin-Karp

Lažen zadetek

Ko se zgoščena vrednost vzorca ujema z zgoščeno vrednostjo okna besedila, vendar okno ni dejanski vzorec, se imenuje lažni zadetek.

Napačen zadetek poveča časovno zapletenost algoritma. Da bi zmanjšali napačne zadetke, uporabljamo modul. Močno zmanjša lažen zadetek.

Kombinacija algoritma Rabin-Karp

Povprečna zapletenost in najboljša zapletenost algoritma Rabin-Karp je, O(m + n)najslabša pa O (mn).

V najslabšem primeru se zapletenost pojavi, ko pride do napačnih zadetkov za vsa okna.

Aplikacije algoritma Rabin-Karp

  • Za ujemanje vzorcev
  • Za iskanje niza v večjem besedilu

Zanimive Članki...