Recherche textuelle et algorithme de Boyer-Moore (Bac NSI)
Mis à jour le · AprenAI
La recherche textuelle consiste à trouver un motif dans un texte, par exemple une séquence d'ADN dans une chaîne. Dans les annales digitalisées du Bac NSI, le thème n'apparaît qu'une fois : Métropole France 1 remplacement, 2025, exercice 3, pour 1 point seulement dans un exercice de 8 points sur les papillons, mêlé à du SQL. Il faut compléter une recherche naïve et expliquer l'intérêt de l'algorithme de Boyer-Moore-Horspool.
- 3 sujets officiels
- 0,6 % des sujets
- 2025-2026 années
Comment fonctionne la recherche d'un motif dans un texte ?
Le problème est le suivant : étant donnés un motif seq de longueur m et un texte chaine de longueur n, trouver l'indice du premier caractère où seq apparaît dans chaine, ou -1 s'il n'y est pas. Dans le sujet 2025, la fonction recherche_seq(seq, chaine) joue ce rôle pour une séquence d'ADN représentée par une chaîne de caractères.
La recherche naïve fait glisser une fenêtre de la longueur du motif sur le texte. Pour chaque position de départ i, qui varie de 0 à len(chaine) - len(seq) (d'où range(len(chaine) - len(seq) + 1)), elle compare les caractères un à un avec une variable j. La boucle while j < len(seq) and chaine[i + j] == seq[j] avance tant que les caractères coïncident. À la sortie, si j == len(seq), tous les caractères du motif ont été trouvés : le motif commence à l'indice i, on renvoie i. Sinon on passe à la position suivante, un cran plus loin. Si aucune position ne convient, la fonction renvoie -1. Avec un texte de 10 caractères et un motif de 3, il y a 8 positions à essayer ; dans le pire des cas, chacune demande jusqu'à len(seq) comparaisons, soit un coût en O(n × m).
L'algorithme de Boyer-Moore-Horspool (BMH) accélère la recherche. Il compare le motif à la fenêtre du texte de droite à gauche, en partant du dernier caractère du motif. En cas de non-concordance, il décale le motif de plusieurs positions d'un coup, grâce à un dictionnaire de décalages précalculé, ici par la fonction dico_lettres(seq). Ce dictionnaire associe à chaque lettre du motif (sauf la dernière) la position de sa dernière occurrence, d'où le code d[seq[i]] = i pour i allant de 0 à len(seq) - 2. On regarde le caractère du texte aligné avec la fin du motif : s'il n'apparaît pas dans le motif, on peut décaler le motif de toute sa longueur, puisqu'aucune concordance n'est possible plus tôt. Sinon, on décale juste assez pour aligner ce caractère avec son occurrence dans le motif.
L'avantage donné par le corrigé : alors que la recherche naïve décale d'un seul cran à chaque échec, avec un coût au pire en O(n × m), BMH fait des sauts de plusieurs caractères et réduit fortement le nombre de comparaisons, ce qui le rend souvent sous-linéaire en pratique. Le prétraitement du motif (la construction du dictionnaire) est le prix à payer, et il est court.
- Motif: Séquence de caractères que l'on cherche dans un texte.
- Recherche naïve: Algorithme qui compare le motif à chaque position du texte, en décalant d'un cran à chaque échec.
- Boyer-Moore-Horspool: Algorithme qui compare de droite à gauche et décale le motif de plusieurs crans grâce à un dictionnaire des dernières positions des lettres.
- Prétraitement: Calcul préalable, ici le dictionnaire de décalages, qui évite des comparaisons pendant la recherche.
- Dictionnaire (dict): Structure Python qui associe une valeur à une clé, ici une position à une lettre du motif.
- Fenêtre: Portion du texte de la longueur du motif, alignée avec lui à un instant donné.
À ne pas confondre en recherche textuelle
- Recherche naïve ≠ Boyer-Moore-Horspool: La naïve décale d'un cran à chaque échec ; BMH décale de plusieurs crans grâce au dictionnaire et compare de droite à gauche.
- Pire des cas ≠ Cas pratique: Le pire cas naïf est en O(n × m) ; en pratique, BMH est souvent sous-linéaire, sans que le corrigé l'affirme pour tous les cas.
- Indice i du texte ≠ Indice j du motif: i repère le début de la fenêtre dans chaine ; j repère le caractère courant du motif. La comparaison porte sur chaine[i + j] et seq[j].
- Renvoyer i ≠ Renvoyer -1: On renvoie i dès que le motif est trouvé ; -1 n'est renvoyé qu'après avoir essayé toutes les positions, donc hors de la boucle for.
- Chaîne d'ADN ≠ Séquence caractéristique: chaine est le texte exploré ; seq est le motif à localiser.
| Recherche naïve | Boyer-Moore-Horspool | |
|---|---|---|
| Sens de comparaison | De gauche à droite | De droite à gauche |
| Décalage après échec | Un cran | Plusieurs crans, via le dictionnaire |
| Prétraitement | Aucun | Dictionnaire des positions (dico_lettres) |
| Pire des cas | O(n × m) | Moins de comparaisons en pratique |
Mode Bac : ce qui rapporte des points
- Condition de la boucle while: chaine[i + j] == seq[j] (ou seq[j] == chaine[i + j]).
- Condition du if: j == len(seq) : tous les caractères du motif ont concordé.
- Bornes de la boucle for: range(len(chaine) - len(seq) + 1) : la dernière fenêtre commence à len(chaine) - len(seq).
- Principe de BMH à citer: Comparaison de droite à gauche et dictionnaire de décalages permettant de sauter plusieurs caractères.
- Avantage: Moins de comparaisons que la recherche naïve, qui décale d'un seul cran à chaque échec.
Comment le Bac NSI interroge-t-il sur la recherche textuelle ?
Un seul sujet digitalisé : Métropole France 1 remplacement, 2025, exercice 3. L'exercice vaut 8 points au total et mélange SQL, Python et recherche textuelle sur le thème des papillons ; la part sur Boyer-Moore est de 1 point, ce qui en fait le thème le plus léger du programme dans ces annales. Il est pourtant facile à gagner avec un peu de préparation.
- Compléter la recherche naïve (1): Deux conditions à compléter dans recherche_seq : la comparaison des caractères dans la boucle while et le test final avant de renvoyer l'indice (question 14).
- Expliquer le principe et l'avantage de Boyer-Moore-Horspool (1): À partir du code de recherche_BMH et de dico_lettres, décrire le principe et expliquer en quoi l'algorithme est plus efficace que la recherche naïve.
- Exercice 3 - Recherche textuelle et algorithme de… · Métropole 1 remplacement 2025 · Compléter la recherche naïve
- Exercice 3 - Recherche textuelle et algorithme de… · Métropole 1 remplacement 2025 · Expliquer le principe et l'avantage de Boyer-Moore-Horspool
Entraîne-toi : Recherche textuelle et algorithme de Boyer-Moore (3 sujets officiels)
Tous les sujets de NSI sur « Recherche textuelle et algorithme de Boyer-Moore » (2025-2026), avec le corrigé.
Comment compléter une recherche de motif en Python ?
Exemple : Métropole France 1 remplacement, 2025, exercice 3, question 14. Le code contient une boucle for i in range(len(chaine) - len(seq) + 1), puis j = 0 et while j < len(seq) and ... : j += 1, puis if ... : return i, et enfin return -1.
- Comprendre le rôle de i et de j: i est le début de la fenêtre dans chaine, j le nombre de caractères déjà concordants. Le caractère du texte comparé à seq[j] est chaine[i + j].
- Compléter la ligne du while: La boucle continue tant que j < len(seq) et que les caractères coïncident : chaine[i + j] == seq[j].
- Compléter le if: Après la boucle, deux sorties possibles : divergence ou fin du motif. Il faut tester la seconde : j == len(seq). Alors le motif commence à l'indice i.
- Vérifier avec un petit exemple: Si seq = "AT" et chaine = "GATTACA", pour i = 1 la boucle compare A puis T, j atteint 2 = len(seq) et la fonction renvoie 1.
- Rédiger l'explication de BMH: Trois éléments : comparaison de droite à gauche, dictionnaire de décalages construit par dico_lettres, saut de plusieurs caractères au lieu d'un. Ajoutez : si le caractère du texte aligné avec la fin du motif n'est pas dans le motif, on décale de toute la longueur du motif.
Quelles erreurs éviter en recherche textuelle ?
La solution de ce sujet est une réponse type sans barème détaillé. Les attentes concernent surtout des conditions exactes et une explication qui nomme les deux idées de BMH.
- Comparer seq[j] à chaine[j]: Il faut décaler de i : chaine[i + j]. Sinon on compare toujours le début du texte.
- Tester une condition trop faible: Le if doit vérifier que tout le motif a concordé : j == len(seq), et non j > 0.
- Dépasser la fin du texte: La borne len(chaine) - len(seq) + 1 évite un IndexError lorsque la fenêtre sort du texte.
- Renvoyer -1 dans la boucle: Le return -1 se place après la boucle for, une fois toutes les positions testées.
- Expliquer BMH sans parler du décalage: Dire seulement « c'est plus rapide » ne suffit pas : nommez le dictionnaire de décalages et le saut de plusieurs caractères.
Comment réviser la recherche textuelle ?
- Écrire la recherche naïve de mémoire: Une boucle sur les positions, une boucle de comparaison, un test de fin de motif.
- Savoir décrire BMH en trois phrases: Comparaison de droite à gauche, dictionnaire des décalages, sauts multiples.
- Retenir les coûts: Naïf en O(n × m) au pire ; BMH souvent plus rapide en pratique.
- Manipuler les dictionnaires Python: Construire d = {} puis d[lettre] = position, et lire d[c] ou tester c in d.
- Refaire l'exercice officiel: Seule la partie de recherche textuelle vaut 1 point, mais l'exercice entier entraîne SQL et tri.
Comment fonctionne la recherche naïve d'un motif dans un texte ?
On place le motif au début du texte et on compare caractère par caractère. En cas d'échec, on décale le motif d'un cran et on recommence jusqu'à trouver le motif ou atteindre la fin.
Qu'est-ce que l'algorithme de Boyer-Moore-Horspool ?
C'est une recherche de motif qui compare de droite à gauche et qui décale le motif de plusieurs caractères à l'aide d'un dictionnaire des dernières positions des lettres du motif.
Pourquoi Boyer-Moore est-il plus rapide que la recherche naïve ?
Parce qu'il saute plusieurs positions à la fois au lieu d'avancer d'un cran, ce qui réduit le nombre de comparaisons. Le coût naïf au pire est de l'ordre de n × m.
Que fait la fonction dico_lettres du sujet 2025 ?
Elle construit un dictionnaire qui associe à chaque lettre du motif, sauf la dernière, sa position : d[seq[i]] = i pour i de 0 à len(seq) - 2.
Combien de points vaut la recherche textuelle au Bac NSI ?
Dans les annales digitalisées, un seul sujet en parle, en 2025, pour 1 point dans un exercice de 8 points.
Plus sur l'épreuve de NSI
- Piles, files, listes et dictionnaires · 66 sujets
- Programmation orientée objet · 46 sujets
- Arbres et arbres binaires de recherche · 50 sujets
- Graphes : modélisation et parcours · 27 sujets
- Bases de données et SQL · 83 sujets
- Binaire, entiers et opérateurs booléens · 16 sujets
- Architectures matérielles et systèmes d'exploitation · 32 sujets
- Réseaux : adressage IP et sous-réseaux · 39 sujets
- Protocoles de routage : RIP et OSPF · 51 sujets
- Sécurisation des communications : chiffrement et HTTPS · 9 sujets
- Récursivité · 24 sujets
- Modularité, API et paradigmes de programmation · 6 sujets
- Mise au point des programmes : bugs, assertions et tests · 13 sujets
- Programme comme donnée, calculabilité et décidabilité · 2 sujets
- Diviser pour régner · 8 sujets
- Programmation dynamique · 7 sujets
- Coût des algorithmes, tris et recherche · 23 sujets