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[1]. Il a été développé par Robert S. Boyer et J Strother Moore[2] en 1977.

Efficacité / complexité en temps

L'algorithme de Boyer-Moore pré-traite la sous-chaîne « clé » (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 sous-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 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 Cole[3].

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é 2 fois 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 :

stupid_spring_string

string

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_spring_string

······string

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_spring_string

·······string

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_string

·········string

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_string

··············string

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 (en) 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)[4].

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 :

ENCYCLOPEDIA

WIKIPEDIA

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 :

ENCYCLOPEDIA

···WIKIPEDIA

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é ;
• démarrer de l’avant-dernière position dans la clé avec le compteur à 1, et aller vers le début en incrémentant le compteur ;
• pour chaque position, si le caractère courant n’est pas déjà dans le tableau, l’ajouter avec la valeur actuelle du compteur.

Exemple : avec la clé WIKIPEDIA, le premier tableau est rempli comme suit (pour plus de clarté, les entrées sont données dans l'ordre où elles sont ajoutées dans le tableau) :

Caractère de l’alphabet	Distance à la fin de clé
I	1
D	2
E	3
P	4
K	6
W	8
autres caractères	9

Le lecteur attentif remarquera que le A, le dernier caractère de la clé, n’a pas été ajouté dans le tableau. En effet, il ne présente pas d’autre occurrence dans la clé.

Notes de performance :

1. Ce tableau a une taille (nombre total d‘entrées) indépendante de la longueur de la clé, mais proportionnelle à la taille de l’alphabet.
   • Si l’alphabet est très grand (par exemple le répertoire universel UCS d’Unicode et ISO/CEI 10646 dont l’alphabet comprend plus d’un million de points de code possibles) sa taille pourrait devenir prohibitive, alors que la plus grande partie de ce tableau contiendrait la valeur par défaut (la longueur de la clé), et son pré-remplissage peut prendre du temps. Cela peut s’optimiser en remarquant que la table ne contient pas de valeur nulle. la valeur par défaut pourra donc être codée par 0 sans ambiguïté. Cette astuce permet d’économiser l’initialisation du tableau dans un environnement qui pré-remplit les tableaux à zéro.
   • De plus, l’algorithme de Boyer-Moore doit son efficacité à sa capacité de sauter des longueurs de texte suffisantes. Il n’est pas nécessaire de sauter la distance maximale, une distance raisonnablement grande (par rapport à la longueur de la clé) suffit. Quand l’alphabet est bien plus grand que la clé, l’algorithme restera efficace si on réduit l’alphabet à des classes de caractères (ou d’éléments de collation) avec une bonne répartition.
   • Dans ce cas, le tableau ne sera pas indicé par les caractères mais par les classes de caractères : une fonction de hachage simple réduisant ce grand alphabet à (par exemple) un ensemble réduit à 256 classes convenablement distribuées suffira et fonctionnera très efficacement pour des longueurs de clé pouvant aller jusqu'à plusieurs milliers de caractères, la table permettant alors d’effectuer des sauts de 1 à 256 caractères.
2. En revanche, si l’alphabet est extrêmement réduit (par exemple, un alphabet binaire), l’efficacité de l’algorithme sera totalement nulle (par rapport à un algorithme de recherche naïf) avec cette table de sauts. L’astuce consistera à lire le texte et la clé non pas caractère par caractère, mais par groupes de caractères afin d’augmenter l’alphabet à un cardinal suffisant. Par exemple, avec un alphabet binaire, on pourra lire par paquets de 8 caractères, en fixant un caractère de bourrage arbitraire (ou moins probable) pour les caractères (du petit alphabet) qui manquent au début de la clé ou au début du texte mais qui sont nécessaires à la formation de groupes complets de lettres convertis en lettres équivalentes du nouvel alphabet augmenté. On tiendra ensuite compte, lorsque des correspondances sont trouvées entre des groupes de caractères, du nombre de caractères de bourrage utilisés pour ajuster la position du groupe trouvé.

Seconde table de saut (indicée par la longueur de la clé comparée avec succès)

Le second tableau est sensiblement plus compliqué à calculer : pour chaque valeur de N inférieure à la longueur K de la sous-chaîne clé, il faut calculer le motif composé des N derniers caractères de la sous-chaîne K, précédé d'un caractère qui ne correspond pas. Puis, il faut trouver le plus petit nombre de caractères pour lesquels le motif partiel peut être décalé vers la gauche avant que les deux motifs ne correspondent. Par exemple, pour la sous-chaîne clé ANPANMAN longue de 8 caractères, le tableau de 8 lignes est rempli de cette manière (les motifs déjà trouvés dans le texte sont montrés alignés dans des colonnes correspondant à l’éventuel motif suivant possible, pour montrer comment s’obtient la valeur de décalage qui est la seule réellement calculée et stockée dans la seconde table de saut) :

Indice							Motif suivant								Décalage obtenu
							A	N	P	A	N	M	A	N
0													N		1
1					A	N									8
2									M	A	N				3
3					N	M	A	N							6
4				A	N	M	A	N							6
5			P	A	N	M	A	N							6
6		N	P	A	N	M	A	N							6
7	A	N	P	A	N	M	A	N							6

Notes relatives à la complexité de calcul cette table :

• On remarque que cette table contient autant de lignes que la longueur de clé. Si la clé est longue, les valeurs de décalage dans la table peuvent être elles aussi assez importantes, ce qui va nécessiter une allocation de mémoire de travail peut-être importante, souvent plus grande en taille elle-même que la chaîne clé qui utilise un alphabet plus réduit (par exemple 1 octet par caractère) que les entiers alors qu’en fin de compte les longueurs de clé seront importantes (typiquement des entiers codés sur 4 octets).
• La constitution de cette table nécessite là aussi de rechercher des sous-chaînes (toutes les sous-chaînes possibles de la fin de clé) pour en trouver pour chacune la dernière occurrence dans la clé, et l’algorithme de Boyer-Moore pourrait être utilisé récursivement (mais en utilisant une recherche sur des textes et clés de direction inversée).
• Au-delà d’une certaine longueur raisonnable (par exemple jusqu’aux 256 derniers caractères de la clé), il peut être inutile d’augmenter la taille de cette table puisque le seul but sera de savoir si des décalages plus grands peuvent être obtenus pour sauter plus vite dans le texte principal. En ne pré-traitant que les 256 derniers caractères en fin de clé, on obtiendra une longueur déjà suffisante pour accélérer la majorité des recherches (mais si on veut aller au-delà, on pourra, lorsque cette table contient déjà la longueur maximale retenue pour le saut et dans les rares cas où cette longueur serait atteinte, et si l’alphabet est assez discriminant, ce que peut indiquer le taux de remplissage de la première table, employer l’algorithme pour rechercher par récursion (plutôt que par pré-calcul dans cette table) les sous-chaînes dans la clé.
• Mais le plus simple est de borner les décalages à une valeur raisonnable comme 256 et ne pas chercher à aller au-delà. Dans ce cas, cette table aura une taille prédéfinie et ne coûtera rien en termes de complexité pour les clés très longues, puisque son remplissage prendra un temps constant.
• Différentes stratégies sont possibles selon un compromis espace/temps (des stratégies dites « avec cache », ne font aucun pré-calcul des tables, même si elles en utilisent, mais remplissent cette table à la demande en fonction des longueurs de concordances effectivement trouvées à rebours lors de la vérification des occurrences finales déjà trouvées par la première table ci-dessus).

Variantes

On donne ici le pseudo-code donné dans[5] qui est un autre algorithme que les auteurs appellent aussi algorithme de Boyer-Moore :

entrée : le motif m
sortie : une table T tel que T[j][c] soit le plus grand k avec m[k] = c et k < j
construireTable(m)
      T[0..|m|-1] := table où chaque case est vide
      pour j = 0 à |m| - 1
           T[j] := table où on a une case contenant -1 pour chaque caractère
           pour k = 0 à j-1
                 T[j][m[k]] = k
      renvoyer T

entrée : un motif m, un texte
sortie : le nombre d'occurrences du motif m dans le texte
BoyerMoore(m, texte)
     T = construireTable(m)
     compteur = 0
     i = 0
     tant que i ≤ |texte| - |m|
           k = 0
           pour j = |m| - 1 à 0 en décrémentant de 1 à chaque pas
                  si texte[i+j] != m[j]
                        k = j - T[j][texte[i+j]]
                        sortir de la boucle pour j

           si k = 0
                 occurrence trouvée à la position i
                 compteur = compteur + 1
                 k = 1
           i = i + k
     renvoyer compteur

La fonction construireTable(m) réalise le prétraitement. Elle calcule une table T avec pour tout position j dans le motif m et pour tout caractère c, T[j][c] est la plus grande position k dans le motif m avec m[k] = c et k < j. Une fois cette table T construite, l'algorithme de BoyerMoore compte le nombre d'occurrences de m dans le texte. La boucle tant que i parcourt toutes les positions i dans le texte. On parcourt les caractères du motif en partant de la droite. En cas de différence ( texte[i+j] != m[j] ), on retient le décalage trouvé dans k et on sort de la boucle (ce décalage vaut au moins 1). Une fois sorti de cette boucle pour interne, on fait face à une occurrence si et seulement si k = 0. Si tel est le cas, on augmente le compteur et on met k à 1. Puis on incrémente i de k.

Voir aussi

Articles connexes

• Algorithme de recherche de sous-chaîne
• Algorithme de Boyer-Moore-Horspool
• Algorithme de Knuth-Morris-Pratt
• Algorithme de Rabin-Karp

Liens externes

• (en) Analyse, bibliographie et animation de l'algorithme de Boyer-Moore ;
• (en) Un exemple de l'algorithme de Boyer-Moore sur la page Internet de J Strother Moore, co-inventeur de l'algorithme.

Références

1. Andrew Hume et Daniel Sunday, « Fast String Searching », Software: Practice and Experience, vol. 21, n^o 11,‎ novembre 1991, p. 1221–1248 (DOI 10.1002/spe.4380211105, S2CID 5902579)
2. Le prénom de « J Strother Moore » est bien la lettre J et non l’abréviation « J. » d’un prénom
3. Tight bounds on the complexity of the Boyer-Moore algorithm, Proceedings of the 2^d Annual ACM-SIAM Symposium on Discrete Algorithms, (1991)
4. (en) Efficient text searching in Java, par Laura Werner, paru dans Java Report en 1999 (document présenté dans le projet ICU).
5. Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre, Kim Nguyen, Laurent Sartre, Informatique MP2I/MPI: CPGE 1re et 2e années Cours et exercices corrigés, Ellipse, Chapitre 9, Section 9.5.1.1 p. 535-539