Rabin-Karp algoritm

I den här handledningen lär du dig vad rabin-karp algoritm är. Dessutom hittar du arbetsexempel på rabin-karp-algoritm i C, C ++, Java och Python.

Rabin-Karp algoritm är en algoritm som används för att söka / matcha mönster i texten med en hash-funktion. Till skillnad från Naive strängmatchningsalgoritm, går den inte genom varje tecken i den inledande fasen, utan filtrerar de tecken som inte matchar och utför sedan jämförelsen.

En hash-funktion är ett verktyg för att mappa ett större inmatningsvärde till ett mindre utdatavärde. Detta utgångsvärde kallas hash-värdet.

Hur fungerar Rabin-Karp-algoritmen?

En sekvens av tecken tas och kontrolleras för möjligheten att det finns den önskade strängen. Om möjligheten hittas utförs teckenmatchning.

Låt oss förstå algoritmen med följande steg:

  1. Låt texten vara: Text
    Och strängen som ska sökas i ovanstående text vara: Mönster
  2. Låt oss tilldela a numerical value(v)/weightför de karaktärer som vi kommer att använda i problemet. Här har vi endast tagit de första tio alfabeten (dvs. A till J). Textvikter
  3. m vara längden på mönstret och n vara längden på texten. Här, m = 10 and n = 3.
    Låt d vara antalet tecken i ingångssatsen. Här har vi tagit inmatningsuppsättningen (A, B, C, …, J). Så d = 10. Du kan anta vilket lämpligt värde som helst för d.
  4. Låt oss beräkna hashvärdet för mönstret. Hash-värde för text
hashvärde för mönster (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

I beräkningen ovan väljer du ett primtal (här, 13) på ett sådant sätt att vi kan utföra alla beräkningar med en-precision aritmetik.

Anledningen till att beräkna modulen ges nedan.

  1. Beräkna hashvärdet för textfönstret med storlek m.
För det första fönstret ABC, hashvärde för text (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Jämför hashvärdet för mönstret med hashvärdet för texten. Om de matchar så utförs karaktärsmatchning.
    I exemplen ovan matchar hashvärdet för det första fönstret (dvs. t) med p så, gå till teckenmatchning mellan ABC och CDD. Eftersom de inte matchar så, gå till nästa fönster.
  2. Vi beräknar hashvärdet för nästa fönster genom att subtrahera den första termen och lägga till nästa term som visas nedan.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

För att optimera denna process använder vi det tidigare hashvärdet på följande sätt.

t = ((d * (t - v (tecken som ska tas bort) * h) + v (tecken som ska läggas till)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Var , h = d m-1 = 10 3-1 = 100.
  1. För BCC är t = 12 ( ≠ 6). Gå därför till nästa fönster.
    Efter några sökningar får vi matchningen för fönstret CDA i texten. Hash-värde för olika fönster

Algoritm

 n = t. längd m = p. längd h = dm-1 mod qp = 0 t0 = 0 för i = 1 till mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q för s = 0 till n - m om p = ts om p (1 … m) = t (s + 1 … s + m) skriva ut "mönster hittat vid position" s Om s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Python, Java och C / C ++ exempel

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

Begränsningar av Rabin-Karp-algoritmen

Rosig hit

När mönstrets hashvärde matchar hashvärdet för ett fönster i texten men fönstret inte är det aktuella mönstret kallas det en falsk träff.

Spurious hit ökar algoritmens tidskomplexitet. För att minimera falsk träff använder vi modul. Det minskar kraftigt den falska träffen.

Rabin-Karp algoritmkomplexitet

Rabin-Karp-algoritmens genomsnittliga fall och bästa fallskomplexitet är O(m + n)och komplexiteten i värsta fall är O (mn).

I värsta fall uppstår komplexitet när falska träffar förekommer ett nummer för alla fönster.

Rabin-Karp algoritmapplikationer

  • För mönstermatchning
  • För söksträng i en större text

Intressanta artiklar...