ULUMINE · Numérique et sciences informatiques (NSI) · Terminale
Recherche textuelle : l’algorithme de Boyer-Moore
Boyer-Moore cherche un motif dans un texte en comparant de droite à gauche et en sautant de nombreuses positions grâce à une table de décalages.
Algorithme naïf
- Toutes les positions de 0 à n − m, comparaisons de gauche à droite.
- Décalage d’une position ; pire cas : n × m comparaisons.
Boyer-Moore (Horspool)
- Table : pour c dans le motif sans sa dernière lettre, décalage(c) = m − 1 − dernière position de c ; sinon m.
- Comparaison de droite à gauche à la position i.
- Nouveau i = i + décalage(texte[i + m − 1]).
Pièges à éviter
- Inclure la dernière lettre du motif dans la table.
- Prendre la première occurrence d’une lettre au lieu de la dernière.
- Calculer le décalage avec la lettre où la différence a eu lieu au lieu de la lettre alignée avec la fin du motif.
- Oublier les espaces quand on compte les positions dans un texte.