C17.2 : Algorithme de Horspool
Présentation
L'algorithme de Boyer-Moore est un algorithme de recherche d'un motif dans une texte particulièrement efficace. Il a été développé par Robert S. Boyer et J Strother Moore en 1977.
Il existe une version simplifiée, développée par Nigel Horspool en 1980, que nous allons présenter ici.
Structure de base de l'algorithme
L'algorithme de Horspool est basé sur l'algorithme vu dans l'activité précédente :
- - Le parcours du texte se fait de la gauche vers la droite.
- - Pour chaque position du motif, la comparaison avec les caractères du texte se fait de la droite vers la gauche.
Dans toute l'activité :
- - on note T le texte et M le motif ;
- - on note t la longueur de T et m la longueur de M ;
- - on utilise l'indice i_T pour parcourir T et i_M pour parcourir M.
def recherche(M: str, T: str) -> list:
"""
Exemples
>>> recherche('Bon', 'Hello !')
[]
>>> recherche('Bon', 'Bonjour !')
[0]
>>> recherche('Bon', 'Bonjour. Bonne année !')
[0, 9]
>>> recherche('bon', 'Ce gâteau est très bon')
[19]
"""
m = len(M)
t = len(T)
res = []
for i_T in range(t - m + 1):
i_M = m - 1
while M[i_M] == T[i_T + i_M] and i_M > 0 :
i_M = i_M - 1
if M[i_M] == T[i_T + i_M]:
res.append(i_T)
return res
if __name__ == "__main__":
import doctest
doctest.testmod(verbose = True)
L'amélioration de l'algorithme est basée sur le fait qu'il est possible d'augmenter i_T plus rapidement que de 1 en 1.
Quelques exemples pour comprendre comment accélérer la progression de i_T
Situation n° 1
■ Exemple
• Si on souhaite recherche la motif "dab" dans le texte "abracadab" :
Ici, 'r' et 'b' sont différents. De plus, 'r' n'est pas dans M.
Alors on peut décaler le motif d'une longueur m, c'est-à-dire augmenter i_M de la valeur m.
• Si on souhaite recherche la motif "dar" dans le texte "abracadab" :
Ici, les 'r' correspondent, mais 'a' et 'b' sont différents. De plus, 'r' n'est pas dans le reste de M.
Alors on peut décaler le motif d'une longueur m, c'est-à-dire augmenter i_M de la valeur m.
■ Synthèse
Si, pour une position i_T du motif M, la comparaison entre M et la portion de T correspondante échoue, et que le caractère de droite de la portion de T n'est pas dans le reste de M, alors on peut augmenter i_T de m.
Situation n° 2
■ Exemple
• Si on souhaite recherche la motif "dacb" dans le texte "abracadab" :
Comme 'a' et 'b' sont différents et que 'a' est dans M deux caractères avant la fin, on peut décaler le motif de deux positions, c'est-à-dire augmenter i_M de 2.
• Si on souhaite recherche la motif "daca" dans le texte "abracadab" :
Ici, 'a' et 'a' correspondent, mais ensuite 'r' et 'c' ne correspondent pas. Par ailleurs 'a' est dans M deux positions avant la fin (on exclue le 'a' de droite qui conduirait à un décalage de 0).
Alors, on peut décaler le motif de deux positions, c'est-à-dire augmenter i_M de 2.
■ Synthèse
Si, pour une position i_T du motif M, la comparaison entre M et la portion de T correspondante échoue, et que le caractère de droite de la portion de T est dans M à une position k en partant de la fin de M, alors on peut augmenter i_T de k.
A faire (à la main)
Représenter les étapes de la rechercher de "dab" dans "abracadabra".
Construction de la table de décalage
Afin de ne pas recalculer les décalages des lettres de M à chaque tentative de comparaison de M avec une portion de T, on va calculer les décalages une seule fois, à l'avance, et les stocker dans un dictionnaire. On notera qu'il n'est pas utile de mettre le caractère de droite de M dans le dictionnaire car le décalage pour ce caractère serait de 0.
Exemples :
- - Pour le mot "bac" le dictionnaire est {'b':2, 'a':1}.
- - Pour le mot "cacao" le dictionnaire est {'c':2, 'a':1}
A faire
Écrire la fonction decalage(mot:str)->dict qui prend un motif en paramètre et renvoie le dictionnaire des décalages de ses lettres.
Algorithme de Horspool
Écrire la fonction recherche_bmh(motif:str, texte:str)->list qui prend un motif et un texte en paramètres et renvoie la liste des positions du motif dans le texte.