Après la présentation d'une approche naïve du problème, nous introduisons les heuristiques de l'algorithme de Boyer-Moore
I. Le problème
On part d’une séquence S dans laquelle on cherche un motif M. La longueur de M est souvent très petite devant celle de S. On souhaite trouver toutes les occurrences de M dans S.
Ce problème correspond par exemple à la recherche qu’on peut faire dans un document bureautique ou une page web, mais aussi à la recherche d’un motif donné dans une séquence génomique. Par exemple, si on cherche le motif M = 'GACA' dans la chaine S = 'GCCGACTGACACCAGACATCG', on le trouve 2 fois (en positions 7 et 14, en numérotant 0 le premier caractère d’une chaîne).
M et S sont stockés sous forme de chaînes de caractères ou de tableaux et on considère que l’accès à un caractère par son indice se fait en O(1), c’est-à-dire est en temps constant.
II. L’approche « naïve »
1) En utilisant les fonctions natives de Python
On peut tout d’abord utiliser simplement les facilités de Python : 'fait' in 'il fait beau' renvoie True mais ne donne pas les positions ni le nombre d’occurrences trouvées. Il est également difficile d’en évaluer la complexité algorithmique à moins d’aller voir le détail de l’implémentation Python.
2) Méthode « naïve » de référence
Écrivons cette méthode naïve avec une boucle for et une boucle while :
L’utilisation de while permet de s’arrêter dès qu’un caractère ne correspond pas.
3) Complexité algorithmique de la recherche naïve
L’opération élémentaire est la comparaison entre 2 cases des chaînes S et M.
Pour la complexité de cette recherche, le meilleur cas correspond à la situation où on trouve d’emblée que la première lettre du motif M n’est jamais dans S ce qui arrive lorsque, pour tout 0 ≤ i ≤ n-m+1, S[i] != M[0]. Dans ce cas, on ne rentre pas dans la boucle while et la complexité est en n−m. On notera : recherche_naïve = Ω(n−m), ce qui signifie que recherche_naïve « domine » la fonction f(n)=n−m pour de grandes valeurs de n.
Le pire des cas se présente si on est amené à parcourir les deux boucles dans leur intégralité comme par exemple si M se répète dans S comme M = 'BOA' dans S = 'BOABOABOABOABOABOABOA'. Dans ce cas la complexité est en O(n−m)m. Ce calcul peut s’avérer long pour de grandes valeurs de n, d’où le besoin d’une approche plus efficace.
III. Une approche plus élaborée : Boyer-Moore
L’idée est d’améliorer la recherche en utilisant certaines heuristiques dont nous détaillons la première.
Mot-clé
Du grec ancien ε′υρ′ισκω, eurisko, « je trouve », une heuristique en informatique est une méthode de calcul efficace (en termes de complexité algorithmique) mais pas nécessairement optimale ou exacte (parfois solution approchée).
L’algorithme est aussi à fenêtre glissante comme dans la recherche naïve mais la comparaison du motif avec la chaîne, soit M[0:m] avec S[i:i+m], se fait de droite à gauche, en commençant par la fin ! La première heuristique, souvent appelée celle du « mauvais caractère », va tirer parti du parcours inversé en testant d’abord s’il y a correspondance pour le dernier caractère du motif.
Par exemple, dans la recherche suivante de M dans S :
On voit que E et U ne correspondent pas ! Et comme U n’apparaît pas du tout dans le motif, nous pouvons faire glisser le motif vers la droite de sa propre longueur (ici |M| = 7) en étant sûr de ne manquer aucune correspondance. Et même si le caractère de S apparaît ailleurs dans M, lorsque l’on fait la comparaison S[i+j] == M[j], si S[i+j] = a ne correspond pas, on aligne alors l’occurrence la plus à droite de a dans M[0:m-1] avec S[i+j].
Pour la seconde heuristique, appelée celle du « bon suffixe », un tableau suf est utilisé dont chaque entrée suf[i] contient le décalage du motif en cas d’erreur de correspondance en position i-1, si le suffixe (la fin) du motif commençant position i correspond.