Algorithme de Rabin-Karp

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme de Rabin-Karp ou Karp-Rabin est un algorithme de recherche de chaînes de caractères créé par Richard M. Karp et Michael O. Rabin (1987). Cette méthode recherche un motif donné (c'est-à-dire une sous-chaîne) dans un texte grâce à une fonction de hachage. L'algorithme n'est pas beaucoup employé pour les recherches d'une seule 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 une sous-chaîne d'une longueur m, sa complexité moyenne est de O(n+m). Sa complexité dans le pire des cas est de O(nm) ce qui explique son utilisation relativement limitée. Toutefois, il 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), indépendamment de la taille de k.

Son efficacité pour les recherches de multiples sous-chaînes le rend utile pour la détection de plagiat.

Description[modifier | modifier le code]

Contrairement à l'algorithme naïf qui compare directement le motif à toutes les sous-chaînes du texte, l'algorithme de Rabin-Karp va comparer des hachages du motif aux hachage des sous-chaîne du texte, l'utilisation d'une fonction de hachage pouvant être moins coûteux qu'une comparaison.

Pseudo-code[modifier | modifier le code]

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 un fonction de hachage hach on peut écrire l'algorithme de Rabin-Karp de cette façon :

    rabin_karp(T, M, h)
 1. lT ← longueur(T)
 2. lM ← longueur(M)
 3. hM ← hach(M[1..lM])
 4. pour i ← 0 à lT-lM faire
 5.     hT ← hach(T[i+1..i+lM])
 6.     si hT = hM alors
 7.         si M[1..lM] = T[i+1..i+lM] alors
 8.            afficher « le motif est présent à la position » i
 9.         fin si
10.     fin si
12. fin pour

Choix d'une bonne fonction de hachage[modifier | modifier le code]

Dans l'algorithme ci-dessus, on appelle la fonction de hachage pour chaque sous-chaîne du texte de la longueur du motif. Un gain de performance important peut être effectué si l'on utilise une fonction de hachage qui permet de calculer facilement l'empreinte de T[i+1..j+1] en fonction de celle T[i..j].

Exemple d'une bonne fonction de hachage[modifier | modifier le code]

Si l'on représente les caractères comme des nombres dans une base b donnée (en pratique si l'encodage de 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

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

Par exemple, prenons le texte suivant composé de chiffre 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) - 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 hT avec l'empreinte de T[i+1..i+lM] 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

Complexité[modifier | modifier le code]

Extension de l'algorithme à la recherche de multiple sous-chaîne[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Notes et références[modifier | modifier le code]