Algorithme de Rabin-Karp
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
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.
[modifier] 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.
