NSI Terminale • Programme français, lycées de Montréal
Fiche de révision : recherche textuelle, Boyer-Moore et Horspool
La recherche textuelle est le chapitre où tout tient en cinq lignes de Python et où presque chaque copie perd des points sur l'une d'elles. Le principe de Boyer-Moore se retient vite : comparer de droite à gauche, sauter grâce à une table. Ce qui se perd, c'est le détail : quelle lettre sert de clé, quelle apparition garder, pourquoi la dernière case est exclue.
Cette fiche liste les huit erreurs qui reviennent dans les copies, avec la phrase exacte à écrire à la place et ce que chacune coûte. Le programme ne demande pas l'étude générale du coût de Boyer-Moore : il demande de construire la table, de dérouler une trace et de compter des comparaisons sur un exemple.
Marque ici la fiche comme lue ou mets-la en favori : un compte gratuit, sans mot de passe, retient tes fiches lues et tes favoris d'une visite à l'autre et te dit quel chapitre attaquer ensuite. Crée ton espace, un courriel suffit.
Le fil du chapitre
La table se construit avec le MOTIF seul, une fois, avant de lire le texte ; elle se consulte avec une lettre du TEXTE, celle qui est alignée avec la fin du motif.
•La FENÊTRE en i est la portion texte[i] à texte[i + m - 1], comparée au motif de longueur m. Un texte de longueur n en compte n−m+1.
•Recherche naïve : dans chaque fenêtre, on compare de gauche à droite jusqu'au premier échec, puis on glisse de 1. Au plus m(n−m+1) comparaisons.
•Horspool : dans chaque fenêtre, on compare de DROITE à GAUCHE ; puis on glisse de d.get(c, m), où c = texte[i + m - 1] est la lettre du TEXTE sous la dernière case du motif.
•Règle du mauvais caractère (Boyer-Moore d'origine) : on lit la lettre c de l'ÉCHEC, en position k du motif, et l'on glisse de max(1, k - pos.get(c, -1)).
Horspool lit la lettre sous la FIN du motif, e en bleu, absente de la table de prune : saut de 5. Le mauvais caractère lit la lettre de l'échec, b en rouge, en k=0 : saut de 1.
Le motif avance toujours de gauche à droite dans le texte. Seule la comparaison à l'intérieur d'une fenêtre va de droite à gauche.
La table de Horspool, en quatre règles
•Pour k de 0 à m−2 : d[motif[k]] = m - 1 - k, la distance de la lettre à la fin du motif.
•Une lettre répétée garde sa DERNIÈRE apparition (hors dernière case) : la boucle va de gauche à droite et chaque écriture écrase la précédente.
•La dernière case est EXCLUE : range(m - 1). Aucune valeur de la table n'est donc nulle.
•Une lettre qui n'est pas une clé, absente du motif ou présente seulement en dernière case, donne m : d.get(c, m).
La table ne dépend que du motif. On la calcule une fois, avant la boucle de recherche : c'est le prétraitement dont le programme demande de montrer l'intérêt.
Ce que le programme demande, et ce qu'il ne demande pas
•Demandé : construire la table à la main et en Python, compléter le code, dérouler une trace, compter les comparaisons sur un exemple et les comparer à la recherche naïve.
•Demandé : expliquer l'intérêt du prétraitement du motif.
•Non exigible : l'étude générale du coût de Boyer-Moore, que le programme déclare difficile.
•Non demandé : la règle du bon suffixe, seconde règle de Boyer-Moore complet.
Les règles de calcul en tableau
Chaque ligne se lit de gauche à droite : les hypothèses, puis le résultat. Une case rouge n'est pas une réponse, c'est le constat que la forme ne décide rien et l'ordre de transformer l'écriture. Chaque cas est suivi d'un exemple chiffré.
Le décalage selon la lettre lue, motif ananas
Le motif ananas a m=6 lettres ; la table ne regarde que les cinq premières, a, n, a, n, a. Chaque ligne donne une lettre lue en fin de fenêtre et le saut qu'elle commande.
Lettre lue
Dans ananas
Décalage
a
indices 0, 2, 4
1
Exemple : Dernière apparition hors fin en 4 : 6−1−4=1.
n
indices 1, 3
2
Exemple : Dernière apparition en 3 : 6−1−3=2.
s
dernière case seulement
6
Exemple : s n'est pas une clé : d.get('s', 6) vaut 6.
x
absente
6
Exemple : Le motif passe entièrement au-delà : saut de 6.
a
première apparition
5règle inexistante
Exemple : 6−1−0=5 fait manquer l'occurrence de un ananas, en position 3.
Ce qu'il faut faire : Garder la DERNIÈRE apparition : parcourir le motif de gauche à droite et laisser écraser.
s
compté en fin
0règle inexistante
Exemple : Avec un décalage 0, i n'avance plus : la boucle tourne sans fin.
Ce qu'il faut faire : Exclure la dernière case : for k in range(m - 1).
Toute valeur de la table est comprise entre 1 et m. Une case hors de cet intervalle signale une table fausse avant même de dérouler la trace.
Les pièges qui coûtent des points
Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.
1.Lire le décalage sur la lettre du motif au lieu de celle du texte
toute la trace, souvent 2 à 3 points
Ce qu'il ne faut pas écrire
« La fenêtre échoue sur la dernière lettre du motif, e, donc je décale de d['e']. »
Ce qu'il faut écrire
« La lettre lue est c = texte[i + m - 1], celle du TEXTE sous la dernière case du motif ; j'avance de d.get(c, m). »
Pourquoi : La lettre du motif en dernière case est toujours la même : lire le décalage dessus donne un saut constant, et la trace entière devient fausse dès la deuxième fenêtre.
2.Garder la première apparition d'une lettre répétée
1 point sur la table, et des occurrences manquées dans la trace
Ce qu'il ne faut pas écrire
« Dans ananas, a apparaît d'abord en 0, donc d['a'] = 5. »
Ce qu'il faut écrire
« La boucle écrase les valeurs de gauche à droite : a garde sa dernière apparition hors fin, en 4, donc d['a'] = 1. »
En i=0 la lettre lue est un a, en bleu. La dernière apparition donne un saut de 1, puis 2, et le motif atteint l'occurrence en 3 ; la première apparition sauterait de 5, trop loin.
Pourquoi : Le décalage doit être le plus PETIT saut qui amène une copie de la lettre lue sous elle. Dans un ananas, la valeur 5 fait sauter de i=0 à i=5>n−m=3 : l'occurrence en 3 est perdue.
3.Donner 0 à la dernière lettre du motif
1 point, et un programme qui boucle sans fin
Ce qu'il ne faut pas écrire
« s est à distance 0 de la fin, donc d['s'] = 0. »
Ce qu'il faut écrire
« La dernière case est exclue : for k in range(m - 1). s n'apparaissant nulle part ailleurs, d.get('s', 6) vaut 6. »
Pourquoi : Un décalage nul laisse i immobile : la boucle while réexamine la même fenêtre pour toujours. La terminaison de l'algorithme repose sur le fait que tout décalage vaut au moins 1.
4.Mélanger la table de Horspool et la lettre de l'échec
la trace entière, et une occurrence manquée
Ce qu'il ne faut pas écrire
« En i=0, l'échec a lieu sur le l de il ple, et d['l'] = 4 : j'avance de 4. »
Ce qu'il faut écrire
« Avec la table de Horspool, la clé est TOUJOURS texte[i + m - 1], ici le e : d['e'] = 3, j'avance de 3. »
Pourquoi : La table de Horspool mesure une distance à la FIN du motif ; appliquée à une lettre lue plus à gauche, elle ne veut plus rien dire. Sur il pleut, il pleure, il pleurniche, ce mélange saute par-dessus l'occurrence en 13 et ne trouve rien.
5.Oublier le max(1, ...) de la règle du mauvais caractère
1 point, et une trace qui revient en arrière
Ce qu'il ne faut pas écrire
« Échec en k=2 sur un r, dont la position dans pleure est 4 : je recule de 2. »
Ce qu'il faut écrire
« k− pos['r'] =2−4=−2 : la dernière apparition est à droite de l'échec, j'avance de max(1, -2) = 1. »
Pourquoi : Reculer ferait réexaminer des fenêtres déjà vues, et un décalage nul bloquerait la boucle. La règle du mauvais caractère avance donc d'au moins une case quand elle n'a rien de mieux.
6.Croire que Boyer-Moore lit le texte à l'envers
toute la question de trace
Ce qu'il ne faut pas écrire
« Boyer-Moore commence par la fin du texte et remonte vers le début. »
Ce qu'il faut écrire
« Le motif glisse de gauche à droite le long du texte, i croissant ; seule la comparaison DANS une fenêtre va de droite à gauche. »
Pourquoi : Une trace qui part de la fin du texte donne des positions dans le mauvais ordre et des sauts qui ne correspondent à aucune table : rien n'est récupérable.
7.Affirmer que Horspool est toujours plus rapide
1 point de justification
Ce qu'il ne faut pas écrire
« Boyer-Moore fait toujours moins de comparaisons que la recherche naïve. »
Ce qu'il faut écrire
« Sur un texte de 60 lettres a, le motif baaa coûte 228 comparaisons à Horspool et 57 à la recherche naïve : le gain dépend du texte et du motif. »
Pourquoi : De droite à gauche, les trois a coïncident avant que le b échoue, et la lettre lue, un a, ne fait sauter que de 1. La recherche naïve, elle, bute sur le b dès la première case.
8.Consulter la table sans valeur par défaut
le programme plante : KeyError
Ce qu'il ne faut pas écrire
« i = i + d[texte[i + m - 1]] »
Ce qu'il faut écrire
« i = i + d.get(texte[i + m - 1], m) »
Pourquoi : À la fin de chaque occurrence, la lettre lue est la dernière lettre du motif, qui n'est pas une clé sauf si elle apparaît plus tôt : sans get, la fonction plante dès la première occurrence.
Quelle méthode choisir
Quel décalage appliquer ?
Regarder quelle règle l'énoncé impose, puis quelle lettre du texte elle fait lire.
Si l'énoncé parle de Horspool, ou de la table des décalages → lire c = texte[i + m - 1] et avancer de d.get(c, m), après un échec comme après une occurrence
Exemple : motif pleure, lettre lue une virgule : saut de 6
Si l'énoncé parle de la règle du mauvais caractère, échec en k sur la lettre c → avancer de max(1, k - pos.get(c, -1)), pos donnant la dernière position dans le motif ENTIER
Exemple : pleure, échec en k=4 sur un l : 4−1=3
Si la lettre lue n'est pas une clé → Horspool : m ; mauvais caractère : k+1, le motif passe au-delà de la lettre
Exemple : motif de 6 lettres, lettre lue x : saut de 6
Si la dernière apparition de la lettre est à droite de l'échec → mauvais caractère seulement : le calcul donne un nombre négatif ou nul, on avance de 1
Exemple : pleure, échec en k=2 sur un r : max(1,−2)=1
Aucune branche ne donne un décalage nul ou négatif, et aucune ne donne plus que m pour Horspool. Un saut hors de ces bornes signale une erreur de lecture de la table.
La rédaction attendue
Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.
Dérouler une trace de Horspool
Quand l'utiliser : L'énoncé donne un texte et un motif, et demande les positions trouvées ou le nombre de comparaisons.
1Écrire la table AVANT de lire le texte, avec la valeur par défaut m pour les autres lettres.
2Dresser un tableau à cinq colonnes : i, contenu de la fenêtre, lettre lue texte[i + m - 1], comparaisons, décalage.
3Dans chaque fenêtre, comparer de droite à gauche et compter jusqu'au premier échec INCLUS ; écrire « occurrence » si les m cases coïncident.
4Calculer le i suivant, et écrire le test d'arrêt quand i dépasse n - m.
5Conclure par les positions trouvées et le total des comparaisons, comparé à la recherche naïve si on le demande.
Phrase de conclusion
« Les fenêtres examinées sont i=0,3,9,13,16,22,24 ; puis i=30>28 arrête la boucle. Le motif est trouvé en position 13, pour 13 comparaisons, contre 43 pour la recherche naïve. »
Le piège : Oublier de compter la comparaison qui échoue : elle a bien été faite, c'est elle qui arrête la fenêtre.
Barème : 1 point pour la table, 2 points pour le tableau de trace, 1 point pour les positions et le total.
Compléter un code à trous
Quand l'utiliser : Le sujet donne cherche_horspool ou table_decalages avec des pointillés.
1Repérer le sens de comparaison : k commence à m - 1 et descend.
2Écrire la condition de boucle avec le garde-fou EN PREMIER : k >= 0 and texte[i + k] == motif[k].
3Reconnaître l'occurrence au test k == -1, jamais k == 0.
4Écrire le saut avec la lettre du texte et une valeur par défaut : d.get(texte[i + m - 1], m).
5Dans le prétraitement, écrire range(m - 1), pour exclure la dernière case.
Phrase de conclusion
« k part de m - 1 car on compare de droite à gauche ; la boucle continue tant que k >= 0 et que les caractères coïncident ; une occurrence est reconnue quand k vaut -1 ; on avance de d.get(texte[i + m - 1], m). »
Le piège : Écrire k > 0 : motif[0] n'est jamais comparé, k ne vaut jamais -1, et la fonction renvoie toujours une liste vide.
Vérifier avant de rendre
Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.
Les sauts se relisent sur la table
Deux positions consécutives de la trace diffèrent exactement du décalage de la lettre lue. On relit chaque écart contre la table, sans refaire la trace.
Une trace qui passe de 9 à 12 alors que la lettre lue est un l, de décalage 4, est fausse : il fallait 13.
Encadrer le nombre de comparaisons
Chaque fenêtre coûte au moins 1 comparaison et au plus m : le total est entre le nombre de fenêtres et m fois ce nombre, et chaque occurrence en coûte exactement m.
7 fenêtres et un motif de 6 lettres : un total de 5 ou de 45 est impossible.
Chaque décalage est entre 1 et m
Parcourir la table une fois : une valeur nulle, négative ou supérieure à m trahit une erreur de construction.
Une table de ananas qui contient s : 0 ou a : 5 est fausse avant même de commencer.
Recouper chaque occurrence
Pour chaque position p trouvée, vérifier que texte[p : p + m] est bien le motif, et qu'aucune occurrence évidente du texte n'a été sautée.
Dans il pleut, il pleure, il pleurniche, pleure commence bien en 13, et nulle part ailleurs.
L'exercice type décortiqué
Une trace de Horspool complète
On cherche le motif pleure (m=6) dans le texte il pleut, il pleure, il pleurniche, de 34 caractères espaces et virgules compris, avec l'algorithme de Horspool.
Construire la table, dérouler la trace, donner la position trouvée et le nombre de comparaisons, puis comparer avec la recherche naïve.
Première fenêtre : la lettre lue, en bleu, est un e, qui coïncide avec la fin du motif ; l'échec vient une case plus à gauche, et le saut se lit quand même sur ce e.
python
def table_decalages(motif):
m = len(motif)
d = {}
for k in range(m - 1):
d[motif[k]] = m - 1 - k
return d
Étape 1
Table sur p, l, e, u, r : p 5, l 4, e 3, u 2, r 1 ; toute autre lettre 6. Le e final est exclu, mais le e d'indice 2 donne à e la valeur 6−1−2=3.
Pourquoi
La table se fait avant de lire le texte et ne dépend que du motif. Le cas du e est celui que les copies ratent : exclure la dernière case n'interdit pas à sa lettre d'avoir une clé.
Étape 2
i=0 : fenêtre il ple, lettre lue texte[5] = e, qui coïncide ; puis l contre r échoue. 2 comparaisons, saut d['e'] = 3.
Pourquoi
Le saut se lit sur la lettre du texte en fin de fenêtre, même quand elle a coïncidé et que l'échec est ailleurs. C'est le geste qui fait la différence avec la règle du mauvais caractère.
Étape 3
i=3 : lettre lue une virgule, 1 comparaison, saut 6. i=9 : lettre lue l, 1 comparaison, saut 4, qui place le l du motif sous ce l.
Pourquoi
Une lettre absente du motif fait sauter le motif entier : c'est là que Horspool gagne. Une lettre présente fait sauter juste assez pour l'aligner avec sa copie la plus à droite.
Étape 4
i=13 : pleure, six égalités, 6 comparaisons, occurrence en 13 ; lettre lue e, saut 3. i=16 : lettre lue i, saut 6. i=22 : lettre lue u, saut 2.
Pourquoi
Après une occurrence, on continue exactement comme après un échec : la fonction doit renvoyer toutes les positions, et deux occurrences pourraient se chevaucher.
Étape 5
i=24 : fenêtre pleurn, lettre lue n contre e, 1 comparaison, saut 6 ; i=30>34−6=28 : arrêt.
Pourquoi
Écrire le test d'arrêt montre au correcteur que la borne est connue. La fenêtre pleurn, presque le mot, ne coûte qu'une comparaison parce qu'on lit sa fin en premier.
Étape 6
Total : 2+1+1+6+1+1+1=13 comparaisons sur 7 fenêtres. La recherche naïve examine 29 fenêtres pour 43 comparaisons.
Pourquoi
Vérification : chaque écart entre deux positions de la trace est bien le décalage de la lettre lue, et le total est compris entre 7 et 42. La comparaison avec la méthode naïve est la conclusion que les sujets attendent.
Conclusion rédigée
« Avec la table p 5, l 4, e 3, u 2, r 1 et 6 par défaut, l'algorithme de Horspool examine les fenêtres 0,3,9,13,16,22,24, trouve le motif en position 13 et fait 13 comparaisons, contre 43 pour la recherche naïve. »
L'erreur classique sur cet exercice : Donner 6 à e parce que c'est la dernière lettre : la fenêtre i=0 saute alors à 6, puis 10, puis 16, et l'occurrence en 13 est perdue. La recherche renvoie une liste vide, sans aucun message d'erreur.
À savoir par cœur
•Prétraitement : pour k de 0 à m−2, d[motif[k]] = m - 1 - k ; la DERNIÈRE apparition gagne.
•La dernière case est exclue ; une lettre qui n'est pas une clé donne m : d.get(c, m).
•Horspool lit c = texte[i + m - 1], la lettre du TEXTE sous la fin du motif, après un échec comme après une occurrence.
•Mauvais caractère : échec en k sur c, décalage max(1, k - pos.get(c, -1)).
•Recherche naïve : n−m+1 fenêtres, au plus m(n−m+1) comparaisons.
•Tout décalage vaut au moins 1 : la boucle termine. Le décalage de la table est le plus grand saut sûr.
Questions fréquentes
Quelle est la différence entre Boyer-Moore et Horspool ?
Les deux comparent le motif au texte de droite à gauche et sautent grâce à une table calculée à l'avance. Horspool lit toujours la lettre du texte alignée avec la fin du motif et consulte une seule table. Boyer-Moore d'origine lit la lettre où la comparaison a échoué et combine deux règles, le mauvais caractère et le bon suffixe. Horspool est la version simplifiée qu'on programme en Terminale.
Comment calculer la table des décalages de Boyer-Moore Horspool ?
Pour chaque lettre du motif sauf la dernière, on écrit la distance entre sa dernière apparition et la fin du motif, c'est-à-dire la longueur moins un moins son indice. Une lettre répétée garde sa valeur la plus petite. Toute lettre qui n'est pas dans la table, absente du motif ou présente seulement en dernière position, donne un décalage égal à la longueur du motif.
Pourquoi Boyer-Moore compare-t-il le motif de droite à gauche ?
Parce que la lettre du texte lue en fin de fenêtre suffit souvent à décider d'un grand saut. Si elle n'apparaît pas dans le motif, aucune position qui la recouvre ne peut être une occurrence, et l'on déplace le motif de toute sa longueur. Le motif, lui, avance toujours de gauche à droite dans le texte.
L'algorithme de Boyer-Moore est-il au programme du bac de NSI ?
Oui. La recherche textuelle et l'algorithme de Boyer-Moore font partie de la rubrique algorithmique de Terminale, et tout le programme de Terminale peut être évalué à l'écrit. On attend la table, le code, une trace et l'intérêt du prétraitement du motif ; l'étude générale du coût, jugée difficile, ne peut pas être exigée.
Boyer-Moore est-il toujours plus rapide que la recherche naïve ?
Non. Il est beaucoup plus rapide quand les lettres lues sont absentes du motif, ce qui est le cas habituel dans un texte en français, et il peut alors ignorer la plupart des caractères. Mais sur un texte très répétitif qui ressemble au motif sauf en tête, il compare davantage que la recherche naïve, parce qu'il découvre la différence en dernier.
Passer à la pratique
Exercices corrigés : Recherche textuelle : Boyer-Moore et Horspool
Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.
Contactez-moi pour une première séance. La recherche textuelle se maîtrise en une heure de travail guidé : une table, une lettre lue au bon endroit, une trace tenue proprement.
