Rabin-Karpin algoritmi

Tässä opetusohjelmassa opit, mikä on rabin-karp-algoritmi. Löydät myös toimivia esimerkkejä rabin-karp-algoritmista C, C ++, Java ja Python.

Rabin-Karp-algoritmi on algoritmi, jota käytetään tekstin kuvioiden etsimiseen / sovittamiseen hash-funktiolla. Toisin kuin naiivi merkkijonojen vastaavuusalgoritmi, se ei kulje jokaisen merkin läpi alkuvaiheessa, vaan suodattaa merkit, jotka eivät täsmää, ja suorittaa sitten vertailun.

Hajautusfunktio on työkalu suuremman syöttöarvon kartoittamiseen pienempään lähtöarvoon. Tätä lähtöarvoa kutsutaan hash-arvoksi.

Kuinka Rabin-Karpin algoritmi toimii?

Merkkijono otetaan ja tarkistetaan vaaditun merkkijonon olemassaolon mahdollisuuden varalta. Jos mahdollisuus löytyy, suoritetaan merkkien sovitus.

Ymmärretään algoritmi seuraavilla vaiheilla:

  1. Olkoon teksti: Teksti
    Ja yllä olevasta tekstistä haettava merkkijono on: Kuvio
  2. Määritä a numerical value(v)/weightmerkille, jota käytämme tehtävässä. Tässä olemme ottaneet vain kymmenen ensimmäistä aakkosta (ts. A - J). Tekstin painot
  3. m on kuvion pituus ja n on tekstin pituus. Täällä m = 10 and n = 3.
    Olkoon D merkkien määrä tulo asetettu. Tässä olemme ottaneet tulojoukon (A, B, C,…, J). Joten d = 10. Voit olettaa minkä tahansa sopivan arvon d: lle.
  4. Lasketaan mallin hajautusarvo. Hash arvo tekstiä
hash-arvo kuviolle (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

Valitse yllä olevassa laskelmassa alkuluku (tässä, 13) siten, että voimme suorittaa kaikki laskelmat yhden tarkkuuden aritmeettisesti.

Syy moduulin laskemiseen annetaan alla.

  1. Laske hash-arvo teksti-ikkunalle, jonka koko on m.
Ensimmäisessä ikkunassa ABC tekstin hash-arvo (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Vertaa kuvion hajautusarvoa tekstin hajautusarvoon. Jos ne sopivat yhteen, suoritetaan merkkien sovitus.
    Edellä olevissa esimerkeissä ensimmäisen ikkunan hajautusarvo (ts. T) vastaa p: tä, joten mene ABC: n ja CDD: n merkkien sovittamiseen. Koska ne eivät täsmää, siirry seuraavaan ikkunaan.
  2. Lasketaan seuraavan ikkunan hajautusarvo vähentämällä ensimmäinen termi ja lisäämällä seuraava termi alla olevan kuvan mukaisesti.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Tämän prosessin optimoimiseksi käytämme edellistä hajautusarvoa seuraavalla tavalla.

t = ((d * (t - v (poistettava merkki) * h) + v (lisättävä merkki)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Missä , h = d m-1 = 10 3-1 = 100.
  1. BCC: lle t = 12 ( ≠ 6). Siksi siirry seuraavaan ikkunaan.
    Muutaman haun jälkeen saamme tekstin ikkunan CDA vastaavuuden. Eri ikkunoiden hash-arvo

Algoritmi

 n = t.pituus m = p. pituus h = dm-1 mod qp = 0 t0 = 0 i = 1 - mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q arvolle s = 0 - n - m, jos p = ts, jos p (1… m) = t (s + 1… s + m) tulosta "kuvio löytyy paikasta" s Jos s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Python-, Java- ja C / C ++ -esimerkkejä

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-algoritmin rajoitukset

Väärä hitti

Kun kuvion hajautusarvo vastaa tekstin ikkunan hajautusarvoa, mutta ikkuna ei ole varsinainen kuvio, sitä kutsutaan vääräksi osumaksi.

Väärät osumat lisäävät algoritmin aikakompleksisuutta. Väärän osuman minimoimiseksi käytämme moduulia. Se vähentää huomattavasti väärää osumaa.

Rabin-Karpin algoritmin monimutkaisuus

Rabin-Karp-algoritmin keskimääräinen tapaus ja parhaan tapauksen monimutkaisuus on O(m + n)ja pahimmassa tapauksessa O (mn).

Pahimmassa tapauksessa monimutkaisuus tapahtuu, kun väärät osumat esiintyvät kaikissa ikkunoissa.

Rabin-Karpin algoritmisovellukset

  • Kuvion sovittamiseen
  • Merkkijonon etsimiseen isommasta tekstistä

Mielenkiintoisia artikkeleita...