Recherche textuelle et Boyer-Moore : exercices de Terminale NSI

On enlève la dernière lettre du motif : il reste CART.

Dans CART, les indices sont C : 0, A : 1, R : 2, T : 3. La lettre R est donc à l'indice $k=2$.

On applique la formule : $d(\text{R})=m-1-k=5-1-2=2$.

Contrôle : R est à deux lettres de la fin du motif CARTE (R, T, E), donc on décale de 2 pour amener ce R sous la lettre du texte qui vient d'être lue.

On a $m=3$. La lettre X n'est pas dans AB, donc $d(\text{X})=3$.

À l'alignement 0, on compare la dernière lettre du motif, C, avec X : échec, une comparaison. On décale de 3.

Les alignements testés sont 0, 3, 6 et 9. L'alignement 12 ne convient pas car $12+3>12$.

Chaque alignement coûte une seule comparaison, donc le total est $4\times 1=4$.

Pour comparer, la méthode naïve teste les $12-3+1=10$ alignements avec une comparaison chacun, soit 10 comparaisons.

Table : $m=3$. Dans AN, $d(\text{A})=3-1-0=2$ et $d(\text{N})=3-1-1=1$. Toute autre lettre donne 3.

Alignement 0 : le motif est sous BAN. On compare le dernier A du motif à N du texte : échec, 1 comparaison. La lettre lue est N, on décale de 1.

Alignement 1 : le motif est sous ANA. On compare de droite à gauche : A=A, N=N, A=A. Trois comparaisons, occurrence trouvée à l'indice 1. La lettre lue sous la fin du motif est A, on décale de 2.

Alignement 3 : le motif est sous ANA. Trois nouvelles comparaisons réussies, occurrence à l'indice 3. Le décalage suivant sortirait du texte, on s'arrête.

Total : $1+3+3=7$ comparaisons, avec deux occurrences aux indices 1 et 3.

Alignement 0 : B contre A, échec. 1 comparaison.

Alignement 1 : A=A, N=N, A=A. 3 comparaisons, occurrence.

Alignement 2 : N contre A, échec. 1 comparaison.

Alignement 3 : A=A, N=N, A=A. 3 comparaisons, occurrence.

Total : $1+3+1+3=8$ comparaisons, contre 7 pour Horspool.

On écrit la fonction :

def table_decalage(motif):
    m = len(motif)
    table = {}
    for k in range(m - 1):
        table[motif[k]] = m - 1 - k
    return table

La boucle range(m - 1) va de 0 à $m-2$ : le dernier caractère est exclu.

Comme on parcourt de gauche à droite, une lettre qui réapparaît voit sa valeur remplacée par une valeur plus petite, ce qui correspond à sa dernière occurrence.

Pour BANANE, $m=6$ : B (indice 0) donne 5, A (indice 1) donne 4 puis A (indice 3) donne 2, N (indice 2) donne 3 puis N (indice 4) donne 1. Le dictionnaire final est {'B': 5, 'A': 2, 'N': 1}.

Le dernier caractère est exclu car son décalage serait $m-1-(m-1)=0$ : le motif ne bougerait plus et la recherche bouclerait indéfiniment. Les lettres absentes, y compris E quand elle n'apparaît qu'en dernière position, ont le décalage 6, que l'on obtient avec table.get(c, m).

Le motif privé de sa dernière lettre est ABRACADABR, avec A : 0, B : 1, R : 2, A : 3, C : 4, A : 5, D : 6, A : 7, B : 8, R : 9.

Dernières occurrences : A à l'indice 7, B à l'indice 8, C à l'indice 4, D à l'indice 6, R à l'indice 9.

Décalages avec $d=m-1-k=10-k$ : $d(\text{A})=3$, $d(\text{B})=2$, $d(\text{C})=6$, $d(\text{D})=4$, $d(\text{R})=1$.

Somme : $3+2+6+4+1=16$.

Le nombre d'alignements est $n-m+1=1000-10+1=991$.

À chaque alignement, les 9 premières lettres A du motif correspondent au texte. L'échec n'a lieu qu'à la dixième comparaison, entre B et A.

Chaque alignement coûte donc 10 comparaisons.

Total : $991\times 10=9910$ comparaisons.

Ce cas est défavorable parce que l'on ne détecte l'échec qu'à la dernière lettre : toutes les comparaisons précédentes ont été « gaspillées ».

Un alignement $i$ est possible si $i+m\leq n$, soit $i\leq 9992$.

Les alignements testés forment la suite $0, 8, 16, \dots$ jusqu'à $8q\leq 9992$, donc $q\leq 1249$.

Il y a donc $1249+1=1250$ alignements, en comptant l'alignement 0.

Chaque alignement fait une unique comparaison (celle de la dernière lettre du motif, qui échoue), donc 1250 comparaisons au total.

En comparaison, un parcours naïf testerait $10000-8+1=9993$ alignements.