Terminale NSI — Recherche textuelle

Séance 2 — Boyer-Moore-Horspool

Le décalage intelligent · 2h

1. Les limites de l'algorithme naïf

L'algorithme naïf décale toujours d'un seul caractère à chaque échec. Boyer-Moore-Horspool améliore cela avec deux idées :

2. Exercice 1 — Table de décalage : « banane »

Pour chaque caractère du motif (sauf le dernier), à l'indice i, le décalage associé est m - 1 - i. En cas de répétition, on garde le décalage de la dernière occurrence.

motif = "banane"   (m = 6, indices 0 à 5 : b-a-n-a-n-e)

a) Indice et décalage pour chaque caractère (hors dernier). b) Cas du « a » répété. c) Cas du « n » répété. d) Décalage pour un caractère absent du motif ?

Voir la réponse
b (0) → 5 ; a (1) → écrasé par a (3) → 2 ; n (2) → écrasé par n (4) → 1.
Table finale : {b: 5, a: 2, n: 1} — tout autre caractère (absent du motif, ex. « z ») : décalage m = 6 (on peut sauter toute la longueur du motif).

3. Exercice 2 — Table de décalage : « chercher »

Même méthode sur le motif « chercher » (attention aux lettres répétées c, h, e, r).

Voir la réponse
c: indices 0,4 → garde 4 → décalage 3. h: indices 1,5 → garde 5 → décalage 2. e: indices 2,6 → garde 6 → décalage 1. r: indice 3 → décalage 4.
Table finale : {c: 3, h: 2, e: 1, r: 4} — autres caractères : décalage 8.

4. Exercice 3 — Dérouler l'algorithme à la main

Avec la table de l'exercice 2, déroule la recherche de « chercher » dans « chercher, rechercher et chercher encore ». Compte les comparaisons et compare au résultat naïf (54).

Voir la réponse
Position 0 : 8 comparaisons, occurrence trouvée. Position 1 : échec immédiat sur l'espace (absent de la table) → décalage de 8. On progresse ainsi, avec un total d'environ une vingtaine de comparaisons, contre 54 pour l'algorithme naïf — un net gain grâce aux sauts de plusieurs caractères.

5. Exercice 4 — Implémentation Python

NO_CAR = 256

def recherche_boyer_moore(txt, motif):
    m = len(motif)
    n = len(txt)
    tab_car = [m] * NO_CAR
    for i in range(m - 1):
        tab_car[ord(motif[i])] = m - 1 - i

    decalage = 0
    res = []
    while decalage <= n - m:
        j = m - 1
        while j >= 0 and motif[j] == txt[decalage + j]:
            j = j - 1
        if j < 0:
            res.append(decalage)
            decalage += 1
        else:
            decalage += tab_car[ord(txt[decalage + j])]
    return res

a) Vérifie que tab_car correspond à tes calculs manuels. b) Teste sur l'exemple de l'exercice 3. c) Ajoute un compteur de comparaisons.

Voir la réponse
nb_comparaisons = 0
while j >= 0 and motif[j] == txt[decalage + j]:
    nb_comparaisons += 1
    j = j - 1
if j >= 0:
    nb_comparaisons += 1   # la comparaison qui a échoué compte aussi

6. Exercice 5 — Comparaison expérimentale

a) Sur un motif court et fréquent, lequel est le plus rapide ? b) Sur un motif long et rare ?

Voir la réponse
Motif court et fréquent : le gain de BMH est souvent modeste. Motif long et rare : BMH est généralement bien plus rapide, car les décalages potentiels sont plus grands.

Exercices défis (bonus)

Défi — Le pire des cas défi

Trouve un texte/motif où Boyer-Moore-Horspool ne fait pas mieux que l'algorithme naïf.

Voir la réponse
texte = "a" * 1000
motif = "a" * 20
# tous les caractères identiques : la table ne permet quasiment aucun saut utile
Défi — Boyer-Moore complet (hors attendus stricts) défi

Version où le décalage dépend aussi de la position j dans le motif, pas seulement du caractère fautif.

def table_bm(m):
    d = [{} for _ in range(len(m))]
    for j in range(len(m)):
        for k in range(j):
            d[j][m[k]] = k
    return d

def decalage(d, j, c):
    if c in d[j]:
        return j - d[j][c]
    else:
        return j + 1
Voir la réponse
Le décalage dépend à la fois du caractère fautif ET de la position j où l'échec se produit, permettant des sauts encore plus précis, au prix d'un prétraitement plus coûteux (un dictionnaire par position du motif).