Bangoua-IT — Accueil
Écrire

Terminale • Algorithmique

Recherche textuelle : Algorithme de Boyer-Moore

Rechercher un motif dans un texte en mettant en avant l’idée clé : prétraiter le motif pour pouvoir faire de grands décalages

Objectif : Rechercher un motif dans un texte en mettant en avant l’idée clé : prétraiter le motif pour pouvoir faire de grands décalages.

1. Le problème

On dispose d’un texte T et d’un motif M.
On cherche à savoir si M apparaît dans T, et éventuellement à quelle position.

Exemple : dans le texte LE CODE EST EFFICACE, chercher le motif FACE.

2. Méthode naïve

La méthode naïve aligne le motif sous le texte, compare de gauche à droite, puis décale d’une position en cas d’échec.
Elle est simple, mais refait souvent des comparaisons inutiles.

3. Idée de Boyer-Moore

Boyer-Moore compare de droite à gauche (on commence par la dernière lettre du motif).
Quand il y a un échec, on ne décale pas forcément d’une seule position : on peut souvent faire un grand saut.

Idée centrale : on investit du temps au début (prétraitement du motif) pour gagner du temps pendant la recherche.

4. Prétraitement : la règle du « mauvais caractère »

On construit une table indiquant, pour chaque caractère du motif, la dernière position où il apparaît dans le motif. Si un caractère n’apparaît pas, on prend -1.

Exemple : motif BANANE

B  A  N  A  N  E
0  1  2  3  4  5

Dernières occurrences :
B → 0
A → 3
N → 4
E → 5
Autres lettres → -1

5. Comment se calcule le décalage ?

Lors d’un échec sur le caractère du texte placé sous l’index j du motif :

Décalage = j - derniere_occurrence(caractère_en_échec)
puis on décale d’au moins 1 : max(1, décalage).

Interprétation :

6. Simulation

Texte : ACCTGCATTAGATTACA
Motif : GATTA

  1. Aligner le motif sous le texte.
  2. Comparer de droite à gauche.
  3. Au premier échec, utiliser la table des dernières occurrences pour calculer le décalage.
  4. Recommencer jusqu’à trouver une occurrence ou dépasser la fin du texte.

Le déroulé

Texte : ACCTGCATTAGATTACA
Motif : GATTA

Table des dernières occurrences (motif = GATTA)

Motif : G  A  T  T  A
Index : 0  1  2  3  4

derniere_occurrence(G) = 0
derniere_occurrence(A) = 4
derniere_occurrence(T) = 3
autre lettre → -1

Règle du « mauvais caractère » :
decalage = j - derniere_occurrence(T[i+j])
puis i ← i + max(1, decalage). (Comparaison de droite à gauche.)

Indices (pour se repérer)

T :  A  C  C  T  G  C  A  T  T  A  G  A  T  T  A  C  A
     0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16

Déroulé (comparaison de droite à gauche)

Étape 1 : Alignement i = 0

T :  A  C  C  T  G  C  A  T  T  A  G  A  T  T  A  C  A
M :  G  A  T  T  A
     0  1  2  3  4
  • j = 4 :
    M[4] vs T[4]
    A vs G → ÉCHEC
Caractère fautif du texte : carac_fautif = T[i+j] = T[4] = G
derniere_occurrence(G) = 0
decalage = j - derniere_occurrence(carac_fautif) = 4 - 0 = 4
Donc i ← i + max(1, decalage) = 0 + 4 = 4

Étape 2 : Alignement i = 4

T :  A  C  C  T  G  C  A  T  T  A  G  A  T  T  A  C  A
M :              G  A  T  T  A
                 0  1  2  3  4
  • j = 4 :
    M[4] vs T[4+4]
    M[4] vs T[8]
    A vs T → ÉCHEC
    • Caractère fautif du texte : carac_fautif = T[i+j] = T[8] = T
    derniere_occurrence(T) = 3
    decalage = j - derniere_occurrence(carac_fautif) = 4 - 3 = 1
    Donc i ← i + max(1, decalage) = 4 + 1 = 5

    Étape 3 : Alignement i = 5

    T :  A  C  C  T  G  C  A  T  T  A  G  A  T  T  A  C  A
M :                 G  A  T  T  A
                    0  1  2  3  4
    • j = 4 :
      M[4] = A vs T[9] = A → SUCCÈS
    • j = 3 :
      M[3] = T vs T[8] = T → SUCCÈS
    • j = 2 :
      M[2] = T vs T[7] = T → SUCCÈS
    • j = 1 :
      M[1] = A vs T[6] = A → SUCCÈS
    • j = 0 :
      M[0] = G vs T[5] = C → ÉCHEC
    Caractère fautif du texte : carac_fautif = T[i+j] = T[5] = C
    derniere_occurrence(C) = -1
    decalage = j - derniere_occurrence(carac_fautif) = 0 - (-1) = 1
    Donc i ← i + max(1, decalage) = 5 + 1 = 6

    Étape 4 : Alignement i = 6

    T :  A  C  C  T  G  C  A  T  T  A  G  A  T  T  A  C  A
M :                    G  A  T  T  A
                       0  1  2  3  4
    • j = 4 :
      M[4] = A vs T[10] = G → ÉCHEC
    Caractère fautif du texte : carac_fautif = T[i+j] = T[10] = G
    derniere_occurrence(G) = 0
    decalage = j - derniere_occurrence(carac_fautif) = 4 - 0 = 4
    Donc i ← i + max(1, decalage) = 6 + 4 = 10

    Étape 5 : Alignement i = 10

    T :  A  C  C  T  G  C  A  T  T  A  G  A  T  T  A  C  A
M :                                G  A  T  T  A
                                   0  1  2  3  4
    • j = 4 :
      M[4] = A vs T[14] = A → SUCCÈS
    • j = 3 :
      M[3] = T vs T[13] = T → SUCCÈS
    • j = 2 :
      M[2] = T vs T[12] = T → SUCCÈS
    • j = 1 :
      M[1] = A vs T[11] = A → SUCCÈS
    • j = 0 :
      M[0] = G vs T[10] = G → SUCCÈS
    Motif trouvé : on obtient j = -1, donc une occurrence du motif commence en i = 10.

    Bilan

    Première occurrence de GATTA dans ACCTGCATTAGATTACA : 10.

    7. Mise en œuvre python (dans le notebook)

    La programmation est faite dans le notebook associé :

    8. À retenir

    • Boyer-Moore compare de droite à gauche.
    • Le prétraitement du motif permet de calculer des décalages efficaces.
    • La règle du « mauvais caractère » utilise la dernière occurrence d’un caractère dans le motif.