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.
L'algorithme de Boyer-Moore (L'algorithme de Boyer-Moore est un algorithme de recherche de sous-chaîne...) pré-traite la sous-chaîne (c'est-à-dire la chaîne (Le mot chaîne peut avoir plusieurs significations :) recherchée), et non pas le texte (c'est-à-dire la chaîne dans laquelle la recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue...) est effectuée), à l'inverse (En mathématiques, l'inverse d'un élément x d'un ensemble muni d'une loi de...) de certains algorithmes, qui amortissent le coût du prétraitement du texte en effectuant de très nombreuses recherches répétitives. Le coût d'exécution de l'algorithme de Boyer-Moore peut être sub-linéaire, c'est-à-dire qu'il n'a pas besoin (Les besoins se situent au niveau de l'interaction entre l'individu et l'environnement. Il est...) de vérifier chacun des caractères du texte, mais peut au contraire sauter certains d'entre eux. En général, l'algorithme devient plus rapide lorsque la longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus...) de la sous-chaîne s'allonge. Cette efficacité provient du fait que, pour chaque tentative infructueuse de correspondance (La correspondance est un échange de courrier généralement prolongé sur une longue période. Le...) entre les deux chaînes (texte et sous-chaîne), il utilise les informations déduites de cet échec pour éliminer le plus grand nombre (La notion de nombre en linguistique est traitée à l’article « Nombre...) possible de positions à vérifier.
En comparaison des méthodes de recherches basiques par la méthode de « force brute » (qui recherche la sous-chaîne en commençant par chercher partout dans le texte une correspondance du premier caractère de la sous-chaîne, puis en vérifiant si les caractères suivants correspondent) et dont la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par...) en temps (Le temps est un concept développé par l'être humain pour appréhender le...) (calculée par exemple selon le nombre de paires de caractères à comparer) croit en O(L · K) où K est la longueur de la sous-chaîne clé recherchée, et L la longueur où l’on recherche s’il existe au moins une occurrences de la clé, l’algorithme de Boyer-Moore peut trouver les occurrences en un temps :
Le cas moyen pour établir s’il y a correspondance ou non requiert environ (3 · K) comparaisons. La preuve est due à Richard Cole.
Dans le pire cas, les performances de l'algorithme de base (sans la variante avec la seconde table de vérification des occurrences) pour trouver toutes les correspondances est de l'ordre de O(K · L). Le pire cas se produit quand la sous-chaîne consiste en une répétition d’un unique caractère, et que le texte correspond à la répétition de (K - 1) fois ce même caractère, précédé par un seul autre caractère différent. Dans ce cas de figure, l’algorithme doit vérifier (L - K+ 1) décalages différents dans le texte pour chaque correspondance. Or, chacune de ces vérifications nécessite K comparaisons.
En raison de l’intérêt de la variante avec la seconde table qui permet un comportement sous-linéaire même dans le pire cas, cette variante est décrite ici (et est celle aujourd'hui intégrée dans de nombreuses librairies de traitement du texte pour C/C++, Java, etc.).