Algoritmo di Rabin-Karp

In questo tutorial imparerai cos'è l'algoroitmo rabin-karp. Inoltre, troverai esempi funzionanti dell'algoritmo rabin-karp in C, C ++, Java e Python.

L'algoritmo Rabin-Karp è un algoritmo utilizzato per cercare / abbinare modelli nel testo utilizzando una funzione hash. A differenza dell'algoritmo di corrispondenza delle stringhe Naive, non viaggia attraverso tutti i caratteri nella fase iniziale, ma filtra i caratteri che non corrispondono e quindi esegue il confronto.

Una funzione hash è uno strumento per mappare un valore di input più grande a un valore di output più piccolo. Questo valore di output è chiamato valore hash.

Come funziona l'algoritmo di Rabin-Karp?

Viene presa una sequenza di caratteri e verificata la possibilità della presenza della stringa richiesta. Se viene trovata la possibilità, viene eseguita la corrispondenza dei caratteri.

Cerchiamo di capire l'algoritmo con i seguenti passaggi:

  1. Lascia che il testo sia: Testo
    E la stringa da cercare nel testo sopra sia: Pattern
  2. Assegniamo una numerical value(v)/weightper i caratteri che useremo nel problema. Qui abbiamo preso solo i primi dieci alfabeti (cioè dalla A alla J). Pesi del testo
  3. m è la lunghezza del motivo en la lunghezza del testo. Qui, m = 10 and n = 3.
    sia d il numero di caratteri nel set di input. Qui, abbiamo preso l'insieme di input (A, B, C,…, J). Così, d = 10. Puoi assumere qualsiasi valore adatto per d.
  4. Calcoliamo il valore hash del pattern. Valore hash del testo
valore hash per pattern (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

Nel calcolo sopra, scegli un numero primo (qui, 13) in modo tale da poter eseguire tutti i calcoli con aritmetica a precisione singola.

La ragione per il calcolo del modulo è fornita di seguito.

  1. Calcola il valore hash per la finestra di testo di dimensione m.
Per la prima finestra ABC, valore hash per il testo (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Confronta il valore hash del pattern con il valore hash del testo. Se corrispondono, viene eseguita la corrispondenza dei caratteri.
    Negli esempi precedenti, il valore hash della prima finestra (cioè t) corrisponde a p quindi, vai per la corrispondenza dei caratteri tra ABC e CDD. Dal momento che non corrispondono, vai alla finestra successiva.
  2. Calcoliamo il valore hash della finestra successiva sottraendo il primo termine e aggiungendo il termine successivo come mostrato di seguito.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Per ottimizzare questo processo, utilizziamo il valore hash precedente nel modo seguente.

t = ((d * (t - v (carattere da rimuovere) * h) + v (carattere da aggiungere)) mod 13 = ((10 * (6-1 * 9) + 3) mod 13 = 12 Dove , h = d m-1 = 10 3-1 = 100.
  1. Per BCC, t = 12 ( ≠ 6). Quindi, vai alla finestra successiva.
    Dopo alcune ricerche, otterremo la corrispondenza per la finestra CDA nel testo. Valore hash di diverse finestre

Algoritmo

 n = t. lunghezza m = p. lunghezza h = dm-1 mod qp = 0 t0 = 0 per i = 1 a mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q per s = 0 an - m se p = ts se p (1… m) = t (s + 1… s + m) stampa "modello trovato alla posizione" s Se s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Esempi di Python, Java e 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); )

Limitazioni dell'algoritmo di Rabin-Karp

Colpo spurio

Quando il valore hash del pattern corrisponde al valore hash di una finestra del testo ma la finestra non è il pattern effettivo, viene chiamato hit spurio.

Il colpo spurio aumenta la complessità temporale dell'algoritmo. Per ridurre al minimo i colpi spuri, utilizziamo il modulo. Riduce notevolmente il colpo spurio.

Complessità dell'algoritmo di Rabin-Karp

Il caso medio e la complessità del caso migliore dell'algoritmo di Rabin-Karp sono O(m + n)e la complessità del caso peggiore è O (mn).

La complessità del caso peggiore si verifica quando si verificano colpi spuri con un numero per tutte le finestre.

Applicazioni dell'algoritmo di Rabin-Karp

  • Per la corrispondenza del modello
  • Per cercare una stringa in un testo più grande

Articoli interessanti...