Algorithme de Rabin-Karp

Dans ce tutoriel, vous apprendrez ce qu'est l'algoroithme rabin-karp. Vous trouverez également des exemples fonctionnels de l'algorithme rabin-karp en C, C ++, Java et Python.

L'algorithme de Rabin-Karp est un algorithme utilisé pour rechercher / faire correspondre des motifs dans le texte à l'aide d'une fonction de hachage. Contrairement à l'algorithme de correspondance de chaînes naïves, il ne parcourt pas tous les caractères de la phase initiale, mais filtre les caractères qui ne correspondent pas, puis effectue la comparaison.

Une fonction de hachage est un outil pour mapper une valeur d'entrée plus grande à une valeur de sortie plus petite. Cette valeur de sortie est appelée la valeur de hachage.

Comment fonctionne l'algorithme de Rabin-Karp?

Une séquence de caractères est prise et vérifiée pour la possibilité de la présence de la chaîne requise. Si la possibilité est trouvée, la correspondance des caractères est effectuée.

Comprenons l'algorithme avec les étapes suivantes:

  1. Soit le texte: Texte
    Et la chaîne à rechercher dans le texte ci-dessus soit: Motif
  2. Attribuons un numerical value(v)/weightpour les caractères que nous utiliserons dans le problème. Ici, nous n'avons pris que les dix premiers alphabets (c'est-à-dire de A à J). Poids du texte
  3. m la longueur du motif et n la longueur du texte. Ici, m = 10 and n = 3.
    Soit d le nombre de caractères dans le jeu d'entrée. Ici, nous avons pris l'ensemble des entrées (A, B, C,…, J). Ainsi, d = 10. Vous pouvez prendre toute valeur appropriée pour d.
  4. Calculons la valeur de hachage du motif. Valeur de hachage du texte
valeur de hachage pour le motif (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

Dans le calcul ci-dessus, choisissez un nombre premier (ici, 13) de manière à pouvoir effectuer tous les calculs avec l'arithmétique simple précision.

La raison du calcul du module est donnée ci-dessous.

  1. Calculez la valeur de hachage pour la fenêtre de texte de taille m.
Pour la première fenêtre ABC, valeur de hachage pour le texte (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. Comparez la valeur de hachage du modèle avec la valeur de hachage du texte. S'ils correspondent alors, la correspondance des caractères est effectuée.
    Dans les exemples ci-dessus, la valeur de hachage de la première fenêtre (c'est-à-dire t) correspond à p donc, optez pour une correspondance de caractères entre ABC et CDD. Puisqu'ils ne correspondent pas, passez à la fenêtre suivante.
  2. Nous calculons la valeur de hachage de la fenêtre suivante en soustrayant le premier terme et en ajoutant le terme suivant comme indiqué ci-dessous.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Afin d'optimiser ce processus, nous utilisons la valeur de hachage précédente de la manière suivante.

t = ((d * (t - v (caractère à supprimer) * h) + v (caractère à ajouter)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Où , h = d m-1 = 10 3-1 = 100.
  1. Pour BCC, t = 12 ( ≠ 6). Par conséquent, passez à la fenêtre suivante.
    Après quelques recherches, nous obtiendrons la correspondance pour la fenêtre CDA dans le texte. Valeur de hachage de différentes fenêtres

Algorithme

 n = t.longueur m = p.longueur h = dm-1 mod qp = 0 t0 = 0 pour i = 1 à mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q pour s = 0 à n - m si p = ts si p (1… m) = t (s + 1… s + m) imprime "motif trouvé à la position" s Si s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Exemples Python, Java et 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); )

Limitations de l'algorithme de Rabin-Karp

Coup faux

Lorsque la valeur de hachage du motif correspond à la valeur de hachage d'une fenêtre du texte mais que la fenêtre n'est pas le motif réel, cela s'appelle un faux hit.

Un faux coup augmente la complexité temporelle de l'algorithme. Afin de minimiser les coups parasites, nous utilisons le module. Cela réduit considérablement le faux coup.

Complexité de l'algorithme de Rabin-Karp

Le cas moyen et la complexité du meilleur cas de l'algorithme de Rabin-Karp sont O(m + n)et la complexité du pire des cas est O (mn).

La complexité du pire des cas se produit lorsque des hits parasites se produisent un nombre pour toutes les fenêtres.

Applications de l'algorithme Rabin-Karp

  • Pour la correspondance de motifs
  • Pour rechercher une chaîne dans un texte plus grand

Articles intéressants...