algorithme de Rabin-Karp

L’algorithme de Rabin-Karp ou 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. Pour un texte d’une longueur de n caractères, et p sous-chaînes d’une longueur totale de 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). 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+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.