Chercher un mot dans un document, une séquence dans un génome de plusieurs milliards de lettres : la recherche d’un motif dans un texte est partout. L’algorithme naïf compare le motif à toutes les positions. L’algorithme de Boyer-Moore est bien plus malin : en lisant le motif de droite à gauche, il peut sauter d’un coup de nombreuses positions.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Programmer et analyser l’algorithme naïf de recherche textuelle
- Construire la table des décalages d’un motif (version de Horspool)
- Dérouler l’algorithme de Boyer-Moore-Horspool sur un exemple
- Comprendre pourquoi Boyer-Moore est en pratique beaucoup plus rapide
1. L’algorithme naïf
On place le motif (longueur m) à chaque position i du texte (longueur n), de 0 à n − m, et on compare les lettres de gauche à droite jusqu’à une différence ou jusqu’au bout du motif.
def recherche_naive(texte, motif):
n, m = len(texte), len(motif)
occurrences = []
for i in range(n - m + 1):
j = 0
while j < m and texte[i + j] == motif[j]:
j = j + 1
if j == m:
occurrences.append(i)
return occurrences2. Les idées de Boyer-Moore
- On compare le motif au texte de droite à gauche, en commençant par la dernière lettre du motif.
- Après la comparaison, on regarde la lettre du texte alignée avec la dernière lettre du motif, et on décale le motif pour amener sous cette lettre son occurrence la plus à droite dans le motif (hors dernière position).
- Si cette lettre n’apparaît pas dans le motif (hors dernière position), on décale de toute la longueur m du motif.
Table des décalages (Horspool) : Pour chaque lettre c présente dans le motif privé de sa dernière lettre : décalage(c) = m − 1 − (indice de la dernière occurrence de c parmi les m − 1 premières lettres). Pour toute autre lettre : décalage = m.
| Lettre | C | H | I | E | autre (dont N) |
|---|---|---|---|---|---|
| Décalage | 4 | 3 | 2 | 1 | 5 |
3. Programme et exemple
def table_decalages(motif):
m = len(motif)
d = {}
for k in range(m - 1): # toutes les lettres sauf la dernière
d[motif[k]] = m - 1 - k
return d
def boyer_moore(texte, motif):
n, m = len(texte), len(motif)
d = table_decalages(motif)
occurrences = []
i = 0 # position du motif dans le texte
while i <= n - m:
j = m - 1 # comparaison de droite à gauche
while j >= 0 and texte[i + j] == motif[j]:
j = j - 1
if j < 0:
occurrences.append(i)
i = i + d.get(texte[i + m - 1], m) # m si la lettre est absente de la table
return occurrencesRecherche de CHIEN dans « UN CHAT ET UN CHIEN » (19 caractères, espaces compris)
- i = 0 : la lettre alignée avec N est H : différence. Décalage(H) = 3, donc i = 3.
- i = 3 : la lettre alignée avec N est une espace, absente du motif : décalage 5, i = 8.
- i = 8 : N = N, puis U ≠ E. La lettre alignée avec la fin du motif est N : décalage 5, i = 13.
- i = 13 : E ≠ N. Décalage(E) = 1, i = 14.
- i = 14 : les 5 lettres coïncident : occurrence à la position 14.
10 comparaisons de lettres, contre 21 pour l’algorithme naïf sur le même exemple.
À retenir
- Algorithme naïf : décalage d’une position, jusqu’à n × m comparaisons.
- Boyer-Moore : comparaison de droite à gauche et décalages calculés à l’avance.
- Décalage(c) = m − 1 − dernière position de c dans le motif privé de sa dernière lettre ; m si c n’y figure pas.
- Le décalage dépend de la lettre du texte alignée avec la dernière lettre du motif.
- En pratique, Boyer-Moore saute de nombreuses positions et va bien plus vite.
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.