Numérique et sciences informatiques (spécialité) · TerminaleBac
Recherche textuelle et Boyer-Moore : quiz de Terminale NSI
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
- Chercher un motif dans un texte, c'est trouver une ou toutes les occurrences du mot x dans le mot t.2
- Le coût d'une recherche textuelle s'évalue surtout en comptant les comparaisons effectuées.1
- Boyer-Moore date de 1977 ; la version de Horspool en est une forme simplifiée.1
- Les algorithmes à motif prétraité, comme Knuth-Morris-Pratt, ont un temps linéaire en la taille du texte.2
Avant de commencer
Ce quiz vérifie ce que tu as retenu sur la recherche textuelle et sur l'algorithme de Boyer-Moore. Il couvre le vocabulaire (motif, texte, occurrence), la façon de mesurer le coût d'une recherche, l'histoire de l'algorithme et sa version simplifiée, ainsi que quelques calculs que tu peux refaire à la main.
Pour comparer deux méthodes de recherche, on compte des opérations : ce sont surtout les comparaisons entre caractères qui servent d'unité de mesure.1 Un algorithme qui évite des comparaisons inutiles est donc plus efficace.
Quiz
14 questions · correction immédiate · ton score reste sur ton appareil.
-
Le motif est le mot que l'on cherche, le texte étant le mot dans lequel on le cherche.2 Confondre les deux inverse le problème. Quant au tableau des décalages, c'est un outil de certains algorithmes, pas la définition du motif.
-
Le motif apparaît deux fois, aux positions 2 et 4.2 Les deux occurrences se chevauchent : le dernier de la première est le premier de la seconde. Répondre 1 revient à oublier les occurrences qui se chevauchent.
-
L'algorithme de Boyer et Moore a été inventé en 1977.1 1997 ressemble à 1977 par inversion de chiffres, mais ne correspond pas à l'invention de l'algorithme.
-
Le coût se mesure surtout en comptant les comparaisons effectuées.1 La longueur du code n'a aucun lien avec le temps d'exécution. La taille de l'alphabet peut influencer le résultat, mais elle ne suffit pas à mesurer le coût.
-
Ces algorithmes relèvent de la classe où le motif est prétraité, avec un temps linéaire en la taille du texte.2 Un temps constant est impossible : il faut au moins parcourir le texte. Prétraiter le texte correspond à l'autre classe de situations.
-
L'arbre des suffixes permet de stocker le texte et de trouver ensuite les occurrences d'un motif.2 Il s'applique donc quand on prépare le texte, à l'inverse de Knuth-Morris-Pratt.
-
Boyer et Moore étaient alors informaticiens à l'université d'Austin, au Texas.1 La recherche approximative trouve des occurrences proches du motif, en autorisant des variations sur le motif ou sur les segments de texte.2 La version complète est au contraire difficile à justifier et à programmer.1 Enfin, on cherche une ou toutes les occurrences du motif.2
-
Le texte compte 6 caractères et le motif 2 : il y a alignements possibles. Chaque alignement coûte une seule comparaison, soit 5 au total. L'erreur tentante est de répondre 6 en oubliant que le motif ne peut pas commencer sur le dernier caractère, ou 10 en comptant deux comparaisons par alignement.
-
Le motif peut commencer du premier caractère jusqu'au 17e, car il doit tenir entièrement dans le texte : . Répondre 16 (en oubliant le ) ou 20 (en ignorant la longueur du motif) sont les deux erreurs fréquentes.
-
C'est faux : une occurrence est un morceau du texte, donc le motif ne peut pas être plus long que le texte. Aucun alignement n'est possible, et le nombre d'occurrences est nul.
-
Suivant la situation, c'est le motif ou le texte qui se prête à une préparation.2 Si le motif n'est pas connu à l'avance, on ne peut pas le préparer : c'est donc le texte. Le résultat final, lui, n'existe qu'après la recherche.
-
Ces méthodes s'appliquent au traitement des séquences génétiques en bioinformatique, mais aussi au traitement de la langue naturelle, à l'analyse de séquences musicales ou à la détection de plagiats.2 Elles ne sont donc pas seulement théoriques.
Les questions qu'on se pose
Pourquoi compte-t-on les comparaisons pour juger un algorithme de recherche ?
La comparaison de caractères est l'opération qui revient le plus souvent dans la recherche d'un motif, et c'est elle qui sert surtout à évaluer le coût.1 Moins un algorithme en fait, plus il est rapide. Pour comparer deux méthodes, tu peux compter ces comparaisons sur un même texte et un même motif.
Dois-je connaître l'algorithme complet de Boyer-Moore ou seulement la version de Horspool ?
Le document de référence présente une version simplifiée, celle de Horspool, et précise que l'algorithme complet utilise une seconde table de décalage, beaucoup plus difficile à calculer.1 Il ajoute que la justification et la programmation de la version complète posent des difficultés qui dépassent ce qui est présenté.1 Concentre-toi donc d'abord sur le principe de la version simplifiée et sur le gain de comparaisons qu'elle apporte.
Sources
- Document Éduscol - Recherche textuelle et algorithme de Boyer-Moore, Éduscol (Ministère de l'Éducation nationale). Consulté le 7 novembre 2026.
- Algorithmique du texte, Wikipédia. Consulté le 7 novembre 2026.
Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.