Recherche de motifs dans des chaînes de caractères

icône de pdf
Signaler

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 :

8f35ae8a-2178-450a-8487-a3d00c34c255

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 nm. On notera : recherche_naïve = Ω(nm), ce qui signifie que recherche_naïve « domine » la fonction f(n)=nm 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(nm)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 :

19261d2b-9b93-4cea-9408-135485b1024a

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.