Algorithme de Boyer-Moore

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^[1] 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^[2].

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

Fonctionnement

Beaucoup de personnes sont surprises par l'algorithme de Boyer-Moore lorsqu'elles le découvrent pour la première fois, 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 la quelque peu contre-intuitive affirmation disant que plus la sous-chaîne est longue, et plus l'algorithme est efficace pour la trouver.

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 de force brute, 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, on 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 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 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 9 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 le relire le texte ou la clé depuis le début, et sans avoir à utiliser de couteux tampons mémoire compliqués à gérer. Ce n’est pas toujours le cas de tous les flux de fichiers texte à lecture unidirectionelle.

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)^[3].

Pré-traitement

L'algorithme précalcule deux tableaux pour traiter l'information qu'il obtient pour chaque vérification ayant échoué. La première indique le nombre de positions à sauter avant de reprendre la recherche, en se basant sur l'index du caractère qui a provoqué l'échec de la vérification. La seconde donne une information similaire, basée sur le nombre de caractères vérifiés avec succès avant que la vérification échoue. Comme ces deux tableaux indiquent le nombre de positions qu'il faut sauter dans le texte avant de poursuivre la recherche, ils sont parfois appelés "tables de sauts".

Première table de sauts (non-concordance du dernier caractère de clé)

Le premier tableau contenant le nombre de caractères suivants à ignorer en cas de non-concordance du dernier caractère de la clé est facile à remplir ; il correspond à la distance, mesurée depuis la fin de la clé, de la dernière occurrence dans la sous-chaîne clé de chaque caractère de l’alphabet (alphabet commun à la clé et au texte) :

• préremplir toutes les positions du tableau des caractères avec la longueur de la sous-chaîne clé ;
• démarrer par le dernier caractère de la sous-chaîne clé avec le compteur à 0, et aller en direction du premier caractère :
• pour chaque déplacement vers la gauche, incrémenter le compteur, et si le caractère à la position courante n’est pas déjà dans le tableau, l’ajouter avec la valeur actuelle du compteur.

Exemple : avec la sous-chaîne 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) :

Le lecteur attentif remarquera que le A, le dernier caractère de la sous-chaîne, n’a pas été ajouté dans le tableau.

La raison est que l’algorithme utilise le tableau après avoir trouvé un caractère qui ne correspond pas. Le tableau lui indique le nombre de positions vers l’avant que l'algorithme doit sauter avant que ce caractère puisse théoriquement correspondre dans le texte. Par exemple, si en vérifiant la neuvième position du texte, l’algorithme trouve un I plutôt qu’un A, cela indiquerait que la prochaine correspondance potentielle pourrait être trouvée une position plus loin vers l’avant, et que la dixième position doit être vérifiée pour y chercher un A. S’il s'agit d’un A, soit l’algorithme le trouve dans la dernière position, et dans ce cas, la vérification est un succès, soit la dernière position a déjà été vérifiée ; dans ce second cas, il n'existe aucun endroit dans le reste de la sous-chaîne clé où le A peut correspondre. De ce fait, aucune correspondance n’est possible jusqu'à ce que l’algorithme cherche complètement au-delà de la position du A.

Notes de performance :

1. On doit remarquer que ce tableau a une taille (nombre total d‘entrées) indépendante de la longueur de la clé, mais dépendante de la taille de l’alphabet des caractères possibles.
   • Si l’alphabet est très grand (par exemple le répertoire universel UCS d’Unicode et ISO/IEC 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 clé), et son préremplissage peut prendre du temps.
   • De même les longueurs de saut stockées dans le tableau ne pourront pas être supérieures à la taille A de l‘alphabet avec l’algorithme de remplissage ci-dessus, et il est donc inutile de traiter la totalité de la clé en dehors des A derniers caractères de celle-ci.

     Cette optimisation sera utile si la longueur K de la clé cherchée est suffisamment longue (K ≥ A), tout en étant ne dépassant pas la longueur L du texte à parcourir, K < L.

     En effet, lorsque K ≥ L la réponse est immédiate et ne nécessite pas cet algorithme, puisqu’alors :

     • soit on a K > L, et aucune occurrence de la clé n’existe dans le texte ;
     • sinon on a K = L, et un simple test d’égalité des deux chaînes (lues chacune du début à la fin) détermine si le texte est lui-même la seule occurrence de la clé cherchée.

   • On doit noter cependant que l’algorithme de Boyer-Moore doit son efficacité à sa capacité de sauter des longueurs de texte suffisantes. Quand l’alphabet est bien plus grand que la longueur de clé, l’algorithme restera efficace si on réduit l’alphabet à des classes de caractères (l’algorithme de Boyer-Moore continuera à comparer les caractères, mais il n’est pas nécessaire de sauter le nombre maximum de caractères mais seulement un nombre raisonnable (par rapport à la longueur de clé) quand on peut aussi sauter (au prix de quelques pas supplémentaires si la clé contient des caractères distincts mais appartenant à la même classe).
   • Dans ce cas, le tableau ne sera pas indexé sur tous les caractères possibles mais sur tous les numéros de classes de caractère possibles : une fonction de hachage simple réduisant ce grand alphabet à (par exemple) un ensemble réduit à 256 classes de caractères convenablement distribués (ou 256 classes de poids de collation) sera suffisant et fonctionnera de façon très efficace pour des longueurs de clés pouvant aller jusqu'à plusieurs milliers de caractères (ou éléments de collation), la table permettant alors d’effectuer des sauts de 1 à 256 caractères (ou éléments de collation).
   • Le saut maximum (256) ne sera en fait possible que pour les caractères inexistants dans la clé et correspond dans la table ci-dessus aux index des « Autres caractères ». Comme la table ne contient aucune valeur nulle, ce saut maximum pour les caractères (ou classes de caractères) inexistants dans la clé peut aussi être codé 0 (et il n’est pas nécessaire d’initialiser le tableau à autre chose que 0, si le tableau alloué est déjà prérempli à zéro).
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 brute) avec cette table de sauts, qui ne contiendra qu’une seule ligne « Autres caractères » pour le caractère autre que celui en dernière position de la clé : l’astuce consistera à lire le texte ou la clé non pas caractère par caractère, mais par groupe successifs de caractères afin d’augmenter l’alphabet à un cardinal suffisant : par exemple on pourra lire le texte ou la clé par paquet de 8 caractères, si l’alphabet effectivement utilisé dans la clé et le texte est binaire, 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 en début de clé ou de fichier pour ajuster la position du groupe trouvé.

Seconde table de saut (non-concordance des caractères de la clé autres que le dernier)

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 lequel 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) :

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 lui aussi un temps fini.
• 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).

Voir aussi

Articles connexes

• Algorithme de recherche de sous-chaîne
• 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érence

• Portail de l’algorithmique
• Portail de l’informatique