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.

Sommaire

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Rabin-Karp de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme De Rabin-Karp — L algorithme de Rabin Karp est un algorithme de recherche de chaînes de caractères crée 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 à du hachage. L algorithme n est pas …   Wikipédia en Français

  • Algorithme de rabin-karp — L algorithme de Rabin Karp est un algorithme de recherche de chaînes de caractères crée 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 à du hachage. L algorithme n est pas …   Wikipédia en Français

  • Algorithme De Recherche De Sous-chaîne — Un algorithme de recherche de sous chaine est un type d algorithme de recherche qui a pour objectif de trouver une chaîne de caractères à l intérieur d une autre. Un tel algorithme fournit la position du premier caractère de la sous chaîne… …   Wikipédia en Français

  • Algorithme de recherche de sous-chaine — Algorithme de recherche de sous chaîne Un algorithme de recherche de sous chaine est un type d algorithme de recherche qui a pour objectif de trouver une chaîne de caractères à l intérieur d une autre. Un tel algorithme fournit la position du… …   Wikipédia en Français

  • Algorithme De Boyer-Moore — L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme 2.1 Pré traitement …   Wikipédia en Français

  • Algorithme de boyer-moore — L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme 2.1 Pré traitement …   Wikipédia en Français

  • Algorithme de recherche de chaîne de caractères de Boyer-Moore — Algorithme de Boyer Moore L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme …   Wikipédia en Français

  • Algorithme de recherche de sous-chaîne de Boyer-Moore — Algorithme de Boyer Moore L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme …   Wikipédia en Français

  • Algorithme De Knuth-Morris-Pratt — L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside en un pré traitement de la chaîne …   Wikipédia en Français

  • Algorithme de Knuth-Pratt-Morris — Algorithme de Knuth Morris Pratt L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”