Recherche textuelle et Boyer-Moore : cours de Terminale NSI

Quand tu utilises la fonction « rechercher » d'un traitement de texte ou d'un navigateur, un programme parcourt un long texte pour retrouver une courte suite de caractères. Ce problème fait partie des plus anciens et des plus étudiés de l'algorithmique du texte ². Dans ce chapitre, tu vas voir pourquoi la méthode la plus simple peut être lente, puis comment l'algorithme de Boyer-Moore, dans sa version simplifiée, évite une grande partie du travail.

Tu as déjà rencontré l'idée de gagner du temps en organisant le calcul : le diviser pour régner découpe un problème, la programmation dynamique mémorise des résultats intermédiaires. Ici, l'idée est proche de cette dernière : on prépare une petite table à partir du motif, une fois pour toutes, puis on s'en sert pour avancer plus vite dans le texte.

Notons $n$ la longueur du texte et $m$ celle du motif. Imagine le motif écrit sur une bande de papier que tu poses sous le texte, d'abord tout à gauche. Tu compares les caractères en vis-à-vis. Si tout correspond, tu as trouvé une occurrence. Sinon, tu décales la bande d'un seul cran vers la droite et tu recommences.

Ce principe s'écrit très simplement :

Pour juger un algorithme de recherche, on ne se contente pas de chronométrer un programme : on compte des opérations. Dans ce domaine, le coût se ramène surtout au nombre de comparaisons entre deux caractères ¹. C'est ce compteur que nous utiliserons dans tous les exemples.

L'algorithme date de 1977. Ses deux inventeurs, Boyer et Moore, étaient alors informaticiens à l'université d'Austin, au Texas ¹. Il est très efficace ¹, et il repose sur des idées simples que tu retrouveras dans la version simplifiée.

Première idée : comparer de droite à gauche. On aligne toujours le motif sous le texte, mais on commence la comparaison par le dernier caractère du motif. Si celui-ci ne correspond pas, on sait tout de suite que la position est mauvaise, et surtout on connaît la lettre du texte qui pose problème.

Deuxième idée : décaler de plusieurs crans. Grâce à cette lettre, on calcule de combien on peut avancer le motif sans risquer de manquer une occurrence. Ce décalage est lu dans une table de décalage, construite une seule fois à partir du motif.

Dans la suite, nous gardons les notations suivantes : le texte est la chaîne texte de longueur $n$, le motif est la chaîne motif de longueur $m$, et $i$ désigne la position du début de la fenêtre, c'est-à-dire l'indice du texte placé en face de motif[0]. La fenêtre couvre donc texte[i] jusqu'à texte[i+m-1].

La table répond à la question : « Quand la lettre c se trouve en face du dernier caractère du motif, de combien puis-je avancer sans rater d'occurrence ? »

Soit c la lettre du texte située sous le dernier caractère du motif, que la comparaison ait réussi ou non.

• Si c n'apparaît pas parmi les $m-1$ premiers caractères du motif, aucune fenêtre décalée de moins de $m$ crans ne peut convenir. On avance donc de $m$ crans.
• Si c apparaît parmi ces $m-1$ caractères, on retient sa dernière apparition. On avance juste assez pour amener cette apparition en face de c dans le texte. Choisir la dernière apparition est prudent : on ne dépasse jamais une occurrence possible.

Comme pour les autres algorithmes de recherche, on compte les comparaisons de caractères ¹. Il faut distinguer plusieurs situations.

Le meilleur cas. Si la lettre sous le dernier caractère du motif est toujours absente du motif, chaque fenêtre coûte une seule comparaison et on avance de $m$ crans. Le nombre de comparaisons est alors de l'ordre de $\dfrac{n}{m}$ : plus le motif est long, moins on lit de lettres. L'algorithme regarde alors moins de caractères que le texte n'en contient.

Le pire cas. Il existe des textes pour lesquels la version simplifiée se comporte comme la méthode naïve : par exemple le motif BAAA dans un texte formé de A. La table donne un décalage de $1$ pour la lettre A, et chaque fenêtre coûte $m$ comparaisons, la différence étant tout à gauche. Le nombre de comparaisons peut alors atteindre l'ordre de $n \times m$.

On retrouve une idée générale : une grande efficacité en pratique n'empêche pas l'existence de cas défavorables. La seconde table de l'algorithme complet sert justement à obtenir de meilleurs décalages ¹.

La recherche d'un motif n'est pas réservée aux éditeurs de texte. Ces techniques servent pour la langue naturelle, pour les séquences génétiques en bioinformatique, pour les séquences musicales, pour les flux de données et les bases de données textuelles. On les retrouve aussi dans la détection de plagiats et l'analyse d'image ².

Prenons une séquence d'ADN, qui s'écrit avec seulement quatre lettres. Chercher un court enchaînement de lettres dans un texte très long est exactement notre problème. L'alphabet très petit a une conséquence sur la table : beaucoup de lettres du texte apparaissent dans le motif, donc les décalages sont plus petits que pour un texte en langue naturelle, où l'alphabet est plus grand.