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.

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.

À ne pas confondre en recherche textuelle

Recherche naïveBoyer-Moore-Horspool
Sens de comparaisonDe gauche à droiteDe droite à gauche
Décalage après échecUn cranPlusieurs crans, via le dictionnaire
PrétraitementAucunDictionnaire des positions (dico_lettres)
Pire des casO(n × m)Moins de comparaisons en pratique

Mode Bac : ce qui rapporte des points

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.

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.

  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].
  2. 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].
  3. 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.
  4. 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.
  5. 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.

Comment réviser la recherche textuelle ?

  1. Écrire la recherche naïve de mémoire: Une boucle sur les positions, une boucle de comparaison, un test de fin de motif.
  2. Savoir décrire BMH en trois phrases: Comparaison de droite à gauche, dictionnaire des décalages, sauts multiples.
  3. Retenir les coûts: Naïf en O(n × m) au pire ; BMH souvent plus rapide en pratique.
  4. Manipuler les dictionnaires Python: Construire d = {} puis d[lettre] = position, et lire d[c] ou tester c in d.
  5. 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