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 MooreLe prénom de « J Strother Moore » est bien la lettre J et non l’abréviation « J. » d’un prénom en 1977.

Efficacité / complexité en temps

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 : 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’accroît). 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 ColeTight bounds on the complexity of the Boyer-Moore algorithm, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, (1991).

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 a suivi d'une occurrence d'un deuxième cactère b distinct de a, et que le texte correspond à la répétition de (K - 1) fois le caractère a. 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 bibliothèques de traitement du texte pour des langages tels que C/C++, Java, JavaScript, Python, etc.).

Fonctionnement Principe L'algorithme de Boyer-Moore est assez surprenant car il effectue la vérification, c'est-à-dire qu'il tente d'établir la correspondance de la sous-chaîne à une certaine position, à l'envers. Par exemple, s'il commence la recherche de la sous-chaîne WIKIPEDIA au début d'un texte, il vérifie d'abord la neuvième position en regardant si elle contient un A. Ensuite, s'il a trouvé un A, il vérifie la huitième position pour regarder si elle contient le dernier I de la sous-chaîne, et ainsi de suite jusqu'à ce qu'il ait vérifié la première position du texte pour y trouver un W.

La raison pour laquelle l'algorithme de Boyer-Moore utilise cette approche à rebours est plus claire si l'on considère ce qui se produit quand la vérification échoue, par exemple si au lieu de trouver un A en neuvième position, un X est lu. Le X n'apparaît nulle part dans la sous-chaîne WIKIPEDIA, ce qui signifie qu'aucune correspondance avec la sous-chaîne n'existe au tout début du texte, ainsi que dans les huit positions qui la suivent. Après la vérification d'un seul caractère, l'algorithme est capable de passer ces huit caractères et de rechercher le début d'une correspondance à partir de la dixième position dans le texte, juste après le X.

Ce principe de fonctionnement à rebours explique l'affirmation contre-intuitive disant que plus la sous-chaîne est longue, et plus l'algorithme est efficace pour la trouver.

Exemple Prenons un exemple plus significatif : on veut rechercher les occurrences de la clé de K=6 caractères “string” dans le texte de L=20 caractères “stupid_spring_string".

Avec un algorithme classique utilisant une méthode naïve, on devrait rechercher le s dans tout le texte sauf les 5 derniers caractères, et donc faire toutes les 15 comparaisons. Et on trouverait 3 occurrences du s au début de chaque mot du texte ; pour chacune de ces occurrences on devrait vérifier la suite de la clé tant qu'elle correspond : on détecterait le p une fois pour rejeter l’occurrence commençant par spring, mais le t serait détecté dans stupid et string ; on doit alors tester la présence du r après st pour éliminer l’occurrence dans stupid ; il reste encore à vérifier chacun des 3 autres caractères de la clé string, il faudra donc 23 comparaisons (ce serait pire si le texte contenait de nombreuses occurrences de la quasi-totalité du début de la clé).

Avec l’algorithme de Boyer-Moore, on recherchera aussi les occurrences depuis le début du texte (en affichant ci-dessous la clé cherchée en dessous du texte balayé, les points notés avant la clé indiquant les positions déjà éliminées, le surlignage indique les comparaisons effectuées), mais on commencera en comparant le dernier caractère de la clé cherchée : stupi_spring_string strin Les deux caractères d et g ne correspondent pas, on a trouvé à la place un d dans le texte, alors qu’il n’y a aucun d dans la clé. On peut sauter directement dans le texte les 6 caractères de la clé : stupid_sprig_string ······strin Le g de la clé ne correspond pas au n du texte. Cependant, la clé contient un n, 1 caractère avant, on peut donc décaler d’1 position, et vérifier à nouveau en commençant par la fin de clé : stupid_s_string ·······s On a trouvé successivement la correspondance du g, puis du n, puis du i, puis du r, mais pas du t de la clé. Au lieu de cela on a trouvé un p dans le texte, qui ne figure pas dans la clé, ce qui permet de décaler de 2 caractères pour placer le début de la clé après le p: stupid_spring_tring ·········strin Le g de la clé ne correspond pas au s du texte. Cependant, la clé contient un s, 5 caractères avant, on peut donc décaler de 5 positions, et vérifier à nouveau en commençant par la fin de clé : stupid_spring_ ·············· On trouve successivement les correspondances du g, puis du n, du i, du r, du t et du s. Il n'y a plus d’autre caractère dans la clé, on a bien trouvé une occurrence en seulement 14 comparaisons (au lieu de 23 avec l’algorithme classique). Si on devait chercher les occurrences suivantes, il suffit de reprendre l’algorithme dans le texte à partir de la position qui suit la position trouvée.

Contraintes d’implémentation Il faut noter que, pour que l’algorithme de Boyer-Moore puisse fonctionner de façon efficace, il est nécessaire de pouvoir parcourir le texte (ainsi que la clé cherchée) en le parcourant linéairement en sens inverse, et de pouvoir sauter directement à une position ultérieure du texte sans avoir à le lire intégralement entre les deux positions, ni à devoir relire le texte ou la clé depuis le début, et sans avoir à utiliser de coûteux tampons mémoire compliqués à gérer. Ce n’est pas toujours le cas de tous les flux de fichiers texte à lecture unidirectionnelle.

Et dans le cas où la recherche doit utiliser des comparaisons basées sur la collation de chaînes conformes à des règles linguistiques dans lesquelles certaines différences sont ignorées dans la recherche des correspondances, les éléments à comparer ne seront pas les caractères eux-mêmes mais les éléments de collation précalculés sur la clé et ceux obtenus au fil de l’eau dans le texte, dans lequel il doit être nécessaire de déterminer si les positions sont celles marquant la séparation des éléments de collation (afin de ne pas trouver de faux positifs ni oublier des correspondances lorsqu’on saute directement certaines positions ou quand on lit le texte ou la clé en sens inverse) : cela pose certaines difficultés dans les collations linguistiques comprenant des contractions et expansions, ou encore dans des textes Unicode non normalisés pour lesquels plusieurs codages sont possibles. Mais des algorithmes complémentaires ont été développés pour traiter efficacement cette difficulté (et quelques autres liées à l’étendue du jeu de caractères Unicode (ou l’étendue numérique encore plus grande des poids de collation multiniveau) Efficient text searching in Java, par Laura Werner, paru dans Java Report en 1999 (document présenté dans le projet ICU)..

Pré-traitement À partir de la clé, l'algorithme précalcule deux tableaux indiquant un nombre de positions à sauter après chaque vérification dans le texte. Ces tableaux (parfois appelés « tables de sauts ») exploitent l’information tirée de la vérification effectuée. Le premier se base sur le caractère du texte qui a été comparé au dernier caractère de la clé (c’est la première comparaison effectuée puisque les vérifications se font de droite à gauche). Le second se base sur le nombre de caractères vérifiés avec succès (ce nombre peut égaler la taille de la clé, auquel cas la vérification a réussi).

Première table de sauts (indicée par les lettres de l’alphabet) Le premier tableau utilise le constat suivant : si on cherche par exemple la clé WIKIPEDIA dans le texte ENCYCLOPEDIA, alors la première vérification sera :

ENCYCLOPDIA WIKIPEDI

Sachant que la première lettre du texte qu’on a comparée est un E, il est inutile de vérifier les appariements suivants :

ENCYCLOPEDIA ·WIKIPEDIA

ENCYCLOPEDIA ··WIKIPEDIA

On peut sauter directement à celui-ci :

ENCYCL ···WIK

Ici, on a donc avancé de trois positions au lieu d’une seule, c’est-à-dire la distance entre la dernière lettre E dans la clé et la fin de la clé. Si cette lettre n’apparaissait pas dans la clé, alors on aurait pu sauter toute la longueur de celle-ci.

La première table de sauts est donc facile à calculer : elle associe à chaque caractère de l’alphabet la distance, mesurée depuis la fin de la clé, de la dernière occurrence de cette lettre dans la clé. La dernière position de la clé n’est pas comptée dans les occurrences ; autrement, la distance associée à la dernière lettre de la clé (la lettre A dans l’exemple) serait nulle et on resterait sur place après l’avoir lue dans le texte. Les lettres n’apparaissant pas dans la clé sont associées à la longueur de la clé. Un algorithme de calcul est donc : pré-remplir toutes les valeurs du tableau avec la longueur de la clé ;