Algorithme de Boyer-Moore - Définition

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

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