Algorithme de Rabin-Karp

L’algorithme de Rabin-Karp ou algorithme de Karp-Rabin est un algorithme de recherche de sous-chaîne créé par Richard M. Karp et Michael O. Rabin (1987). Cette méthode recherche un ensemble de motifs donnés (c’est-à-dire des sous-chaînes) dans un texte grâce à une fonction de hachage. L’algorithme n’est pas beaucoup employé pour les recherches d’une unique sous-chaîne mais a une importance théorique et s’avère très efficace pour des recherches de multiples sous-chaînes.

Pour un texte d’une longueur de n caractères, et p sous-chaînes d’une longueur totale m, sa complexité moyenne est en O(n+m) pour une utilisation mémoire en O(p). Mais, dans le pire des cas, sa complexité est de O(nm), ce qui explique son utilisation relativement limitée. En comparaison, l’algorithme de recherche de chaînes d’Aho-Corasick a une complexité asymptotique, dans le pire des cas, en O(n+m) pour une utilisation mémoire en O(m).

L'algorithme de Karp-Rabin a l’avantage d’être capable de trouver dans un texte une sous-chaîne présente dans un ensemble de k chaînes, avec une complexité moyenne de O(n+m) indépendamment de la taille de k. Ainsi, son efficacité pour les recherches de multiples sous-chaînes, sans tenir compte de la casse ou de la ponctuation, le rend utile pour la détection de plagiat.

Description

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

Comparaison avec les autres algorithmes

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.

Pseudo-code

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é

Complexité

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

Choix d’une bonne fonction de hachage

Exemple d’une bonne fonction de hachage

Si l’on représente les caractères comme des nombres dans une base b donnée (en pratique si l’encodage des caractères se fait sur 8 bits, ce qui donne 256 caractères possibles, on utilisera une base 256) et que l’on choisit un nombre entier q approprié, une fonction de hachage est :

hash(t) = t modulo q

où t est la représentation du texte comme un nombre dans la base b.

Par exemple, prenons le texte suivant composé de chiffres décimaux :

6 5 8 2 4 6 9 1 3

On choisit la base 10 et le représentant du texte dans cette base sera naturellement le nombre :

658246913

Si l’on choisit le nombre 11, la fonction de hachage sera :

hash(t) = t modulo 11

soit

hash(658246913) = 658246913 modulo 11
                = 5

Cette fonction de hachage a la propriété de pouvoir calculer facilement l’empreinte de T[i+1..j+1] en fonction de celle de T[i..j]. Dans l’exemple précédent, si l’on veut exprimer hash(582) en fonction de hash(658), on peut constater que

582 = 58×10 + 2 = (658 - 600) × 10 + 2

d’où

hash(582) = [ (hash(658) - hash(600)) × 10 + 2 ] modulo 11

Cet exemple se généralise dans une base quelconque avec un nombre entier q quelconque. Ainsi, dans le pseudo-code précédent, pour i ⩾ 1, on peut procéder ainsi pour mettre à jour la variable h_T avec l’empreinte de T[i+1..i+l_M] en utilisant celle de la sous-chaîne précédente, déjà calculée :

hT ← (hT - T[i]×blM-1) × b + T[i+lM] modulo q

Empreinte de Rabin

L’empreinte de Rabin est une fonction de hachage roulante populaire et efficace pour l’algorithme de Rabin-Karp, dont la performance est directement liée à l’efficacité du calcul des empreintes des sous-chaînes successives du texte. Cette fonction traite chaque sous-chaîne comme un nombre dans une base donnée, en général un grand nombre premier. Par exemple, si la sous-chaîne est « ha » et la base 101, l’empreinte sera 104 × 101¹ + 97 × 101⁰ = 10601 (ASCII de 'h' est 104 et celui de 'a' est 97).

L’intérêt essentiel d’utiliser une telle fonction est qu’elle permet de calculer l’empreinte de la sous-chaîne suivante à partir de la précédente en un nombre constant d’opérations, indépendamment de la longueur des sous-chaînes.

Par exemple, avec le texte « abracadabra » et la recherche d’un motif de 3 caractères, l’empreinte de la première sous-chaîne, « abr », en utilisant la base 101, est :

// ASCII a = 97, b = 98, r = 114.
hach(« abr ») = (97 × 1012) + (98 × 1011) + (114 × 1010) = 999509

L’empreinte de la sous-chaîne suivante, « bra », depuis l’empreinte de « abr », se calcule en soustrayant le nombre ajouté pour le premier 'a' de « abr », soit 97 × 101², en multipliant par la base et en ajoutant le dernier 'a' de « bra », soit 97 × 101⁰, de cette façon :

//             base   empreinte  ancien 'a'       nouveau 'a'
hach(« bra ») = [101 × (999509 - (97 × 1012))] + (97 × 1010) = 1011309

Si les sous-chaînes en question sont longues, cet algorithme économise beaucoup de temps par rapport à d’autres fonctions de hachage.

En théorie, il existe d’autres algorithmes qui peuvent permettre un recalcul facile, comme multiplier entre elles les valeurs ASCII de chaque caractère de manière que le décalage de la sous-chaîne n’entraîne qu’une division par le premier caractère et une multiplication par le dernier. La limite vient alors de la restriction de taille du type entier et de la nécessité d’utiliser l’arithmétique modulaire pour réduire les résultats des empreintes (voir l’article fonction de hachage). A contrario, les fonctions de hachage simples ne produisent pas très vite de grands nombres mais, comme l’addition simple des valeurs ASCII, risquent de provoquer de nombreuses collisions d’empreinte et donc de ralentir l’algorithme. D’où la préférence pour la fonction décrite ci-dessus pour l’algorithme Rabin–Karp.

Extension de l’algorithme à la recherche de multiples sous-chaînes

L’algorithme de Rabin–Karp est inférieur^[Quoi ?] à 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).

Notes et références

• 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.