Rabin-Karp algoritmas

Šioje pamokoje sužinosite, kas yra „rabin-karp“ algoritmas. Taip pat rasite veikiančių rabin-karp algoritmo pavyzdžių C, C ++, Java ir Python.

Rabin-Karp algoritmas yra algoritmas, naudojamas ieškant / derinant šablonus tekste naudojant maišos funkciją. Skirtingai nuo naivaus eilučių derinimo algoritmo, pradinėje fazėje jis nekeliauja per kiekvieną simbolį, o filtruoja nesutampančius simbolius ir tada atlieka palyginimą.

Maišos funkcija yra įrankis, leidžiantis susieti didesnę įvesties vertę su mažesne išvesties verte. Ši išvesties vertė vadinama maišos reikšme.

Kaip veikia Rabin-Karp algoritmas?

Paimama simbolių seka ir patikrinama, ar nėra reikalingos eilutės. Jei galimybė yra randama, atliekamas simbolių derinimas.

Supraskime algoritmą atlikdami šiuos veiksmus:

  1. Tegul tekstas yra: Tekstas
    Ir eilutė, kurios reikia ieškoti aukščiau esančiame tekste, yra: Raštas
  2. Priskirkime numerical value(v)/weightsimbolius, kuriuos naudosime problemoje. Čia mes paėmėme tik pirmuosius dešimt abėcėlių (ty nuo A iki J). Teksto svoriai
  3. m - rašto ilgis ir n - teksto ilgis. Čia m = 10 and n = 3.
    tegul d yra simbolių skaičius įvesties rinkinyje. Čia mes paėmėme įvesties rinkinį (A, B, C,…, J). Taigi d = 10,. Galite prisiimti bet kurią tinkamą d reikšmę.
  4. Apskaičiuokime modelio maišos vertę. Teksto maišos vertė
šablono maišos vertė (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

Atlikdami aukščiau pateiktą skaičiavimą, pirminį skaičių (čia, 13) pasirinkite taip, kad visus skaičiavimus galėtume atlikti taikydami vieno tikslumo aritmetiką.

Modulio apskaičiavimo priežastis pateikiama žemiau.

  1. Apskaičiuokite m dydžio teksto lango maišos vertę.
Pirmojo lango ABC teksto maišos reikšmė (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Palyginkite modelio maišos vertę su teksto maišos verte. Jei jie atitinka, atliekamas simbolių derinimas.
    Pirmiau pateiktuose pavyzdžiuose pirmojo lango maišos reikšmė (ty t) sutampa su p, taigi eikite į simbolių derinimą tarp ABC ir CDD. Kadangi jie nesutampa, eikite į kitą langą.
  2. Mes apskaičiuojame kito lango maišos vertę, atimdami pirmąjį terminą ir pridėdami kitą terminą, kaip parodyta žemiau.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Norėdami optimizuoti šį procesą, mes naudojame ankstesnę maišos vertę taip.

t = ((d * (t - v (simbolis turi būti pašalintas) * h) + v (papildomas simbolis)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Kur , h = d m-1 = 10 3-1 = 100.
  1. BCC atveju t = 12 ( ≠ 6). Todėl eikite į kitą langą.
    Po kelių paieškų gausime lango CDA atitiktį tekste. Skirtingų langų maišos vertė

Algoritmas

 n = t.ilgis m = p. ilgis h = dm-1 mod qp = 0 t0 = 0 i = 1 iki mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q už s = 0 iki n - m, jei p = ts, jei p (1… m) = t (s + 1… s + m) atspausdinti „rastą modelį“ s Jei s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

„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); )

Rabin-Karp algoritmo apribojimai

Netikras hitas

Kai šablono maišos vertė sutampa su teksto lango maišos verte, bet langas nėra tikrasis šablonas, jis vadinamas netikru įvykiu.

Netikras smūgis padidina algoritmo laiko sudėtingumą. Kad sumažintume netikrą smūgį, naudojame modulį. Tai labai sumažina netikrą smūgį.

Rabin-Karp algoritmo kompleksiškumas

Rabin-Karp algoritmo vidutinis atvejis ir geriausio atvejo sudėtingumas yra, O(m + n)o blogiausio atvejo - O (mn).

Blogiausias atvejis būna tada, kai apgaulingi įvykiai įvyksta visuose languose.

„Rabin-Karp“ algoritmų taikymai

  • Dėl modelio derinimo
  • Norėdami ieškoti eilutės didesniame tekste

Įdomios straipsniai...