Exercices#

Recherche textuelle

Usage de l’IA, indiqué sur chaque exercice : aucune ; en appui (déboguer, reformuler, vérifier ; la réponse finale est écrite et comprise par vous) ; l’exercice s’appuie sur une réponse d’IA. Voir la charte d’usage de l’IA.

Rappel : les positions sont comptées à partir de \(0\). Niveau : ★ échauffement, ★★ classique (niveau bac), ★★★ défi ; les coups de pouce et les corrigés se déplient sous chaque exercice.

La méthode naïve#

★ Exercice 1 — Naïf, à la main #

• essentiel

On cherche le motif AA dans le texte CAAAB.

Dérouler la méthode naïve : à quelle(s) position(s) trouve-t-on le motif ?
Cette méthode compare le motif de la gauche vers la droite et décale d’un cran à chaque échec. Quel est son coût dans le pire des cas, en fonction de \(n\) (longueur du texte) et \(m\) (longueur du motif) ?

Coup de pouce

Placer le motif sous le texte à chaque position possible, de \(0\) à \(n - m\), et comparer lettre à lettre. Pour le coût, imaginer un texte et un motif où presque toutes les lettres coïncident à chaque position.

Corrigé

C``AA``AB et CA``AA``B : le motif AA est trouvé aux positions 1 et 2.

▷ Erreur fréquente. S’arrêter à la première occurrence, ou sauter après elle : la méthode naïve teste toutes les positions, et deux occurrences peuvent se chevaucher (AA en \(1\) et en \(2\)).
Au pire, on compare presque tout le motif (\(m\) comparaisons) à chacune des \(\approx n\) positions : coût \(O(n\times m)\) (quadratique).

★ Exercice 2 — Naïf, en Python #

Recopier et compléter la fonction de recherche naïve :

Coup de pouce

Ligne (a) : la dernière position de départ possible est celle où le motif touche la fin du texte. Ligne (b) : à la sortie de la boucle while, que vaut j si toutes les lettres ont correspondu ?

def recherche_naive(motif, texte):
    n, m = len(texte), len(motif)
    positions = []
    for i in range(...):                 # (a) toutes les positions de depart
        j = 0
        while j < m and texte[i + j] == motif[j]:
            j += 1
        if ... :                          # (b) tout le motif a correspondu ?
            positions.append(i)
    return positions

Corrigé

Démarche : on teste chaque position de départ, de \(0\) à \(n - m\) ; la boucle while avance tant que les lettres coïncident, et le motif est trouvé si elle est allée jusqu’au bout.

(a) range(n - m + 1) ; (b) if j == m:.

▷ Erreur fréquente. Écrire range(n - m) : la dernière position de départ, \(n - m\), ne serait pas testée, et un motif placé tout à la fin du texte serait manqué.

Boyer-Moore#

★★ Exercice 3 — Les deux idées, et un grand saut #

• essentiel

Rappeler les deux idées de l’algorithme de Boyer-Moore.
On considère le motif CGGCAG. Donner, pour chaque lettre du motif, sa dernière position (table du prétraitement de Boyer-Moore).
On compare (de droite à gauche) et la lettre du texte qui provoque l’échec est un T. Sachant que T n’apparaît pas dans CGGCAG, de combien de crans peut-on décaler le motif d’un seul coup ? Justifier.

Coup de pouce

Si T n’apparaît nulle part dans le motif, un alignement où le motif recouvre ce T peut-il donner une occurrence ?

Corrigé

(1) comparer le motif de droite à gauche ; (2) prétraiter le motif pour sauter de plusieurs crans en cas d’échec (règle du mauvais caractère).
CGGCAG : C\(\to 3\), G\(\to 5\), A\(\to 4\) (dernières positions ; C0 G1 G2 C3 A4 G5).

▷ Erreur fréquente. Retenir la première position d’une lettre répétée (G\(\to 1\)) : la table de Boyer-Moore garde la dernière position, ici G\(\to 5\).
T n’apparaît pas dans le motif : aucun alignement où T tomberait dans le motif ne peut réussir. On saute donc de 6 crans (toute la longueur du motif) d’un seul coup.

★★ Exercice 4 — Dérouler Boyer-Moore #

On cherche le motif GCAGC dans le texte ACGTGCAGCTGCAGC (règle du mauvais caractère). La table des dernières positions est G\(\to 3\), C\(\to 4\)… (la compléter au besoin).

position i	fenêtre du texte	échec / trouvé	décalage
i = 0	`ACGTG`
… (compléter jusqu’à la fin du texte) …

Donner la (les) position(s) d’occurrence.

Coup de pouce

À chaque échec, repérer la lettre c du texte qui fait échouer et l’indice \(j\) du motif où cela se produit, puis appliquer la règle du mauvais caractère du cours (décalage d’au moins \(1\)).

Corrigé

Table (dernières positions) de GCAGC : G\(\to 3\), C\(\to 4\), A\(\to 2\).

position \(i\)	fenêtre	échec / trouvé	décalage
\(i=0\)	`ACGTG`	échec en \(j=4\) (`G` du texte)	\(1\)
\(i=1\)	`CGTGC`	échec en \(j=2\) (`T`)	\(3\)
\(i=4\)	`GCAGC`	trouvé	\(1\)
\(i=5\)	`CAGCT`	échec en \(j=4\) (`T`)	\(5\)
\(i=10\)	`GCAGC`	trouvé	—

Occurrences aux positions 4 et 10.

Boyer-Moore-Horspool#

★★ Exercice 5 — Construire la table de décalage #

Pour un motif de longueur \(m\), la table de Horspool donne à la lettre en position \(k\) (sauf la dernière) le décalage \(m-1-k\) ; toute autre lettre reçoit \(m\).

Construire la table de décalage de chacun de ces motifs (préciser le décalage par défaut) :

ANANAS
GATTACA
ABRACADABRA

Coup de pouce

Parcourir les lettres de gauche à droite en ignorant la dernière : quand une lettre revient, sa nouvelle valeur remplace l’ancienne.

Corrigé

ANANAS (\(m=6\)) : A\(\to 1\), N\(\to 2\), défaut 6. (La dernière occurrence de A avant la fin est en position 4 \(\to 1\) ; de N en position 3 \(\to 2\).)
GATTACA (\(m=7\)) : G\(\to 6\), A\(\to 2\), T\(\to 3\), C\(\to 1\), défaut 7.
ABRACADABRA (\(m=11\)) : A\(\to 3\), B\(\to 2\), R\(\to 1\), C\(\to 6\), D\(\to 4\), défaut 11.

▷ Erreur fréquente. Donner à la dernière lettre du motif le décalage \(0\) : on parcourt les lettres sauf la dernière. Dans ANANAS, S n’apparaît qu’en dernière position : il prend le décalage par défaut, \(6\).

★★ Exercice 6 — Dérouler Horspool #

• essentiel

On cherche ACGT dans GTACACGTAC. Table : A\(\to 3\), C\(\to 2\), G\(\to 1\), autres \(\to 4\).

Recopier et compléter le tableau (la lettre de fin est celle du texte alignée avec la dernière case de la fenêtre) :

position i	fenêtre	lettre de fin	décalage
i = 0	`GTAC`	`C`	…
…

Conclure : le motif est-il présent, et où ?

Coup de pouce

À chaque étape, la lettre de fin est celle du texte en position \(i+3\) ; son décalage se lit dans la table.

Corrigé

position \(i\)	fenêtre	lettre de fin	décalage
\(i=0\)	`GTAC`	`C`	\(2\)
\(i=2\)	`ACAC`	`C`	\(2\)
\(i=4\)	`ACGT`	`T` (trouvé)	—

Le motif ACGT est trouvé à la position 4.

▷ Erreur fréquente. Chercher la lettre de fin dans le motif au lieu du texte : c’est la lettre du texte alignée avec la dernière case de la fenêtre qui commande le saut.

★★ Exercice 7 — Horspool en Python #

Recopier et compléter les deux fonctions :

Coup de pouce

Pour (c), la lettre c n’est pas dans la table : elle n’apparaît pas dans le motif (sauf peut-être en dernière position). De combien peut-on alors décaler la fenêtre ?

def table_decalage(motif):
    m = len(motif)
    dec = {}
    for k in range(...):              # (a) toutes les lettres SAUF la derniere
        dec[motif[k]] = ...           # (b) le decalage
    return dec

def horspool(motif, texte):
    n, m = len(texte), len(motif)
    dec = table_decalage(motif)
    positions = []
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and texte[i + j] == motif[j]:
            j -= 1
        if j < 0:
            positions.append(i)
        c = texte[i + m - 1]
        if c in dec:
            i += dec[c]
        else:
            i += ...                   # (c) lettre absente de la table
    return positions

Corrigé

Démarche : la table parcourt les lettres du motif sauf la dernière, la lettre en position \(k\) recevant \(m - 1 - k\) ; une lettre absente de la table autorise le saut maximal.

(a) range(m - 1) ; (b) dec[motif[k]] = m - 1 - k ; (c) i += m (lettre absente de la table : saut maximal).

Coût#

★★ Exercice 8 — Le miracle du sous-linéaire #

• essentiel

Combien coûte le prétraitement (construction de la table) en fonction de \(m\) ?
Expliquer pourquoi Horspool peut trouver un motif sans lire tous les caractères du texte.

Coup de pouce

Q2 : quand on saute de \(m\) crans, quelles lettres du texte n’ont jamais été lues ?
Vrai ou faux (justifier) : « plus le motif est long, plus la recherche est lente ».
Boyer-Moore est-il toujours plus rapide que la méthode naïve ?

Coup de pouce

Q4 : penser au pire cas, par exemple chercher AAA dans AAAAAAAA : les sauts sont-ils grands ? combien de comparaisons par alignement ?

Corrigé

Une seule passe sur le motif : \(O(m)\) (les lettres absentes du motif ne sont pas stockées dans la table).
À chaque échec, Horspool saute de plusieurs cases : les lettres survolées ne sont jamais lues. On peut donc conclure en bien moins de \(n\) comparaisons.
Faux : c’est le contraire ! Plus le motif est long, plus les sauts possibles sont grands, donc plus la recherche est rapide (jusqu’à \(\approx n/m\) comparaisons).
Non : au pire cas, Boyer-Moore reste en \(O(n\times m)\), comme le naïf. C’est en pratique, sur des textes ordinaires, qu’il est spectaculairement plus rapide.

★★★ Exercice 9 — Exercice d’entraînement — Chercher un gène dans l’ADN #

≈ 30 min

On modélise un brin d’ADN par une chaîne sur l’alphabet {A, T, G, C}, et on cherche le motif GATTACA par l’algorithme de Horspool.

Construire la table de décalage de GATTACA (préciser le décalage par défaut).
Dérouler Horspool sur le brin GTAGATTACAGT : donner la suite des positions \(i\) testées, la lettre de fin de fenêtre, et le décalage à chaque étape. À quelle position trouve-t-on le motif ?

Coup de pouce

Q2 : le motif a \(7\) lettres : la lettre de fin de la fenêtre \(i\) est brin[i + 6].

Coup de pouce 2 (début de solution)

Q2 : première étape : \(i=0\), fenêtre GTAGATT, lettre de fin T, décalage \(3\).

On donne la fonction ci-dessous, qui compte le nombre d’occurrences. Compléter les lignes (a) et (b).

Coup de pouce

Q3 : comparer avec la fonction horspool du cours : quelle condition signalait une occurrence ?

def compte_occurrences(motif, texte):
    dec = table_decalage(motif)
    n, m = len(texte), len(motif)
    nb = 0
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and texte[i + j] == motif[j]:
            j -= 1
        if ... :                       # (a) motif entierement retrouve ?
            nb = nb + 1
        c = texte[i + m - 1]
        if c in dec:
            i += dec[c]
        else:
            i += ...                   # (b) decalage par defaut ?
    return nb

Un génome humain compte environ \(3\) milliards de bases. En quoi le choix de Horspool plutôt que la méthode naïve est-il crucial ici ?

Corrigé

GATTACA : G\(\to 6\), A\(\to 2\), T\(\to 3\), C\(\to 1\), défaut 7.
Sur GTAGATTACAGT :

\(i\) fenêtre lettre de fin décalage

\(0\) GTAGATT T \(3\)

\(3\) GATTACA A (trouvé) \(2\)

\(5\) TTACAGT T \(3\) (dépasse la fin)

Le motif est trouvé à la position 3.
(a) if j < 0: ; (b) m (le décalage par défaut).
Sur \(3\) milliards de bases, un coût quadratique \(O(n\times m)\) serait prohibitif. Horspool, souvent sous-linéaire (il saute une grande partie du brin sans la lire), rend la recherche réalisable en un temps raisonnable.

Vers le bac#

★ Exercice 10 — Type bac — Parcourir une chaîne de caractères (d’après Centres étrangers 2023, jour 2) #

≈ 15 min

On rappelle quelques notions sur la manipulation des chaînes de caractères en Python. Une chaîne de caractères se comporte comme un tableau de caractères que l’on ne peut pas modifier. Par exemple :

>>> une_chaine = 'Bonjour'
>>> une_chaine[3]
'j'
>>> une_chaine[3] = 'z'
TypeError: 'str' object does not support item assignment

On peut aussi utiliser l’opérateur de concaténation + :

>>> une_chaine = 'a' + 'b'
>>> une_chaine
'ab'
>>> une_chaine = une_chaine + 'c'
>>> une_chaine
'abc'

On définit la fonction bonjour par le code suivant :

def bonjour(nom):
    return 'Bonjour ' + nom + ' !'

Donner le résultat de l’exécution de bonjour(’Alan’).

On exécute le programme suivant :

une_chaine = 'Bonjour'
x = (une_chaine[2] == une_chaine[3])
y = (une_chaine[4] == une_chaine[1])

Donner le type et les valeurs des variables x et y.

▶ Écrire une fonction occurrences_lettre(une_chaine, une_lettre) prenant en paramètres une chaîne une_chaine et une lettre une_lettre et renvoyant le nombre d’occurrences de une_lettre dans une_chaine.

Coup de pouce

Question 2 : relever les lettres d’indices \(1\), \(2\), \(3\) et \(4\) de ’Bonjour’ (le premier indice est \(0\)) ; une comparaison avec == donne un booléen. Question 3 : un compteur et une boucle sur les caractères de la chaîne.

Corrigé

Barème indicatif (sur 2) : Q1 : 0,5 ; Q2 : 0,5 ; Q3 : 1

bonjour(’Alan’) renvoie la chaîne ’Bonjour Alan !’ (concaténation de trois chaînes).
une_chaine[2] vaut ’n’ et une_chaine[3] vaut ’j’ : x vaut False. une_chaine[4] et une_chaine[1] valent tous deux ’o’ : y vaut True. Les deux variables sont de type booléen (bool).
Démarche : on parcourt la chaîne caractère par caractère avec un compteur (c’est la méthode naïve pour un motif d’une seule lettre) :
```
def occurrences_lettre(une_chaine, une_lettre):
    nb = 0
    for c in une_chaine:
        if c == une_lettre:
            nb = nb + 1
    return nb
```
Par exemple occurrences_lettre(’Bonjour’, ’o’) renvoie 2.

★ Exercice 11 — Type bac — Le principe de Boyer-Moore (d’après Asie 2025, jour 1) #

≈ 10 min

Dans ce sujet, on veut repérer un mot-clé (par exemple "while") dans le texte d’un programme Python. On suppose disposer d’une fonction recherche(mot, texte) qui renvoie True si la chaîne de caractères mot est présente dans la chaîne de caractères texte, et False sinon.

Expliquer succinctement le principe de l’algorithme de Boyer-Moore, qui permet d’implémenter cette fonction recherche.

Coup de pouce

Relire les deux idées de Boyer-Moore dans le cours : dans quel sens compare-t-on le motif au texte, et que permet la table calculée à l’avance quand une comparaison échoue ?

Corrigé

Barème indicatif (sur 1) : Q1 : 1

On aligne le mot sous le début du texte, puis on compare les caractères de droite à gauche, en partant de la fin du mot. Si tous les caractères coïncident, le mot est trouvé (True). Sinon, on regarde le caractère du texte qui a provoqué la différence (règle du « mauvais caractère ») : grâce à une table calculée à l’avance à partir du mot seul (prétraitement), on décale le mot vers la droite de façon à aligner ce caractère avec sa dernière occurrence dans le mot, ou au-delà de ce caractère s’il n’apparaît pas dans le mot. On recommence jusqu’à trouver le mot ou dépasser la fin du texte (False). Ces sauts permettent de ne pas lire tous les caractères du texte : l’algorithme est en pratique bien plus rapide que la méthode naïve, surtout pour des mots longs.

★★★ Exercice 12 — Type bac — Rechercher et remplacer dans un éditeur (sujet maison, façon bac) #

≈ 45 min

Un éditeur de texte propose deux commandes : Rechercher, qui surligne toutes les occurrences d’un motif, et Remplacer tout, qui remplace chaque occurrence d’un motif par un autre texte. On étudie leur programmation avec la méthode naïve. On rappelle la fonction du cours :

def recherche_naive(motif, texte):
    n, m = len(texte), len(motif)
    positions = []
    for i in range(n - m + 1):
        j = 0
        while j < m and texte[i + j] == motif[j]:
            j += 1
        if j == m:
            positions.append(i)
    return positions

Dans les questions 1 à 3 et 6, la variable texte contient la chaîne ’LE CHAT ET LE CHATON’.

Donner la longueur \(n\) de texte, puis la valeur renvoyée par chacun des appels suivants :

recherche_naive(’CHAT’, texte) et recherche_naive(’LE’, texte)
Combien de positions de départ i la boucle for examine-t-elle lors de la recherche du motif ’CHAT’ ?
Pour mesurer le coût, on compte les comparaisons de caractères, c’est-à-dire le nombre d’évaluations de texte[i + j] == motif[j]. Expliquer pourquoi, lors de la recherche de ’CHAT’, toutes les positions de départ sauf deux ne coûtent qu’une seule comparaison. En déduire le nombre total de comparaisons.
Donner un motif de longueur \(4\) et un texte de longueur \(12\), écrits avec les lettres A et B, pour lesquels la méthode naïve effectue le plus grand nombre possible de comparaisons. Combien en effectue-t-elle ? Exprimer ce nombre en fonction de \(n\) et \(m\).

Coup de pouce

Q4 : pour que chaque position de départ coûte \(m\) comparaisons, le motif doit « presque » correspondre partout : quel texte et quel motif choisir avec seulement deux lettres ?
▶ Écrire une fonction est_occurrence(motif, texte, i) qui renvoie True si motif apparaît dans texte à partir de la position i, et False sinon. On suppose que i + len(motif) <= len(texte).

Coup de pouce 2 (début de solution)

Q5 :
def est_occurrence(motif, texte, i):
for j in range(len(motif)):
if texte[i + j] != motif[j]:

▶ Pour la commande Remplacer tout, on parcourt le texte de gauche à droite en construisant une nouvelle chaîne. Recopier et compléter les lignes (a) à (d), puis donner la valeur renvoyée par remplacer_tout(’CHAT’, ’LOUP’, texte).

Coup de pouce

Q6 : deux cas : une occurrence commence en i, ou non. Dans chaque cas, que faut-il ajouter à resultat, et de combien faut-il avancer ?

def remplacer_tout(motif, nouveau, texte):
    n, m = len(texte), len(motif)
    resultat = ''
    i = 0
    while i < n:
        if i <= n - m and est_occurrence(motif, texte, i):
            resultat = ...           # (a)
            i = ...                  # (b)
        else:
            resultat = ...           # (c)
            i = ...                  # (d)
    return resultat

L’appel recherche_naive(’AA’, ’AAA’) renvoie [0, 1], alors que remplacer_tout(’AA’, ’B’, ’AAA’) renvoie ’BA’. Expliquer cette différence, et pourquoi c’est bien le comportement attendu d’un éditeur.
Un fichier contient un million de caractères et l’on cherche un motif de \(10\) caractères. Donner l’ordre de grandeur du nombre de comparaisons de la méthode naïve dans le pire des cas. Citer un algorithme du cours plus efficace en pratique, et l’idée qui le rend plus rapide.

Corrigé

Barème indicatif (sur 6) : Q1 : 0,75 ; Q2 : 0,5 ; Q3 : 0,75 ; Q4 : 0,75 ; Q5 : 1 ; Q6 : 1,25 ; Q7 : 0,5 ; Q8 : 0,5

\(n = 20\) (les espaces comptent). recherche_naive(’CHAT’, texte) renvoie [3, 14] et recherche_naive(’LE’, texte) renvoie [0, 11].
La boucle examine les positions \(0\) à \(n - m = 16\), soit \(n - m + 1 = \textbf{17}\) positions.
La première comparaison porte sur motif[0], c’est-à-dire C. Or le texte ne contient la lettre C qu’aux positions \(3\) et \(14\) : partout ailleurs, la première comparaison échoue et la boucle while s’arrête aussitôt (1 comparaison). Aux positions \(3\) et \(14\), les quatre lettres correspondent (4 comparaisons). Total : \(15 \times 1 + 2 \times 4 = \textbf{23}\) comparaisons.
Par exemple le motif ’AAAB’ dans le texte ’AAAAAAAAAAAA’ (douze A) : à chacune des \(12 - 4 + 1 = 9\) positions, les trois A correspondent et l’échec n’a lieu que sur la dernière lettre, soit \(4\) comparaisons. Total : \(9 \times 4 = \textbf{36}\) comparaisons, c’est-à-dire \((n - m + 1) \times m\) : le maximum possible, puisqu’on ne fait jamais plus de \(m\) comparaisons par position. (Le motif ’AAAA’ convient aussi.)

On compare lettre à lettre, comme dans la méthode naïve :

def est_occurrence(motif, texte, i):
    for j in range(len(motif)):
        if texte[i + j] != motif[j]:
            return False
    return True

(a) resultat = resultat + nouveau ; (b) i = i + m (on saute toute l’occurrence) ; (c) resultat = resultat + texte[i] ; (d) i = i + 1.

remplacer_tout(’CHAT’, ’LOUP’, texte) renvoie ’LE LOUP ET LE LOUPON’ (le CHAT de CHATON est remplacé lui aussi).
recherche_naive teste toutes les positions, y compris celles qui chevauchent une occurrence déjà trouvée : AA est présent en \(0\) et en \(1\). remplacer_tout, après une occurrence, saute les \(m\) caractères remplacés (ligne (b)) : l’occurrence en \(0\) donne B, puis on reprend en position \(2\), où il ne reste que A, recopié tel quel. C’est le comportement attendu : un même caractère du texte ne peut pas être remplacé deux fois.
Au pire \((n - m + 1) \times m \approx 10^6 \times 10 = 10^7\) comparaisons. L’algorithme de Boyer-Moore (ou sa version simplifiée, Horspool) est bien plus rapide en pratique : il compare le motif de droite à gauche et, grâce à une table calculée à l’avance à partir du motif, saute plusieurs positions d’un coup en cas d’échec, sans lire les caractères survolés.

★★ Exercice 13 — Type bac — Un antivirus à la recherche de signatures (sujet maison, façon bac) #

≈ 45 min

Un antivirus repère un logiciel malveillant connu en cherchant sa signature — une courte suite d’octets qui le caractérise — dans le contenu des fichiers. Pour simplifier, le contenu d’un fichier et les signatures sont représentés par des chaînes de caractères écrites avec les chiffres hexadécimaux 0 à 9 et A à F, et l’on ne se préoccupe pas du découpage en octets.

L’antivirus utilise l’algorithme de Boyer-Moore-Horspool. On dispose des fonctions table_decalage(motif) et horspool(motif, texte) du cours ; horspool renvoie la liste des positions des occurrences de motif dans texte.

Rappeler comment est construite la table de décalage d’un motif de longueur \(m\). Construire la table de décalage de la signature ’4D5A90’ (préciser le décalage par défaut).
Construire la table de décalage de la signature ’E8FFFF’. La lettre F est la dernière lettre du motif : pourquoi figure-t-elle pourtant dans la table, et avec quel décalage ?

Coup de pouce

Q2 : seule la dernière position du motif est ignorée : la lettre F apparaît-elle aussi ailleurs dans E8FFFF ?
Le contenu d’un fichier, de \(22\) caractères, est :

contenu = ’00E84D5A0090FF4D5A90C3’

Dérouler horspool(’4D5A90’, contenu) en recopiant et complétant le tableau ci-dessous. Quelle valeur la fonction renvoie-t-elle ?

position i fenêtre lettre de fin décalage

i = 0 00E84D … …

…
Combien d’alignements Horspool a-t-il testés ? Combien la méthode naïve en aurait-elle testés ? Combien de comparaisons de caractères Horspool a-t-il effectuées au total ?
▶ Écrire une fonction est_infecte(contenu, signatures) qui prend en paramètres le contenu d’un fichier et une liste de signatures, et renvoie True si au moins une des signatures apparaît dans le contenu, False sinon. On utilisera la fonction horspool.

Coup de pouce

Q5 : parcourir la liste des signatures : que renvoie horspool quand la signature est absente ? Peut-on conclure dès la première trouvée ?
L’antivirus analyse \(100\,000\) fichiers avec la même liste de \(1\,000\) signatures. Combien de fois la table de décalage de chaque signature est-elle construite avec la fonction est_infecte ? Proposer, sans écrire tout le code, une organisation qui évite ce travail inutile.
L’éditeur de l’antivirus affirme : « plus nos signatures sont longues, plus l’analyse est rapide ». Cette affirmation est-elle plausible ? Justifier.

Corrigé

Barème indicatif (sur 6) : Q1 : 0,75 ; Q2 : 0,75 ; Q3 : 1,25 ; Q4 : 0,75 ; Q5 : 1 ; Q6 : 0,75 ; Q7 : 0,75

On parcourt les lettres du motif sauf la dernière : la lettre en position \(k\) reçoit le décalage \(m - 1 - k\) (si une lettre apparaît plusieurs fois, c’est sa dernière position qui l’emporte) ; toute autre lettre reçoit le décalage par défaut \(m\).

’4D5A90’ (\(m = 6\)) : 4\(\to 5\), D\(\to 4\), 5\(\to 3\), A\(\to 2\), 9\(\to 1\), défaut 6.
’E8FFFF’ (\(m = 6\)) : E\(\to 5\), 8\(\to 4\), F\(\to 1\), défaut 6. On n’exclut que la dernière case du motif, pas la lettre F elle-même : F apparaît aussi aux positions \(2\), \(3\) et \(4\), et c’est la position \(4\) (la plus à droite hors dernière case) qui donne le décalage \(6 - 1 - 4 = 1\).

Déroulé de Horspool :

position \(i\)	fenêtre	lettre de fin	décalage
\(i=0\)	`00E84D`	`D`	\(4\)
\(i=4\)	`4D5A00`	`0` (échec en \(j = 4\))	\(6\)
\(i=10\)	`90FF4D`	`D`	\(4\)
\(i=14\)	`4D5A90`	`0` (trouvé)	\(6\) (dépasse la fin)

La fonction renvoie [14].

Horspool a testé 4 alignements, contre \(22 - 6 + 1 = \textbf{17}\) pour la méthode naïve. Comparaisons : \(1\) (en \(i=0\)) \(+ 2\) (en \(i=4\) : 0 correspond, puis 0 \(\neq\) 9) \(+ 1\) (en \(i=10\)) \(+ 6\) (en \(i=14\)) \(= \textbf{10}\) comparaisons. (La méthode naïve en effectue \(26\).)
On essaie les signatures une à une :
```
def est_infecte(contenu, signatures):
    for s in signatures:
        if len(horspool(s, contenu)) > 0:
            return True
    return False
```
Par exemple, avec le contenu de la question 3 :

est_infecte(contenu, [’E8FFFF’, ’4D5A90’]) renvoie True ;

est_infecte(contenu, [’E8FFFF’]) renvoie False.
Chaque appel à horspool reconstruit la table : la table d’une signature est donc construite jusqu’à \(100\,000\) fois (une fois par fichier analysé), alors qu’elle ne dépend que de la signature. Il suffit de construire une seule fois, avant l’analyse, un dictionnaire qui associe à chaque signature sa table de décalage (\(1\,000\) constructions en tout), puis d’utiliser une version de horspool qui reçoit la table en paramètre au lieu de la recalculer. On dépense un peu de mémoire pour gagner du temps.
Oui, c’est plausible : la table d’une signature longue autorise des décalages plus grands (jusqu’à \(m\) quand la lettre de fin de fenêtre est absente du motif). En pratique, Horspool teste de l’ordre de \(n / m\) alignements : plus \(m\) est grand, moins il y a d’alignements, et la recherche est plus rapide (au pire des cas, le coût reste toutefois en \(O(n \times m)\)).

★★★ Exercice 14 — Type bac — Repérer des amorces dans un brin d’ADN (sujet maison, façon bac) #

≈ 45 min

En biologie moléculaire, une amorce est une courte séquence d’ADN qui ne peut se fixer sur un brin qu’à l’endroit où elle apparaît telle quelle. Avant une expérience, un laboratoire vérifie par programme où ses amorces apparaissent dans un brin. Un brin et une amorce sont représentés par des chaînes de caractères sur l’alphabet {A, C, G, T}. Dans tout l’exercice, brin = ’CATGGATGCATGCC’ (\(14\) caractères) et l’on cherche l’amorce ’TGCATG’.

Partie A — Boyer-Moore (règle du mauvais caractère)

On donne les fonctions suivantes :

def table_dernier(motif):
    last = {}
    for k in range(len(motif)):
        last[motif[k]] = k
    return last

def boyer_moore(motif, texte):
    n, m = len(texte), len(motif)
    last = table_dernier(motif)
    positions = []
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and texte[i + j] == motif[j]:
            j -= 1
        if j < 0:
            positions.append(i)
            i += 1
        else:
            c = texte[i + j]
            if c in last:
                k = last[c]
            else:
                k = -1
            i += max(1, j - k)
    return positions

Donner le dictionnaire renvoyé par table_dernier(’TGCATG’).
Dérouler boyer_moore(’TGCATG’, brin) : pour chaque position \(i\) testée, donner la fenêtre du brin, l’indice \(j\) et le caractère c qui provoquent l’échec (ou « trouvé »), et le décalage appliqué. Quelle valeur la fonction renvoie-t-elle ?

Coup de pouce

Q2 : commencer à \(i=0\) : comparer brin[5] et motif[5], puis reculer tant que les lettres coïncident ; le décalage vient de la ligne i += max(1, ...).
Lors de ce déroulé, la quantité j - k a été négative. À quelle position \(i\) ? Que se passerait-il si l’on remplaçait max(1, j - k) par j - k ?

Coup de pouce

Q3 : chercher l’étape où la dernière occurrence de c dans le motif est à droite de l’indice \(j\).

Partie B — Boyer-Moore-Horspool

Construire la table de décalage de Horspool de l’amorce ’TGCATG’ (préciser le décalage par défaut).
Dérouler l’algorithme de Horspool sur le même brin (position \(i\), fenêtre, lettre de fin de fenêtre, décalage). Comparer le nombre d’alignements testés par les deux algorithmes sur cet exemple.

Partie C — Programmer

▶ Écrire une fonction cherche_amorces(amorces, brin) qui prend une liste d’amorces et un brin, et renvoie un dictionnaire associant à chaque amorce la liste de ses positions dans le brin (on utilisera la fonction horspool du cours). Par exemple, cherche_amorces([’TGCATG’, ’GGA’, ’AAAA’], brin) renvoie {’TGCATG’: [6], ’GGA’: [3], ’AAAA’: []}.

Coup de pouce 2 (début de solution)

Q6 :
def cherche_amorces(amorces, brin):
resultat = {}
for amorce in amorces:
▶ En utilisant cherche_amorces, écrire une fonction amorces_absentes(amorces, brin) qui renvoie la liste des amorces qui n’apparaissent pas dans le brin.
Un génome humain compte environ \(3\) milliards de bases et une amorce environ \(20\) bases. Donner l’ordre de grandeur du nombre d’alignements testés par la méthode naïve, puis par Horspool dans un cas favorable où chaque saut vaut la longueur de l’amorce.

Corrigé

Barème indicatif (sur 6) : Q1 : 0,5 ; Q2 : 1 ; Q3 : 0,75 ; Q4 : 0,5 ; Q5 : 1 ; Q6 : 1 ; Q7 : 0,5 ; Q8 : 0,75

Partie A

TGCATG = T0 G1 C2 A3 T4 G5 : table_dernier renvoie {’T’: 4, ’G’: 5, ’C’: 2, ’A’: 3}.

Déroulé (le brin est C0 A1 T2 G3 G4 A5 T6 G7 C8 A9 T10 G11 C12 C13) :

position \(i\)	fenêtre	échec / trouvé	décalage
\(i=0\)	`CATGGA`	échec en \(j=5\), `c = A`	\(\max(1, 5-3) = 2\)
\(i=2\)	`TGGATG`	échec en \(j=2\), `c = G`	\(\max(1, 2-5) = 1\)
\(i=3\)	`GGATGC`	échec en \(j=5\), `c = C`	\(\max(1, 5-2) = 3\)
\(i=6\)	`TGCATG`	trouvé	\(1\)
\(i=7\)	`GCATGC`	échec en \(j=5\), `c = C`	\(3\) (dépasse la fin)

La fonction renvoie [6] (5 alignements testés).

En \(i = 2\) : le caractère fautif G a sa dernière position (\(5\)) à droite de l’échec (\(j = 2\)), donc j - last[’G’] \(= -3\). Sans le max(1, ...), on ajouterait \(-3\) à \(i\) : le motif reculerait en \(i = -1\). Sur cet exemple, \(i\) prend ensuite les valeurs \(-2\), \(-3\), \(-2\), \(-3\)… (en Python, un indice négatif lit le texte depuis la fin) : le programme boucle sans fin. Le max garantit qu’on avance toujours d’au moins un cran, donc que l’algorithme termine.

Partie B

Lettres sauf la dernière (T0 G1 C2 A3 T4) : T\(\to 1\), G\(\to 4\), C\(\to 3\), A\(\to 2\), défaut 6.
Déroulé de Horspool :

position \(i\) fenêtre lettre de fin décalage

\(i=0\) CATGGA A \(2\)

\(i=2\) TGGATG G (échec en \(j=2\)) \(4\)

\(i=6\) TGCATG G (trouvé) \(4\) (dépasse la fin)

Horspool trouve l’amorce en position \(6\) avec 3 alignements, contre 5 pour Boyer-Moore (règle du mauvais caractère seule). En \(i = 2\), Boyer-Moore ne peut avancer que d’un cran (question 3), alors que Horspool, qui regarde toujours la lettre de fin de fenêtre, saute de \(4\). Ce n’est pas une règle générale : les deux algorithmes sont aussi rapides en pratique.

Partie C

On range la liste des positions de chaque amorce dans le dictionnaire :

def cherche_amorces(amorces, brin):
    resultat = {}
    for a in amorces:
        resultat[a] = horspool(a, brin)
    return resultat

On réutilise le dictionnaire renvoyé par cherche_amorces, et on construit par compréhension la liste des amorces qui n’ont aucune occurrence :

def amorces_absentes(amorces, brin):
    occurrences = cherche_amorces(amorces, brin)
    return [a for a in amorces if len(occurrences[a]) == 0]

amorces_absentes([’TGCATG’, ’GGA’, ’AAAA’], brin) renvoie [’AAAA’].

Autre méthode : une boucle qui ajoute à la liste chaque amorce absente.

def amorces_absentes(amorces, brin):
    absentes = []
    occurrences = cherche_amorces(amorces, brin)
    for a in amorces:
        if len(occurrences[a]) == 0:
            absentes.append(a)
    return absentes

Méthode naïve : \(n - m + 1 \approx 3 \times 10^9\) alignements (3 milliards). Horspool, si chaque saut vaut \(m = 20\) : environ \(n / m = 3 \times 10^9 / 20 = 1{,}5 \times 10^8\) alignements (150 millions), soit vingt fois moins.

Critiquer une réponse d’IA#

★★ Exercice 15 — Une table de décalage construite par un assistant d’IA #

Un élève demande à un assistant d’IA : « Écris en Python la fonction table_decalage(motif) de l’algorithme de Horspool, puis la fonction horspool(motif, texte) qui renvoie la position de la première occurrence (ou -1). » Voici la réponse obtenue :

def table_decalage(motif):
    m = len(motif)
    dec = {}
    for k in range(m):               # chaque lettre du motif
        dec[motif[k]] = m - 1 - k    # distance a la fin du motif
    return dec

def horspool(motif, texte):
    n, m = len(texte), len(motif)
    dec = table_decalage(motif)
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and texte[i + j] == motif[j]:
            j -= 1                   # comparaison droite -> gauche
        if j < 0:
            return i                 # motif trouve en i
        c = texte[i + m - 1]         # lettre de fin de fenetre
        if c in dec:
            i += dec[c]
        else:
            i += m
    return -1

« La table donne, pour chaque lettre du motif, sa distance à la fin ; une lettre absente vaut m. La recherche compare de droite à gauche et saute selon la lettre alignée avec la fin de la fenêtre. »

La réponse est-elle correcte ? Construire la table pour ANANAS, puis dérouler horspool("ANANAS", "ANANES ANANAS") : noter \(i\), la lettre de fin de fenêtre et le décalage à chaque étape.
Localiser et corriger l’erreur.

Coup de pouce

Comparer la boucle de table_decalage avec celle du cours : quelles lettres sont parcourues ? Quelle valeur reçoit alors la dernière lettre ?
Quelle vérification simple, faite avant de faire confiance à la réponse, aurait suffi à détecter l’erreur ?

Corrigé

Non. La table obtenue est {’A’: 1, ’N’: 2, ’S’: 0} : la dernière lettre S reçoit le décalage \(0\). Déroulé : \(i = 0\), fenêtre ANANES, comparaison de droite à gauche : S = S, puis E\(\neq\)A ; la lettre de fin de fenêtre est S, décalage dec[’S’] = 0, donc \(i\) reste à \(0\)… et la même fenêtre est examinée indéfiniment : le programme boucle sans fin (sortie réelle : aucune, il faut l’interrompre).
L’erreur : la dernière lettre du motif ne doit pas figurer dans la table (cours : « on parcourt ses lettres sauf la dernière »), sinon son décalage vaut \(0\). Ligne corrigée :
```
    for k in range(m - 1):           # on ignore la DERNIERE lettre
```
La table devient {’A’: 1, ’N’: 2} (S absent, donc décalage \(6\)). Déroulé corrigé : \(i = 0\) (fin de fenêtre S \(\to\) saut \(6\)), \(i = 6\) (fenêtre « espace + ANANA », fin A \(\to\) saut \(1\)), \(i = 7\) : ANANAS trouvé. La fonction renvoie 7.
Regarder la table produite : un décalage de \(0\) est toujours une erreur (on n’avancerait jamais). Plus généralement, vérifier qu’un algorithme de recherche termine sur un texte où le motif est absent ou précédé d’une fausse piste.

S’entraîner à l’oral#

★★ Exercice 16 — Expliquer en deux minutes #

Au Grand Oral comme devant l’examinateur de l’épreuve pratique, il faut savoir expliquer une notion clairement, sans lire ses notes. Choisir l’un des sujets suivants (ou le tirer au sort) :

Expliquer à un camarade de Première la recherche naïve d’un motif dans un texte et son coût.
Expliquer l’idée de Boyer-Moore-Horspool : pourquoi comparer en partant de la fin du motif permet de sauter des positions.
Expliquer pourquoi Boyer-Moore-Horspool est d’autant plus rapide que le motif est long, et dans quel cas il ne gagne rien.

Préparation (5 min, seul). Noter au brouillon trois idées et un exemple, rien de plus : comme au Grand Oral, ces notes servent d’aide-mémoire. Exposé (2 min, chronométré). Debout, face à un camarade, sans lire ses notes et sans rien écrire : tout passe par la parole. Retour (2 min). Le camarade pose une question de relance (on peut alors s’aider d’un schéma), remplit la grille ci-dessous et donne un conseil ; puis on échange les rôles. Cette grille reprend les critères d’évaluation du Grand Oral.

Coup de pouce

Structurer chaque explication en trois temps : une définition en une phrase, un exemple petit et concret déroulé à voix haute, puis le piège (l’erreur que l’auditeur risque de faire). Finir par une phrase qui répond à la question posée. Prévoir un motif court (quatre lettres) et un texte d’une ligne, que l’on fait « glisser » à voix haute. Sujet 2 : quel caractère du texte regarde-t-on pour décider du saut ?

Grille entre camarades	Oui	En partie	Pas encore
Clair — audible, posé ; chaque mot technique est expliqué	▫	▫	▫
Juste — c’est exact, et l’exemple montre vraiment l’idée	▫	▫	▫
Construit — un fil conducteur, tenu en deux minutes, sans lire	▫	▫	▫
Un conseil pour la prochaine fois :

Corrigé

Pas de texte à apprendre par cœur : voici les éléments attendus pour chaque sujet. L’ordre, les mots et l’exemple peuvent être différents ; l’explication est réussie si ces idées y sont, justes et reliées entre elles.

Sujet 1.

On place le motif (de longueur \(m\)) à chaque position du texte (de longueur \(n\)) et on compare caractère par caractère : une fenêtre glissante qui avance d’un cran.
Exemple : chercher NSI dans LES NSI : positions \(0, 1, 2, 3\) échouent dès la première lettre, la position \(4\) réussit.
Coût dans le pire cas : de l’ordre de \(n \times m\) comparaisons (texte AAAA…A, motif AAB).
Piège : les bornes ; la dernière position possible est \(n - m\).

Sujet 2.

On compare le motif au texte en partant de la fin du motif.
Une table de décalage est préparée à l’avance : pour chaque caractère du motif (sauf le dernier), la distance entre sa dernière apparition et la fin du motif ; pour un caractère absent, la longueur du motif.
En cas d’échec, on décale selon le caractère du texte aligné avec la fin du motif ; s’il n’apparaît pas dans le motif, on saute de \(m\) positions d’un coup.
Exemple : motif CHAT : décalages C \(\to 3\), H \(\to 2\), A \(\to 1\), tout autre caractère \(\to 4\).

Sujet 3.

Chaque saut de \(m\) positions évite de lire des caractères du texte : on en lit souvent bien moins que \(n\) (coût sous-linéaire, de l’ordre de \(n/m\) dans le meilleur cas).
Exemple : un motif de dix lettres rares dans un texte en français avance le plus souvent de dix positions à la fois.
Pire cas : petit alphabet et nombreuses répétitions (ADN, AAAA…) ; les décalages valent \(1\), et l’on retrouve le coût de la méthode naïve.
On paie un peu de mémoire (la table) pour gagner beaucoup de temps ; usages : « Rechercher » d’un éditeur, antivirus, bio-informatique.

Entraînement#

Des séries courtes pour rendre une méthode automatique : même consigne, données différentes. Les réponses sont brèves dans le corrigé.

★ Exercice 17 — Tables de décalage en série #

• essentiel

Construire la table de décalage de Horspool de chacun des motifs suivants, en précisant le décalage par défaut.

Coup de pouce

Écrire la position de chaque lettre sous le motif. Parcourir les lettres de gauche à droite sauf la dernière : la lettre en position \(k\) reçoit \(m - 1 - k\), et une lettre qui revient voit sa valeur remplacée. Toute lettre absente de la table reçoit \(m\).

CHAT
MAMAN
RADAR
BONBON

Corrigé

CHAT (\(m=4\)) : C\(\to 3\), H\(\to 2\), A\(\to 1\), défaut 4.
MAMAN (\(m=5\)) : M\(\to 2\), A\(\to 1\), défaut 5 (M en position \(2\) et A en position \(3\) remplacent leurs valeurs précédentes).
RADAR (\(m=5\)) : R\(\to 4\), A\(\to 1\), D\(\to 2\), défaut 5 (le R final est ignoré, seul compte celui de la position \(0\)).
BONBON (\(m=6\)) : B\(\to 2\), O\(\to 1\), N\(\to 3\), défaut 6.

▷ Erreur fréquente. En c), donner à R le décalage \(0\) à cause du R final : la dernière case du motif est ignorée. R garde la valeur de sa position \(0\), soit \(5 - 1 - 0 = 4\).

★ Exercice 18 — Horspool à la main en série #

• essentiel

Pour chaque recherche, construire la table de décalage du motif, puis dérouler l’algorithme de Horspool : à chaque étape, donner la position \(i\), la fenêtre, la lettre de fin de fenêtre et le décalage. Donner enfin les positions des occurrences.

Coup de pouce

La lettre de fin de fenêtre est la lettre du texte en position \(i + m - 1\). On compare la fenêtre au motif de droite à gauche, puis, trouvé ou non, on décale de la valeur que la table donne pour la lettre de fin. On s’arrête quand la fenêtre dépasse la fin du texte.

motif TAC, texte TICTACTOC
motif GAG, texte TGAGCGAGT
motif CODE, texte DECODERLECODE

Corrigé

a) Table de TAC : T\(\to 2\), A\(\to 1\), défaut \(3\).

position \(i\)	fenêtre	lettre de fin	décalage
\(i=0\)	`TIC`	`C`	\(3\)
\(i=3\)	`TAC`	`C` (trouvé)	\(3\)
\(i=6\)	`TOC`	`C`	\(3\) (dépasse la fin)

Occurrence en position 3.

b) Table de GAG : G\(\to 2\), A\(\to 1\), défaut \(3\).

position \(i\)	fenêtre	lettre de fin	décalage
\(i=0\)	`TGA`	`A`	\(1\)
\(i=1\)	`GAG`	`G` (trouvé)	\(2\)
\(i=3\)	`GCG`	`G`	\(2\)
\(i=5\)	`GAG`	`G` (trouvé)	\(2\) (dépasse la fin)

Occurrences en positions 1 et 5.

c) Table de CODE : C\(\to 3\), O\(\to 2\), D\(\to 1\), défaut \(4\).

position \(i\)	fenêtre	lettre de fin	décalage
\(i=0\)	`DECO`	`O`	\(2\)
\(i=2\)	`CODE`	`E` (trouvé)	\(4\)
\(i=6\)	`RLEC`	`C`	\(3\)
\(i=9\)	`CODE`	`E` (trouvé)	\(4\) (dépasse la fin)

Occurrences en positions 2 et 9.

\(i\)	fenêtre	lettre de fin	décalage
\(0\)	`GTAGATT`	`T`	\(3\)
\(3\)	`GATTACA`	`A` (trouvé)	\(2\)
\(5\)	`TTACAGT`	`T`	\(3\) (dépasse la fin)