Algorithme de Rabin-Karp

L'algorithme de Rabin-Karp est un algorithme de recherche de chaînes de caractères créé par Michael O. Rabin et Richard M. Karp. Cette méthode recherche un motif donné (ie. 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.

Description

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 couteux qu'une comparaison.

Pseudo-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. hT ← hach(T[1..lM])
 4. hM ← hach(M[1..lM])
 5. pour i ← 0 à lT-lM faire
 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
11.     si i < lT - lM alors
12.         hT ← hach(T[i+2..i+lM+1])
13.     fin si
14. fin pour

Choix d'une bonne fonction de hachage

Dans l'algorithme ci-dessus, on recalcule la fonction de hachage pour chaque sous-chaîne du texte dont la longueur est celle du motif. Un gain de performance important peut être effectué si l'on utilise une fonction de hachage qui a la propriété que l'on puisse facilement calculer T[i+1..j+1] en fonction de T[i..j]. De telles fonctions de hachage existent.

Exemple d'une bonne fonction de hachage

Si l'on représente les caractères comme des chiffres dans une base donnée b (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 choisi un nombre entier q approprié, la fonction de hachage est :

hach(t) = t modulo (q) où est la représentation du texte comme un nombre dans la base b.

Montrons plutôt un exemple : prenons le texte suivant composé de chiffre décimaux :

6 5 8 2 4 6 9 1 3

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

658246913

Si l'on choisi le nombre 11, la fonction de hachage sera :

hach(t) = t modulo(11)
soit 
hach(658246913) = 658246913 modulo(11)
                = 5

Cette fonction de hachage a la propriété de pouvoir calculer facilement T[i+1..j+1] en fonction de T[i..j]. Dans l'exemple de tout à l'heure, si l'on veut exprimer hash(658) en fonction de hash(582), on peut constater que

582 = ((658-600) * 10) + 2 = 10 * ( 658 - 600 ) + 2, d'où
hach(582) = 10 * ( hach(658) - 600 ) + 2 modulo(11)

Cette exemple se généralise dans une base quelconque et un nombre entier q quelconque. De cette façon, on peut remplacer la ligne 12. du pseudo-code de l'algorithme par

12'.    hT ← (d(hT - T[i+1]dlM-1) + T[i+lM+1] modulo(q)

Complexité

Extension de l'algorithme à la recherche de multiple sous-chaîne

• Portail de l’algorithmique
• Portail de l’informatique