Rabin-Karpov algoritam

U ovom uputstvu naučit ćete što je rabin-karp algoroitam. Također, naći ćete radne primjere rabin-karp algoritma u C, C ++, Java i Python.

Rabin-Karpov algoritam algoritam je koji se koristi za traženje / podudaranje obrazaca u tekstu pomoću hash funkcije. Za razliku od Naive algoritma za podudaranje nizova, on ne putuje kroz svaki znak u početnoj fazi, već filtrira znakove koji se ne podudaraju i zatim vrši usporedbu.

Hash funkcija je alat za mapiranje veće ulazne vrijednosti u manju izlaznu vrijednost. Ova se izlazna vrijednost naziva hash vrijednost.

Kako djeluje Rabin-Karpov algoritam?

Uzima se slijed znakova i provjerava mogućnost prisutnosti potrebnog niza. Ako se tada pronađe mogućnost, izvodi se podudaranje znakova.

Razumijemo algoritam u sljedećim koracima:

  1. Neka tekst bude: Tekst
    A niz koji se traži u gornjem tekstu: Uzorak
  2. Dodijelimo a numerical value(v)/weightza znakove koje ćemo koristiti u problemu. Ovdje smo uzeli samo prvih deset abeceda (tj. A do J). Utezi teksta
  3. m je duljina uzorka i n duljina teksta. Ovdje je m = 10 and n = 3.
    neka d broj znakova u ulaznom skupu. Ovdje smo uzeli skup ulaza (A, B, C,…, J). Dakle, d = 10. Možete pretpostaviti bilo koju prikladnu vrijednost za d.
  4. Izračunajmo hash vrijednost uzorka. Hash vrijednost teksta
hash vrijednost za uzorak (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

U gornjem izračunu odaberite prost broj (ovdje 13) na takav način da sve izračune možemo izvesti aritmetikom s jednom preciznošću.

Razlog za izračunavanje modula naveden je u nastavku.

  1. Izračunajte hash vrijednost za tekstualni prozor veličine m.
Za prvi prozor ABC, hash vrijednost za tekst (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Usporedite hash vrijednost uzorka s hash vrijednošću teksta. Ako se tada podudaraju, izvodi se podudaranje znakova.
    U gornjim primjerima, hash vrijednost prvog prozora (tj. T) podudara se s p, zato podudarite znakove između ABC i CDD. Budući da se ne podudaraju s tim, idite na sljedeći prozor.
  2. Izračunavamo hash vrijednost sljedećeg prozora oduzimajući prvi pojam i dodajući sljedeći pojam kao što je prikazano u nastavku.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Kako bismo optimizirali ovaj postupak, koristimo prethodnu hash vrijednost na sljedeći način.

t = ((d * (t - v (znak koji se uklanja) * h) + v (znak koji treba dodati)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Gdje , h = d m-1 = 10 3-1 = 100.
  1. Za BCC, t = 12 ( ≠ 6). Stoga idite na sljedeći prozor.
    Nakon nekoliko pretraživanja, u tekstu ćemo dobiti podudarnost za prozorski CDA. Hash vrijednost različitih prozora

Algoritam

 n = t.duljina m = p.duljina 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 ako je p = ts ako je p (1 … m) = t (s + 1 … s + m) ispis "uzorak pronađen na položaju" s Ako je s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Primjeri Pythona, 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); )

Ograničenja Rabin-Karpovog algoritma

Lažni pogodak

Kada se hash vrijednost uzorka podudara s hash vrijednošću prozora teksta, ali prozor nije stvarni uzorak, tada se naziva lažnim pogotkom.

Lažni pogodak povećava vremensku složenost algoritma. Da bismo smanjili lažni pogodak, koristimo modul. Uvelike smanjuje lažni pogodak.

Složenost algoritma Rabin-Karp

Prosječna složenost slučaja i najboljeg slučaja Rabin-Karpovog algoritma je, O(m + n)a najlošija složenost je O (mn).

Složenost u najgorem slučaju javlja se kada se lažni pogoci pojave na broju za sve prozore.

Primjene Rabin-Karp algoritma

  • Za podudaranje uzoraka
  • Za pretraživanje niza u većem tekstu

Zanimljivi članci...