Algorithme de Boyer-Moore - Définition

Introduction

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.

Efficacité / complexité en temps

L'algorithme de Boyer-Moore pré-traite la sous-chaîne (c'est-à-dire la chaîne recherchée), et non pas le texte (c'est-à-dire la chaîne dans laquelle la recherche est effectuée), à 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 sub-linéaire, c'est-à-dire qu'il n'a pas besoin 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 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 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 :

• De l’ordre de O(L / K) dans le cas le plus favorable : dans ce meilleur cas, seul un caractère sur M doit être vérifié. Ainsi, plus la sous-chaîne est longue, et plus l’algorithme est efficace pour la trouver ;
• de l’ordre de O(L + K) dans le pire cas (en utilisant la variante améliorée de l’algorithme avec la seconde table de vérification des occurrences).
• et très souvent en un temps à peine supérieur au meilleur cas (qui devient de plus en plus probable quand la longueur K de la clé s’accroit). Le pire cas est obtenu quand le texte contient de très nombreuses occurrences d’un même caractère, et quand la clé cherchée contient ce caractère fréquent de nombreuses fois en fin de chaine sauf pour le premier caractère qui est différent.

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.).