Algorithme de Rabin-Karp
algorithme de recherche de sous-chaîne / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur Algorithme de Rabin-Karp?
Résumez cet article pour un enfant de 10 ans
L’algorithme de Rabin-Karp ou algorithme de Karp-Rabin est un algorithme de recherche de sous-chaîne créé par Richard M. Karp et Michael O. Rabin (1987). Cette méthode recherche un ensemble de motifs donnés (c’est-à-dire des sous-chaînes) dans un texte grâce à une fonction de hachage. L’algorithme n’est pas beaucoup employé pour les recherches d’une unique sous-chaîne mais a une importance théorique et s’avère très efficace pour des recherches de multiples sous-chaînes.
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
Pour un texte d’une longueur de n caractères, et p sous-chaînes d’une longueur totale m, sa complexité moyenne est en O(n+m) pour une utilisation mémoire en O(p). Mais, dans le pire des cas, sa complexité est de O(nm), ce qui explique son utilisation relativement limitée. En comparaison, l’algorithme de recherche de chaînes d’Aho-Corasick a une complexité asymptotique, dans le pire des cas, en O(n+m) pour une utilisation mémoire en O(m).
L'algorithme de Karp-Rabin 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+m) indépendamment de la taille de k. Ainsi, son efficacité pour les recherches de multiples sous-chaînes, sans tenir compte de la casse ou de la ponctuation, le rend utile pour la détection de plagiat.