Algorithme de Rabin-Karp

Contrairement à l’algorithme naïf qui compare directement le motif à toutes les sous-chaînes du texte caractère par caractère, l’algorithme de Rabin-Karp va comparer des empreintes du motif aux empreintes des sous-chaînes du texte, de manière à faire des comparaisons et des sauts de sous-chaîne plutôt que de simples caractères.

Cet algorithme fonctionne bien dans de nombreux cas réels, mais peut atteindre des temps relativement longs dans certains cas marginaux comme la recherche d’un motif de 10000 "A" suivis d’un unique "B" dans un texte de 10 millions de "A" — dans ce cas, le temps atteint la pire complexité en O(mn).

L’algorithme naïf compare toutes les positions possibles :

algo_naif(texte, motif)
1.  n ← longueur(texte)
2.  m ← longueur(motif)
3. pour i de 1 à n-m+1 faire
4.    si texte[i..i+m-1] = motif[1..m]
5.       motif trouvé dans le texte à la position i
6. motif non trouvé

L’algorithme de Knuth–Morris–Pratt utilise un précalcul pour examiner une seule fois chaque élément du texte (l'augmentation de i d'une unité est remplacée par une augmentation de i à une position non encore examinée), avec une complexité en O(n).

L’algorithme de Boyer–Moore saute autant de caractères que possible à chaque échec de comparaison, ne faisant que n/m comparaisons dans le meilleur des cas.

L’algorithme de Rabin–Karp, lui, vise à accélérer la comparaison des lignes 5 et 6.

La comparaison des empreintes, évoquée ci-dessus, n’est pas suffisante, car limiter le nombre d’empreintes possibles (pour améliorer leur comparaison) conduit à ce que plusieurs motifs peuvent correspondre à la même empreinte. Il faut donc, quand les empreintes correspondent, comparer ensuite les chaînes elles-mêmes, ce qui augmente le temps global. L’objectif est donc de limiter ces comparaisons de chaînes, grâce à la fonction de hachage (voir ci-dessous).

En supposant que le texte T et le motif M sont représentés comme des tableaux de caractères, que la longueur de T est supérieure à celle de M, et en se donnant une fonction de hachage hach, l’algorithme de Rabin-Karp est le suivant :

rabin_karp(texte, motif)
 1.  n ← longueur(texte)
 2.  m ← longueur(motif)
 3.  hn ← hach(texte[1..m])
 4.  hm ← hach(motif[1..m])
 5.  pour i de 0 à n-m+1 faire
 6.    si hn = hm
 7.      si texte[i..i+m-1] = motif[1..m]
 8.        motif trouvé dans le texte à la position i
 9.    hn ← hach(texte[i+1..i+m])
10. motif non trouvé

Les lignes 3, 4, 7 et 9 sont toutes en O(m). Mais les lignes 3 et 4 ne sont exécutées qu’une seule fois, et la ligne 7 uniquement quand les empreintes correspondent, ce qui devrait être rare. La ligne 6 est exécutée n fois, mais requiert un temps constant. La ligne coûteuse est donc la ligne 9.

Recalculer naïvement l’empreinte pour la sous-chaîne T[i+1..i+m] nécessiterait un temps en O(m), et comme cela est fait à chaque boucle, l’algorithme serait en O(mn), comme l’algorithme naïf. L’astuce ici est de remarquer que la variable hn contient déjà l’empreinte de T[i..i+m-1]. S’il est possible de l’utiliser pour calculer la prochaine empreinte avec un temps fixe, alors le problème serait résolu.

Pour cela, il faut utiliser une fonction de hachage déroulante (en). Il s’agit d’une fonction de hachage spécialement conçue pour permettre une telle opération. Un exemple simple est l’addition des valeurs de chaque caractère de la sous-chaîne. Ainsi, il est possible d’utiliser cette formule pour calculer la prochaine empreinte, dans un temps constant :

T[i+1..i+m] = T[i..i+m-1] - T[i] + T[i+m]

Cette fonction simpliste fonctionne, mais risque de produire un passage plus fréquent dans la ligne 7 que des fonctions plus sophistiquées, comme celles présentées dans le chapitre suivant.

Notez bien qu’en cas de malchance, ou de très mauvaise fonction de hachage, la ligne 7 pourrait être exécutée n fois, à chaque passage dans la boucle ; et comme elle est en O(m), l’algorithme sera finalement en O(nm).

L’algorithme de Rabin–Karp est inférieur à celui de Knuth–Morris–Pratt, de Boyer–Moore ou d’autres, pour la recherche d’un motif unique, du fait de son comportement dans les pires cas. Cependant, c’est un algorithme à privilégier pour la recherche de motifs multiples.

Ainsi, pour rechercher un grand nombre k de motifs de longueur fixe dans un texte, on peut créer une variante simple de l’algorithme Rabin–Karp qui utilise un filtre de Bloom ou une structure de données Ensemble pour vérifier si l’empreinte d’une chaîne donnée appartient à un ensemble d’empreintes des motifs recherchés, avec le texte T, un ensemble de motifs M de longueur m :

   rabin_karp_ensemble(T, M, m)
1. n ← longueur(T)
2. hm ← ensemble vide
3. pour chaque S de l’ensemble M faire
4.   ajoute hach(S[1..m]) à hm
5. ht ← hach(T[1..m])
6. pour i de 1 à n-m+1 faire
7.   si ht ∈ hm et T[i..i+m-1] ∈ M
8.     résultat trouvé : i
9.   ht ← hach(T[i+1..i+m])
10. résultat non trouvé

Par rapport à la façon naïve de rechercher k motifs en répétant une recherche mono-motif en O(n), ce qui aboutit à une recherche en O(n k), la variante de l’algorithme ci-dessus peut trouver tous les k motifs en O(n+k) attendus, car une table d’empreintes permet de vérifier si l’empreinte d’une sous-chaîne est celle d’un des motifs en O(1).

• Richard M. Karp et Michael O. Rabin, « Efficient randomized pattern-matching algorithms », IBM Journal of Research and Development, vol. 31, n^o 2,‎ mars 1987, p. 249–260 (DOI 10.1147/rd.312.0249, lire en ligne, consulté le 24 septembre 2013)
• (en) Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L. et Stein, Clifford, Introduction to Algorithms, Cambridge, Massachusetts, MIT Press, 2001, 2nd éd. (1^re éd. 1990), 1180 p. (ISBN 978-0-262-03293-3), « The Rabin–Karp algorithm », p. 911–916.