Rabin-Karp algoritmus

Ebben az oktatóanyagban megtudhatja, mi az a rabin-karp algoritmus. A C, C ++, a Java és a Python nyelvű rabin-karp algoritmusra működő példákat is talál.

A Rabin-Karp algoritmus egy algoritmus, amelyet hash függvény segítségével keresnek / illesztenek a szövegben mintákra. A Naiv karakterlánc-illesztő algoritmustól eltérően a kezdeti szakaszban nem halad át minden karakteren, hanem kiszűri azokat a karaktereket, amelyek nem egyeznek, majd elvégzi az összehasonlítást.

A hash függvény olyan eszköz, amellyel nagyobb bemeneti értéket lehet leképezni egy kisebb kimeneti értékre. Ezt a kimeneti értéket hash értéknek hívják.

Hogyan működik a Rabin-Karp algoritmus?

Karaktersorozatot veszünk, és ellenőrizzük, hogy a szükséges karakterlánc fennáll-e. Ha megtalálják a lehetőséget, akkor a karakterillesztést hajtják végre.

A következő lépésekkel értsük meg az algoritmust:

  1. Legyen a szöveg: Szöveg
    És a fenti szövegben keresendő karakterlánc legyen: Minta
  2. Rendeljünk egy numerical value(v)/weighta karaktert, amelyet a feladatban használni fogunk. Itt csak az első tíz ábécét vettük (azaz A-tól J-ig). Szövegsúlyok
  3. m a minta hossza, n pedig a szöveg hossza. Itt m = 10 and n = 3.
    legyen d a beviteli halmaz karaktereinek száma. Itt vettük az (A, B, C,…, J) bemeneti halmazt. Tehát d = 10. Feltételezhet bármilyen alkalmas d értéket.
  4. Számítsuk ki a minta hash értékét. A szöveg hash értéke
hash értéke a mintához (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

A fenti számítás során válasszon egy prímszámot (itt, 13) oly módon, hogy az összes számítást egypontos aritmetikával tudjuk elvégezni.

A modulus kiszámításának okát az alábbiakban adjuk meg.

  1. Számítsa ki az m méretű szövegablak hash értékét.
Az első ABC ablaknál a szöveg hash értéke (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Hasonlítsa össze a minta hash értékét a szöveg hash értékével. Ha akkor egyeznek, akkor a karakterillesztés történik.
    A fenti példákban az első ablak kivonatértéke (azaz t) megegyezik p-vel, tehát az ABC és a CDD közötti karakterillesztésre kell törekedni. Mivel nem egyeznek, menj a következő ablakhoz.
  2. A következő ablak kivonatolási értékét úgy számoljuk ki, hogy kivonjuk az első tagot és hozzáadjuk a következő tagot az alábbiak szerint.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Ennek a folyamatnak az optimalizálása érdekében az előző hash értéket a következő módon használjuk fel.

t = ((d * (t - v (eltávolítandó karakter) * h) + v (hozzáadandó karakter)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Hol , h = d m-1 = 10 3-1 = 100.
  1. BCC esetén t = 12 ( ≠ 6). Ezért lépjen a következő ablakra.
    Néhány keresés után megkapjuk az egyezést a CDA ablak ablakban a szövegben. Különböző ablakok hash értéke

Algoritmus

 n = t.hossz m = p. hosszúság h = dm-1 mod qp = 0 t0 = 0 i = 1-től mp-ig (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q s = 0-tól n-ig - m, ha p = ts, ha p (1… m) = t (s + 1… s + m), akkor nyomtassa ki a "mintát találtam" s s-t ts - t (s + 1) h) + t (s + m + 1)) mod q

Példák Python, Java és 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); )

A Rabin-Karp algoritmus korlátai

Hamis sláger

Ha a minta hash értéke megegyezik a szöveg ablakának hash értékével, de az ablak nem a tényleges minta, akkor azt hamis találatnak nevezzük.

A hamis találat növeli az algoritmus időbonyolultságát. A hamis találatok minimalizálása érdekében modulust használunk. Nagyban csökkenti a hamis találatot.

Rabin-Karp algoritmus komplexitás

A Rabin-Karp algoritmus átlagos esete és legjobb komplexitása O(m + n)a legrosszabb esetben O (mn).

A legrosszabb eset akkor fordul elő, amikor a hamis találatok száma az összes ablakban előfordul.

Rabin-Karp algoritmus alkalmazások

  • A mintaillesztéshez
  • Karaktersorozat kereséséhez nagyobb szövegben

érdekes cikkek...