Après la présentation d'une approche naïve du problème, nous introduisons les heuristiques de l'algorithme de Boyer-Moore

ILe 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\left(1\right)$, c'est-à-dire est en temps constant.

IIL'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 = $\Omega (n-m)$, ce qui signifie que recherche_naïve « domine » la fonction $f\left(n\right)=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\left((n-m)m\right)$. Ce calcul peut s'avérer long pour de grandes valeurs de $n$, d'où le besoin d'une approche plus efficace.

IIIUne 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.

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:j] 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.