Exercices : recherche textuelle

Exercice 0. QCM d’activation

Pour chaque question, une seule réponse est correcte.

Question 1. L’algorithme naïf de recherche textuelle compare le motif de longueur $m$ dans un texte de longueur $n$. Sa complexité dans le pire cas est :

• A) $O(n)$
• B) $O(n \times m)$
• C) $O(n + m)$
• D) $O(m \log n)$

Correction publiée après la séance.

Exercice 0. QCM d’activation (suite)

Question 2. L’algorithme de Boyer-Moore améliore la recherche en :

• A) comparant le motif de gauche à droite comme l’algorithme naïf
• B) comparant le motif de droite à gauche et en sautant des positions grâce à des tables de décalage
• C) triant le texte avant la recherche
• D) utilisant la programmation dynamique

Correction publiée après la séance.

Question 3. Dans la table de décalages de Boyer-Moore-Horspool pour le motif "ABCD", quelle est la valeur associée à la lettre B ?

Exercice 0. QCM d’activation (suite)

• A) 0
• B) 1
• C) 2
• D) 3

Correction publiée après la séance.

Question 4. On recherche le motif "abc" dans le texte "ababcabc". L’algorithme naïf trouve le motif aux positions :

• A) 2 uniquement
• B) 2 et 5
• C) 0 et 5
• D) 0, 2 et 5

Correction publiée après la séance.

Exercice 0. QCM d’activation (suite)

Question 5. L’algorithme de Boyer-Moore est particulièrement efficace quand :

• A) le motif est très court (un ou deux caractères)
• B) l’alphabet est grand et le motif est long
• C) le texte et le motif sont identiques
• D) le motif ne contient que des caractères identiques

Correction publiée après la séance.

Exercice 1 – Déroulé à la main de l’algorithme naïf

On considère texte = 'abracadabra' et motif = 'abr'.

1. Recopier le tableau ci-dessous et le compléter en indiquant, pour chaque position i, les comparaisons effectuées et le résultat (« échec à j = ... » ou « trouvé ») :

Exercice 1 – Déroulé à la main de l’algorithme naïf (suite)

2. Combien de comparaisons au total l’algorithme naïf effectue-t-il ?

   Indice

   Additionner les comparaisons de toutes les lignes du tableau.

3. À quelles positions le motif est-il trouvé ?

   Indice

   Relever les lignes marquées « trouvé ».

Correction publiée après la séance.

Exercice 2 – Table de décalages

1. Calculer la table de décalages pour le motif 'algorithme' (longueur 10).

   Indice

   Pour chaque caractère du motif sauf le dernier, le décalage vaut m - 1 - i, où i est la position de sa dernière apparition avant la fin du motif : un caractère présent plusieurs fois garde le plus petit décalage.

2. Quel est le décalage si le caractère du texte est 'x' (absent du motif) ?

   Indice

   Que fait l’algorithme du cours quand le caractère ne figure pas dans la table ?

Exercice 2 – Table de décalages (suite)

3. Quel est le décalage si le caractère du texte est 'a' ?

   Indice

   Lire la valeur associée à 'a' dans la table de la question 1.

4. Quel est le décalage si le caractère du texte est 'e' (dernier caractère du motif, absent ailleurs) ?

   Indice

   Le dernier caractère du motif n’entre pas dans la table : 'e' est-il alors traité comme un caractère absent ?

Correction publiée après la séance.

Exercice 3 – Déroulé de Boyer-Moore-Horspool

On cherche le motif 'man' dans le texte 'le management est un art'.

Exercice 3 – Déroulé de Boyer-Moore-Horspool (suite)

1. Calculer la table de décalages du motif.

   Indice

   Même méthode qu’à l’exercice 2, avec m = 3.

2. Dérouler l’algorithme étape par étape en indiquant à chaque fois la position i, le caractère comparé, le décalage appliqué.

   Indice

   À chaque étape, comparer le motif au texte de droite à gauche, en partant de la position i + m - 1 ; en cas d’échec, lire le caractère du texte aligné avec la fin du motif et décaler du nombre donné par la table, ou de m s’il n’y figure pas.

3. Combien d’étapes sont nécessaires ? Combien l’algorithme naïf aurait-il testé de positions ?

   Indice

   L’algorithme naïf teste toutes les positions de 0 à n − m : compter n et m.

Exercice 3 – Déroulé de Boyer-Moore-Horspool (suite)

Correction publiée après la séance.

Exercice 4 – Compteur de comparaisons

Modifier la fonction algo_naif pour qu’elle renvoie, en plus de la liste des indices, le nombre total de comparaisons effectuées.

Faire de même pour recherche_boyer_moore.

Comparer les deux compteurs pour la recherche de 'abd' dans 'abracadabra'.

def algo_naif(texte, motif):
    n = len(texte)
    m = len(motif)
    indices = []
    nb_comp = 0
    for i in range(n - m + 1):
        trouve = True
        for j in range(m):
            nb_comp = ...
            if texte[i + j] != motif[j]:
                trouve = False
                break
        if trouve:
            indices.append(i)
    return indices, ...

Exercice 4 – Compteur de comparaisons (suite)

Correction publiée après la séance.

Exercice 5 – Comparaison expérimentale avec timeit

1. Créer une variable texte contenant un texte long (par exemple en lisant un fichier avec open('fichier.txt').read(), ou en utilisant texte = 'a' * 100000).

2. Choisir un motif de quelques caractères.

3. Utiliser le module timeit pour mesurer le temps d’exécution des deux algorithmes.

   Indice

   timeit.timeit(lambda: algo_naif(texte, motif), number=10) renvoie la durée totale de 10 exécutions, en secondes.

4. Tester avec un motif plus long (par exemple 10 caractères). Le rapport de vitesse change-t-il ?

   Indice

   Calculer, pour chaque motif, le quotient des deux durées, puis comparer ces quotients : Boyer-Moore-Horspool décale-t-il plus loin quand le motif est long ?

Exercice 5 – Comparaison expérimentale avec timeit (suite)

Correction publiée après la séance.

Exercice 6 – Remplacement du slice par une boucle

Dans la version suivante de recherche_boyer_moore, la comparaison complète du motif est faite avec un slice Python (texte[i:i+m] == motif), ce qui est moins fidèle à l’esprit de l’algorithme.

# Version avec slice (à remplacer)
if texte[i + j] == motif[j]:  # dernier caractère OK
    if texte[i:i + m] == motif:
        indices.append(i)

Exercice 6 – Remplacement du slice par une boucle (suite)

Réécrire cette partie avec une boucle while qui compare les caractères de droite à gauche, un par un, et qui s’arrête dès qu’un caractère ne correspond pas.

Correction publiée après la séance.

Exercice 7 – Cas limites

Écrire des assertions pour tester les cas suivants, puis vérifier qu’elles passent pour les deux algorithmes :

1. Le motif est égal au texte entier.
2. Le motif est plus long que le texte.
3. Le texte est vide.
4. Le motif apparaît plusieurs fois et ces occurrences se chevauchent (par exemple 'aa' dans 'aaaa').
5. Le motif n’apparaît pas du tout.

Correction publiée après la séance.

Exercice 8 – Pire cas de l’algorithme naïf

1. Construire un texte de longueur 1000 et un motif de longueur 10 qui provoquent le pire cas de l’algorithme naïf (un maximum de comparaisons).

   Indice

   Le pire cas survient quand, à chaque position, presque tous les caractères du motif correspondent avant l’échec : quel texte et quel motif, faits presque uniquement de la même lettre, produisent cela ?

Exercice 8 – Pire cas de l’algorithme naïf (suite)

2. Vérifier avec le compteur de comparaisons (exercice 4) que le nombre de comparaisons est bien proche de \(n \times m\).

   Indice

   Appeler la version avec compteur de l’exercice 4 sur ce texte et ce motif, et comparer le nombre obtenu à 1000 × 10.

3. Tester le même cas avec Boyer-Moore-Horspool. L’algorithme est-il plus rapide ici ?

   Indice

   Compter aussi les comparaisons de recherche_boyer_moore sur le même cas : de combien la table de décalages fait-elle avancer la fenêtre à chaque échec ?

Correction publiée après la séance.