Algorithme de rabin-karp
- Algorithme de rabin-karp
-
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 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 sous-chaînes multiples.
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). 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.
Utilisation pratique
L'une des applications pratiques les plus simples est la détection de plagiats. Si un professeur suspecte un étudiant d'avoir repris le travail d'autrui, alors il peut utiliser l'algorithme de Rabin-Karp. Il faut d'abord procéder à une extraction des chaînes sources (celles du texte original), en tenant compte ou en ignorant certains détails (ponctuations, majuscules, etc.). Ensuite, l'algorithme de Rabin-Karp appliqué sur le texte de l'étudiant permet de trouver toute chaîne provenant de la source. Comme le nombre de chaînes recherchées, k est très grand, les algorithmes qui se contentent de rechercher une seule chaîne ne sont pas adaptés.
Portail de l’informatique
Catégories : Hachage | Algorithme sur les chaînes de caractères
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éé 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… … 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 KMP — 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
