Algorithme de Boyer-Moore

En informatique, plus précisément en algorithmique, l'algorithme de Boyer-Moore est un algorithme de recherche de sous-chaîne particulièrement efficace, qui est utilisé comme référence avec lequel on compare d'autres algorithmes quand on réalise des expériences de recherche de sous-chaîne. Il a été développé par Robert S. Boyer et J Strother Moore en 1977. L'algorithme de Boyer-Moore pré-traite la sous-chaîne « clé » ( la chaîne recherchée) et non le texte ( la chaîne dans laquelle la recherche est effectuée). Son fonctionnement est à l'inverse 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 sous-linéaire : il n'a pas besoin de vérifier chacun des caractères du texte. Au contraire, il peut sauter certains d'entre eux. En général, l'algorithme devient plus rapide lorsque la longueur de la sous-chaîne s'allonge. Cette efficacité provient du fait que, pour chaque tentative infructueuse de correspondance 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 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é en temps (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 de la séquence où l’on recherche s’il existe au moins une occurrence 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.