Ressources

Algorithme de Boyer Moore

Principe

On recherche un motif dans un texte, le principe va être le suivant

- On va comparer les caractères à partir du dernier:

- Dés qu’on rencontre un caractère non conforme dans le texte, on note ce caractère et on cherche dans le motif si le caractère non conforme n’est pas présent à gauche dans le motif:

Ici le caractère B est non conforme, on regarde si à gauche dans le motif il y a un B. OUI ici. Si le caractère non conforme est présent à gauche dans le motif, on décale le motif pour le mettre en correspondance au niveau de ce caractère:

- On recommence ensuite la comparaison à partir du dernier:

- Dés qu’on rencontre un caractère non conforme dans le texte, on note ce caractère et on cherche dans le motif si le caractère non conforme n’est pas présent à gauche dans le motif ( ici encore B et oui il est présent, on décale le motif) :

- On recommence ensuite la compaison à partir du dernier jusquà une éventuelle différence :

Dés qu’on rencontre un caractère non conforme dans le texte, on note ce caractère et on cherche dans le motif si le caractère non conforme n’est pas présent à gauche dans le motif ( ici ce n’est pas possible, il n’y a plus de caractères à gauche dans le motif)

Si le caractère non conforme n’est pas présent à gauche dans le motif, on décale tout le motif pour le mettre en correspondance avec le caractère qui suit celui qui est non conforme:

- On recommence ensuite la comparaison à partir du dernier :

- On cherche dans le motif si le caractère non conforme n’est pas présent à gauche dans le motif ( ici c’est B et oui il est présent, on décale le motif) :

- On recommence ensuite la comparaison à partir du dernier :

- On recommence ensuite la comparaison à partir du dernier jusqu'à une éventuelle différence. Ici on n’en rentrera plus. Le motif est bien dans le texte.

Table de décalage

Pour vérifier la présence du caractère non conforme à gauche, on dresse une table de décalage qui précise pour une position donnée quel sont les caractères à gauche et où ils se situent. Si un même caractère est présent plusieurs fois, c’est le plus à droite qui est indiqué.

La table précise pour une position j dans le motif à quel emplacement sont les lettres du motif situés avant j.

Voici la table pour le mot "ababa"

En python, on peut mettre ces distances dans une liste de dictionnaires qui donnent le décalage de Boyer-Moore pour chaque lettre selon la position (j)

Algorithme de Boyer-Moore

m = "ABABA"
t = "BBBBABABAAA"

""" affiche toutes les occurrences de m dans t

avec l'algorithme de Boyer-Moore"""

# la fonction table_dec renvoie le dico de décalage pour le motif m

d = table_dec(m)

i = 0

while i <= len(t) - len(m):

k = 0

for j in range(len(m) - 1, -1, -1):

if t[i + j] != m[j]:

# calcul du décalage du motif

k = decalage(d, j, t[i + j])

break

if k == 0:

print("occurrence à la position", i)

k = 1

i += k

Créé avec HelpNDoc Personal Edition: Créer des documents d'aide CHM facilement