Introduction
La recherche textuelle est un domaine fondamental en informatique, utilisé dans de nombreuses applications telles que les moteurs de recherche, l’analyse de données textuelles et les traitements linguistiques. Parmi les algorithmes efficaces pour la recherche de motifs dans un texte, l’algorithme de Boyer-Moore se distingue par sa capacité à effectuer des recherches rapides grâce à un processus de prétraitement ingénieux. Cette leçon a pour objectif d’expliquer le principe de cet algorithme et de faire comprendre l’importance du prétraitement dans l’optimisation de la recherche textuelle.
Le principe de l’algorithme de Boyer-Moore
La recherche de motif
L’algorithme de Boyer-Moore a été conçu pour rechercher efficacement un motif (ou pattern) dans un texte. Contrairement à une recherche naïve qui compare caractère par caractère, de gauche à droite, chaque position possible du motif avec le texte, Boyer-Moore procède de manière différente.
Le motif est comparé au texte en partant de la droite vers la gauche, et non de gauche à droite. Lorsqu’une discordance est détectée, l’algorithme utilise des heuristiques fondées sur le prétraitement du motif pour déterminer le décalage optimal du motif sur le texte.
Deux heuristiques principales sont utilisées :
Heuristique du mauvais caractère : Lorsqu’un caractère du motif ne correspond pas à celui du texte, on regarde dans le motif la position la plus à droite de ce caractère fautif. Cela permet de calculer un décalage pour repositionner le motif plus loin dans le texte, en espérant aligner le caractère fautif avec sa dernière apparition dans le motif, ou, s’il n’est pas dans le motif, de le faire avancer complètement.
Heuristique du bon suffixe : Si une partie du motif a été correctement comparée à la fin (à droite), mais que la discordance survient sur un caractère plus à gauche, on cherche à repositionner ce suffixe du motif sur une autre occurrence de ce même suffixe (ou d’un suffixe plus court) dans le motif lui-même. Cela évite de retester des caractères déjà validés.
Décalage effectif : Lorsqu’une discordance est rencontrée, on calcule les deux décalages proposés par les heuristiques du mauvais caractère et du bon suffixe. L’algorithme choisit le plus grand des deux pour effectuer le saut, garantissant un déplacement correct tout en maximisant l’efficacité.
L’algorithme en action
Examinons un exemple concret. Soit le texte : AABACABC et le motif : ABC.
On commence par aligner le motif à l’extrême gauche du texte :
Les comparaisons commencent par le dernier caractère du motif (« C ») et se font de droite à gauche. Si l’on rencontre une discordance (par exemple ici, « C » ≠ « A »), on applique les deux heuristiques :
Mauvais caractère : « A » est présent au début du motif, donc on peut décaler pour aligner cette occurrence.
Bon suffixe : il n’y a pas de suffixe valide alignable, donc on se base uniquement sur l’heuristique du mauvais caractère.
On répète ce processus jusqu’à ce que le motif soit trouvé ou que la fin du texte soit atteinte. Grâce à ses optimisations, Boyer-Moore évite de tester chaque position comme le ferait une recherche naïve.
L’intérêt du prétraitement
Construction des tables de décalage
L’efficacité de l’algorithme de Boyer-Moore repose en grande partie sur un prétraitement minutieux du motif pour construire deux tables de décalage nécessaires aux heuristiques.
Table du mauvais caractère : Pour chaque caractère de l’alphabet, cette table enregistre la dernière position de ce caractère dans le motif (ou une valeur par défaut s’il est absent). Elle permet, en cas d’erreur de correspondance, de calculer un décalage adapté.
Table du bon suffixe : Cette table est plus complexe. Pour chaque suffixe du motif, elle identifie le plus grand décalage qui aligne ce suffixe avec une autre occurrence dans le motif, ou qui permet de l’aligner avec un préfixe. Elle nécessite de parcourir le motif pour identifier les occurrences répétées ou les frontières.
Ces deux tables sont construites une seule fois, lors du prétraitement, ce qui optimise la recherche en évitant des calculs redondants à chaque étape.
Gains en efficacité
Le prétraitement permet à l’algorithme de Boyer-Moore d’atteindre une complexité optimale dans de nombreux cas. Il est particulièrement performant pour les textes longs et les motifs de taille moyenne, surtout lorsque les caractères du motif sont peu fréquents dans le texte.
En effet, dans le meilleur des cas, l’algorithme effectue moins de comparaisons que la longueur du texte, ce qui en fait l’un des algorithmes les plus rapides pour la recherche de motifs.
À retenir
L’algorithme de Boyer-Moore compare le motif au texte de droite à gauche.
Il utilise deux heuristiques basées sur un prétraitement du motif : le mauvais caractère et le bon suffixe.
En cas de discordance, le décalage effectif est le maximum proposé par ces deux heuristiques.
Le prétraitement construit deux tables de décalage essentielles pour optimiser les comparaisons.
Boyer-Moore est très efficace pour la recherche de motifs, surtout dans des textes longs et avec des motifs courts ou peu fréquents.
Conclusion
L’algorithme de Boyer-Moore illustre parfaitement comment un prétraitement rigoureux peut transformer une tâche simple en une recherche hautement optimisée. En exploitant les heuristiques du mauvais caractère et du bon suffixe, et en combinant leurs décalages, l’algorithme réduit considérablement le nombre de comparaisons nécessaires. Il se distingue par un parcours inversé du motif, une stratégie efficace de sauts intelligents et une adaptation fine au contenu du texte. Maîtriser cet algorithme permet de mieux comprendre les défis de la recherche textuelle et de concevoir des solutions performantes et robustes en informatique.