Exercices : recherche textuelle

Réponse B. Pour chaque position du texte (au plus $n - m + 1$ positions), on compare jusqu’à $m$ caractères. Dans le pire cas (par exemple, texte "aaaaaa" et motif "aab"), on effectue $O(n \times m)$ comparaisons.

• A est faux : cela supposerait une seule comparaison par position ;
• C est faux : c’est la complexité de certains algorithmes optimisés, pas de l’algorithme naïf ;
• D est faux : aucun mécanisme de dichotomie n’intervient dans l’algorithme naïf.

Réponse B. Boyer-Moore compare le motif de droite à gauche. En cas d’échec, il utilise une table de décalage (basée sur le « mauvais caractère ») pour sauter plusieurs positions, évitant des comparaisons inutiles.

• A est faux : la comparaison de droite à gauche est justement ce qui distingue Boyer-Moore ;
• C est faux : on ne trie pas le texte ;
• D est faux : Boyer-Moore n’utilise pas la programmation dynamique.

Réponse C. La valeur associée à un caractère est la distance entre sa dernière occurrence dans le motif (hors dernier caractère) et la fin du motif. Pour "ABCD" : B est en position 1 (en partant de 0), la longueur est 4, donc le décalage est $4 - 1 - 1 = 2$.

• A est faux : aucune lettre du motif n’a un décalage nul ;
• B est faux : c’est le décalage de C ;
• D est faux : c’est le décalage de A (position 0, décalage $4 - 0 - 1 = 3$).

Réponse B. Vérifions chaque position :

• Position 0 : "aba" ≠ "abc" (échec au 3e caractère).
• Position 1 : "bab" ≠ "abc" (échec au 1er caractère).
• Position 2 : "abc" = "abc" → trouvé.
• Position 3 : "bca" ≠ "abc" (échec au 1er caractère).
• Position 4 : "cab" ≠ "abc" (échec au 1er caractère).
• Position 5 : "abc" = "abc" → trouvé.

Le motif est trouvé aux positions 2 et 5.

Réponse B. Avec un grand alphabet (par exemple, l’alphabet latin complet), les caractères du texte qui ne figurent pas dans le motif permettent de sauter de grandes distances. Avec un motif long, ces sauts sont encore plus importants. Dans le meilleur cas, la complexité descend à $O(n/m)$.

• A est faux : avec un motif très court, les sauts sont minimes et Boyer-Moore n’apporte pas de gain significatif ;
• C est faux : si texte et motif sont identiques, aucun saut n’est possible ;
• D est faux : un motif avec des caractères identiques (comme "aaaa") limite les possibilités de saut.

Total : 3 + 1 + 1 + 2 + 1 + 2 + 1 + 3 + 1 = 15 comparaisons.

Le motif est trouvé aux positions 0 et 7.

Le motif est 'algorithme' de longueur 10. On parcourt les caractères du motif sauf le dernier ('algorithme' → 'algorithm').

Dictionnaire : {'a': 9, 'l': 8, 'g': 7, 'o': 6, 'r': 5, 'i': 4, 't': 3, 'h': 2, 'm': 1}.

2. 'x' est absent du motif, donc le décalage est de 10 (la longueur du motif).
3. 'a' est dans le dictionnaire avec un décalage de 9.
4. 'e' est le dernier caractère du motif et n’apparaît pas ailleurs. Il n’est pas dans le dictionnaire, donc le décalage est de 10.

1. Motif 'man', longueur 3. pre_traitement('man') :

   • position 0 : 'm' → décalage 2
   • position 1 : 'a' → décalage 1
   • Dictionnaire : {'m': 2, 'a': 1}

2. Le texte est 'le management est un art' (longueur 24). Indices : l(0) e(1) ␣(2) m(3) a(4) n(5) a(6) g(7) e(8) m(9) e(10) n(11) t(12) ␣(13) e(14) s(15) t(16) ␣(17) u(18) n(19) ␣(20) a(21) r(22) t(23).

   i = 0 : on compare texte[2] = ' ' avec 'n'. ' ' absent du dictionnaire → décalage 3.

   i = 3 : on compare texte[5] = 'n' avec 'n'. Match du dernier caractère ! On vérifie de droite à gauche : texte[4] = 'a' = 'a', texte[3] = 'm' = 'm'. Tous correspondent → trouvé à la position 3.

   La fonction du cours ne s’arrête pas là : elle poursuit jusqu’à la fin du texte pour repérer d’éventuelles autres occurrences, sans en trouver.

   3. Boyer-Moore-Horspool a trouvé l’occurrence à la deuxième fenêtre examinée (i = 0 puis i = 3). L’algorithme naïf aurait testé les positions 0, 1, 2 puis 3 avant de la trouver, soit 4 positions et 1 + 1 + 1 + 3 = 6 comparaisons ; pour parcourir tout le texte, il teste 22 positions et fait 25 comparaisons.

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


def recherche_bm_compteur(texte, motif):
    n = len(texte)
    m = len(motif)
    décalages = pre_traitement(motif)
    indices = []
    compteur = 0

    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0:
            compteur += 1
            if texte[i + j] != motif[j]:
                break
            j -= 1
        if j < 0:
            indices.append(i)
            i += 1
        else:
            c = texte[i + m - 1]
            if c in décalages:
                i += décalages[c]
            else:
                i += m
    return indices, compteur

Pour 'abd' dans 'abracadabra' :

• Naïf : indices = [], compteur = 14 (beaucoup de comparaisons 'a'='a', 'b'='b' avant d’échouer sur le troisième caractère).
• Boyer-Moore-Horspool : indices = [], compteur = 4 (grands décalages car les caractères ne correspondent pas souvent).

import timeit

texte = 'a' * 100000 + 'b'
motif_court = 'aab'
motif_long = 'baaaaaaaaa'

# Motif court
t1 = timeit.timeit(lambda: algo_naif(texte, motif_court), number=10)
t2 = timeit.timeit(lambda: recherche_boyer_moore(texte, motif_court), number=10)
print(f"Motif court – Naïf : {t1:.3f} s, Boyer-Moore : {t2:.3f} s")

# Motif long
t3 = timeit.timeit(lambda: algo_naif(texte, motif_long), number=10)
t4 = timeit.timeit(lambda: recherche_boyer_moore(texte, motif_long), number=10)
print(f"Motif long – Naïf : {t3:.3f} s, Boyer-Moore : {t4:.3f} s")

Avec motif_court = 'aab', Horspool ne décale que d’une case à chaque fenêtre ('a' est l’avant-dernier caractère du motif) mais ne compare qu’un caractère par fenêtre : il reste bien plus rapide que le naïf. Avec motif_long = 'baaaaaaaaa', on est dans le pire cas de Horspool : le décalage vaut 1 et chaque fenêtre est comparée en entier, les deux algorithmes font alors un nombre de comparaisons comparable (environ $n \times m$). En remplaçant le motif par 'aaaaaaaaab', Horspool redevient environ dix fois plus rapide que le naïf, une seule comparaison suffisant par fenêtre.

Pour un texte naturel (roman, article), Boyer-Moore est typiquement trois à cinq fois plus rapide.

j = m - 1
while j >= 0 and texte[i + j] == motif[j]:
    j -= 1
if j < 0:
    indices.append(i)

Cette boucle compare les caractères de droite à gauche (du dernier au premier). Si tous correspondent (j descend en dessous de 0), le motif est trouvé. Sinon, on sort de la boucle dès le premier caractère qui ne correspond pas, ce qui permet d’économiser des comparaisons inutiles.

C’est la version que l’on retrouve dans l’implémentation du cours.

# 1. Motif = texte entier
assert algo_naif("abc", "abc") == [0]
assert recherche_boyer_moore("abc", "abc") == [0]

# 2. Motif plus long que le texte
assert algo_naif("ab", "abc") == []
assert recherche_boyer_moore("ab", "abc") == []

# 3. Texte vide
assert algo_naif("", "a") == []
assert recherche_boyer_moore("", "a") == []

# 4. Occurrences chevauchantes
assert algo_naif("aaaa", "aa") == [0, 1, 2]
assert recherche_boyer_moore("aaaa", "aa") == [0, 1, 2]

# 5. Motif absent
assert algo_naif("abracadabra", "xyz") == []
assert recherche_boyer_moore("abracadabra", "xyz") == []

Ces tests vérifient que les deux algorithmes gèrent correctement les cas limites, sans erreur d’indice ni boucle infinie.

# Le pire cas : un texte composé uniquement de 'a'
# et un motif composé de 'a' sauf le dernier qui est 'b'
texte = 'a' * 1000
motif = 'a' * 9 + 'b'

indices_naif, c_naif = algo_naif_compteur(texte, motif)
indices_bm, c_bm = recherche_bm_compteur(texte, motif)

print(f"Naïf : {c_naif} comparaisons")
# Attendu : environ 991 × 10 = 9910
print(f"Boyer-Moore : {c_bm} comparaisons")

Le pire cas est identique pour les deux algorithmes quand l’alphabet est réduit : le décalage de Boyer-Moore-Horspool est toujours de 1 (car 'a' est en avant-dernière position dans le motif). Les deux algorithmes effectuent alors un nombre comparable de comparaisons.

C’est la limite de la version Horspool : sur un alphabet pauvre, elle ne fait pas mieux que l’algorithme naïf. L’algorithme de Boyer-Moore complet utilise une seconde heuristique (le «bon suffixe») pour gérer ce cas.