Rabin-Karpi algoritm

Selles õpetuses saate teada, mis on rabin-karpi algoritm. Samuti leiate C, C ++, Java ja Pythoni rabin-karpi algoritmi toimivad näited.

Rabin-Karpi algoritm on algoritm, mida kasutatakse tekstis mustrite otsimiseks / sobitamiseks räsifunktsiooni abil. Erinevalt naiivsest stringide sobitamise algoritmist ei liigu see algfaasis läbi iga tähemärgi, pigem filtreerib need tähemärgid, mis ei ühti, ja teostab seejärel võrdluse.

Räsifunktsioon on tööriist suurema sisendväärtuse kaardistamiseks väiksema väljundväärtusega. Seda väljundväärtust nimetatakse räsiväärtuseks.

Kuidas Rabin-Karpi algoritm töötab?

Võetakse märkide jada ja kontrollitakse, kas on olemas vajalik string. Kui võimalus leitakse, viiakse läbi märkide sobitamine.

Mõistame algoritmi järgmiste sammudega:

  1. Olgu tekst järgmine: Tekst
    Ja ülaltoodud tekstist otsitav string on: Muster
  2. Määrake numerical value(v)/weighttähemärgid, mida probleemis kasutame. Siin oleme võtnud ainult kümme esimest tähestikku (st A kuni J). Teksti kaalud
  3. m on mustri pikkus ja n teksti pikkus. Siin m = 10 and n = 3.
    olgu D. märkide arvu sisend komplekti. Siin on võetud sisendkomplekt (A, B, C,…, J). Niisiis, d = 10. Võite eeldada, et d jaoks on sobiv väärtus.
  4. Arvutame mustri räsi väärtuse. Teksti räsi väärtus
mustri räsiväärtus (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

Valige ülaltoodud arvutuses algarv (siin, 13) nii, et saaksime kõik arvutused läbi viia ühe täppisaritmeetikaga.

Mooduli arvutamise põhjus on toodud allpool.

  1. Arvutage suuruse m tekstiakna räsi väärtus.
Esimese akna ABC puhul räsiväärtus tekstile (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Võrrelge mustri räsiväärtust teksti räsiväärtusega. Kui need sobivad, viiakse läbi märkide sobitamine.
    Ülaltoodud näidetes sobib esimese akna räsi väärtus (st t) p-ga, nii et minge ABC ja CDD märkide sobitamiseks. Kuna need ei ühti, minge järgmise akna juurde.
  2. Järgmise akna räsiväärtuse arvutame, lahutades esimese termini ja lisades järgmise termini, nagu allpool näidatud.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Selle protsessi optimeerimiseks kasutame eelmist räsiväärtust järgmisel viisil.

t = ((d * (t - v (eemaldatav märk) * h) + v (lisatav märk)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Kus , h = d m-1 = 10 3-1 = 100.
  1. BCC korral t = 12 ( ≠ 6). Seetõttu minge järgmise akna juurde.
    Mõne otsingu järel saame tekstis vaste akna CDA-le. Erinevate akende räsiväärtus

Algoritm

 n = t.pikkus m = p.pikkus h = dm-1 mod qp = 0 t0 = 0 i = 1 kuni mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q s = 0 kuni n - m jaoks, kui p = ts, kui p (1… m) = t (s + 1… s + m) printige "positsioonist leitud muster" s Kui s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Pythoni, Java ja C / C ++ näited

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-Karpi algoritmi piirangud

Võluhitt

Kui mustri räsi väärtus langeb kokku teksti akna räsiväärtusega, kuid aken pole tegelik muster, nimetatakse seda valelöögiks.

Võltsitud tabamus suurendab algoritmi ajalist keerukust. Võltsitud löögi minimeerimiseks kasutame moodulit. See vähendab valelööki oluliselt.

Rabin-Karpi algoritmi keerukus

Rabin-Karpi algoritmi keskmine juhtum ja parimal juhul keerukus on O(m + n)ning halvimal juhul O (mn).

Halvim keerukus tekib siis, kui võltsitud tabamused esinevad kõigi akende jaoks arvuga.

Rabin-Karpi algoritmirakendused

  • Mustri sobitamiseks
  • Stringi otsimiseks suuremast tekstist

Huvitavad Artiklid...