Recherche textuelle et Boyer-Moore : fiche de Terminale NSI
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
Recherche textuelle : trouver les occurrences d'un motif dans un texte 2.
Méthode naïve : on teste chaque position, en comparant lettre à lettre.
Boyer-Moore : on compare le motif de droite à gauche et on décale selon une table de décalage.
La version simplifiée de Horspool n'utilise qu'une table, calculée une fois sur le motif 1.
Le coût se mesure au nombre de comparaisons de caractères1.
Le problème de la recherche textuelle
Ce problème est l'un des plus anciens de l'algorithmique du texte 2. On le retrouve dans le traitement de la langue, la gestion de bases de textes ou l'analyse de séquences génétiques 2. Pour comparer deux algorithmes, on compte surtout le nombre de comparaisons de caractères1.
La méthode naïve, point de départ
Boyer-Moore et la version de Horspool
L'algorithme de Boyer et Moore date de 1977 ; ses auteurs travaillaient alors à l'université d'Austin, au Texas 1. Au programme, on étudie une version simplifiée, due à Horspool 1.
Exemple complet
Pièges et points de vigilance
Questions flash
5 questions · correction immédiate · ton score reste sur ton appareil.
On part de la dernière lettre du motif : c'est ce qui permet de décaler selon la lettre du texte alignée à cet endroit. Comparer de gauche à droite est le réflexe hérité de la méthode naïve ; dans Boyer-Moore, la convention est de commencer par la fin du motif.
A a pour indice 1 et m=5 : 5−1−1=3. Répondre 4 vient d'un oubli du « −1 » ; répondre 5 revient à traiter A comme une lettre absente du motif.
La dernière lettre est exclue du calcul de la table, donc E reçoit m=5. Un décalage de 0 empêcherait le motif d'avancer.
Vrai : ces comparaisons sont l'opération qui domine le coût 1. Compter seulement les décalages ne suffit pas, car un décalage peut coûter plusieurs comparaisons.
L'algorithme complet utilise une seconde table, beaucoup plus difficile à calculer 1. La version simplifiée garde une seule table, mais compare bien des caractères et fonctionne sur tout texte.
Les questions qu'on se pose
Pourquoi comparer de droite à gauche ?
Parce qu'on teste ainsi en premier la lettre du texte alignée sur la fin du motif, celle qui décide du décalage. Si cette lettre n'est pas dans le motif, on peut le faire avancer d'une longueur entière, sans tester les autres positions.
Boyer-Moore est-il toujours plus rapide que la méthode naïve ?
Il gagne surtout quand le motif est long et que les lettres du texte sont souvent absentes du motif : les décalages sont alors grands. Si les décalages valent souvent 1, le gain est faible. Retiens que le coût se juge au nombre de comparaisons 1.
Que vaut le décalage d'une lettre absente du motif ?
Il vaut la longueur m du motif : le motif saute entièrement au-delà de cette lettre, qui ne peut figurer dans aucune occurrence qui la recouvre.