Lycée > Terminale > NSI > Rechercher un motif dans un texte : l'algorithme de Boyer-Moore

Rechercher un motif dans un texte : l'algorithme de Boyer-Moore

Fiche de cours
Quiz
Profs en ligne
Videos
Application mobile

Objectifs

Connaitre l’algorithme de recherche naïve d’un motif dans un texte.
Connaitre l’algorithme de Boyer-Moore.
Programmer l’algorithme de recherche naïve d’un motif dans un texte.
Programmer l’algorithme de Boyer-Moore.

Points clés

Rechercher un motif dans un texte consiste à rechercher le ou les indices à partir desquels on retrouve le motif dans le texte. On dit que l’on recherche la ou les occurrences du motif dans le texte.
La recherche naïve consiste à comparer un à un, de gauche à droite, les caractères du texte et ceux du motif, et de décaler la recherche dans le texte de un rang dès qu’une comparaison échoue.
L’algorithme de Boyer-Moore consiste à comparer les caractères du motif et ceux du texte de droite à gauche, puis, en cas d’échec d’une comparaison de caractères, d’observer le caractère du texte qui ne correspondait pas à celui du motif et d’en déduire si on ne peut pas décaler le motif de plus de 1 rang dans la recherche du motif dans le texte.

Pour bien comprendre

Utiliser les chaines de caractères.

1. La recherche naïve

a. Principe

Rechercher un motif dans un texte consiste à rechercher le ou les indices à partir desquels on retrouve le motif dans le texte. On dit que l’on recherche la ou les occurrences du motif dans le texte.

La recherche textuelle est très utilisée en génétique pour détecter la présence ou non de gènes, dans le web pour rechercher des chaines de caractères, dans les moteurs de recherche, etc.

Exemple
Dans la chaine de caractères “abracadabra”, on trouve deux occurrences du motif “bra” pour i = 1 et i = 8 (la lettre “a” correspond à i = 0).

b. Description de la recherche naïve

La recherche naïve consiste à comparer un à un, de gauche à droite, les caractères du texte et ceux du motif, et de décaler la recherche dans le texte de un rang dès qu’une comparaison échoue.

Pas à pas, cela donne :

i = 0 : Comparer de gauche à droite chaque caractère du motif avec ceux du texte à partir de i = 0.
- Si tous les caractères du motif correspondent, on a trouvé une occurrence du motif dans le texte.
- On recommence la comparaison au rang suivant : i = 1.
i = 1 : Comparer chaque caractère du motif avec ceux du texte à partir de i = 1.
- Si tous les caractères du motif correspondent, on a trouvé une occurrence du motif dans le texte.
- On recommence la comparaison au rang suivant : i = 2.
...

Exemple
On considère le motif “TAGGAC” et le texte “TAGTAGCACTGTAGGACTGC”.

On recherche la ou les occurrences du motif dans le texte.

i = 0 :

Les trois premiers caractères du motif correspondent mais pas le quatrième. i = 0 n’est donc pas une occurrence du motif dans le texte.

i = 1 :

Le premier caractère du motif ne correspond pas au texte.
i = 1 n’est donc pas une occurrence du motif dans le texte.

i = 2 :

Le premier caractère du motif ne correspond pas au texte.
i = 2 n’est donc pas une occurrence du motif dans le texte.

i = 3 :

Les trois premiers caractères du motif correspondent mais pas le quatrième. i = 3 n’est donc pas une occurrence du motif dans le texte.

i = 4 :

Le premier caractère du motif ne correspond pas au texte.
i = 4 n’est donc pas une occurrence du motif dans le texte.

i = 5 :

Le premier caractère du motif ne correspond pas au texte.
i = 5 n’est donc pas une occurrence du motif dans le texte.

i = 6 :

Le premier caractère du motif ne correspond pas au texte.
i = 6 n’est donc pas une occurrence du motif dans le texte.

i = 7 :

Le premier caractère du motif ne correspond pas au texte.
i = 7 n’est donc pas une occurrence du motif dans le texte.

i = 8 :

Le premier caractère du motif ne correspond pas au texte.
i = 8 n’est donc pas une occurrence du motif dans le texte.

i = 9 :

Le premier caractère du motif correspond au texte mais pas le second.
i = 9 n’est donc pas une occurrence du motif dans le texte.

i = 10 :

Le premier caractère du motif ne correspond pas au texte.
i = 10 n’est donc pas une occurrence du motif dans le texte.

i = 11 :

Tous les caractères du motif correspondent aux caractères du texte à partir de i = 11. On a trouvé une première occurrence du motif au bout de 24 comparaisons.
On peut poursuivre pour chercher une autre occurrence.

c. Programmation de la recherche naïve

En Python, la fonction rech_naive(motif, texte) implémente la recherche naïve du motif dans le texte. Il renvoie le tableau des indices pour lesquels on a trouvé une occurrence du motif dans le texte.

Python	Explication
def rech_naive(motif, texte):	On définit la fonction rech_naive.
reponse = [] t = len(texte) m = len(motif)	On initialise le tableau reponse avec un tableau vide. On affecte à t la taille de texte et à m la taille du motif.
for i in range(0, t – m + 1):	Pour i allant de 0 à t – m,
if texte[i : i + m] == motif: reponse.append(i)	si la partie du texte (de taille m commençant à i) et le motif correspondent, alors on ajoute i au tableau reponse.
return reponse	on retourne le tableau reponse.

Exemple
Voici l’appel de cette fonction sur Python Tutor pour le motif “TAGGAC” et le texte “TAGTAGCACTGTAGGACTGC”.

On obtient [11], ce qui signifie qu’il y a une occurrence en i = 11 du motif “TAGGAC” dans le texte.

2. L'algorithme de Boyer-Moore

a. Principe

L’algorithme de Boyer-Moore consiste à comparer les caractères du motif et ceux du texte de droite à gauche, puis, en cas d’échec d’une comparaison de caractères, d’observer le caractère du texte qui ne correspondait pas à celui du motif et d’en déduire si on ne peut pas décaler le motif de plus de 1 rang dans la recherche du motif dans le texte.

Exemple
Dans la chaine de caractères “abracadabra”, on recherche le motif “cad”.

Étape 1 :

La première comparaison échoue. On observe le caractère r du texte où il y a eu l’échec. Le caractère r n’appartient pas au motif “cad”.
On peut donc décaler le motif de 3 rangs puisque le r ne correspondra jamais.

Étape 2 :

La première comparaison échoue. On observe le caractère a du texte où il y a eu l’échec. Le caractère a appartient au motif “cad”.
On peut donc l’aligner avec le caractère a du motif “cad”.

Étape 3 :

Tous les caractères correspondent. On a donc fini la recherche de la première occurrence. On peut si on le souhaite poursuivre la recherche pour trouver une deuxième occurence.

b. Comprendre le décalage

Lorsque l’on recherche un motif dans un texte, on considère que l’échec de correspondance du motif et du texte au rang i apparait pour le caractère x du texte et le caractère y du motif d’indice j (c’est-à-dire y = motif[j]).

Il y a deux cas :

Si x (caractère du texte) n’est pas un caractère du motif, alors, pour la comparaison, on place le motif juste à droite du caractère x du texte qui a provoqué l’échec. Ainsi le décalage de i (dans le texte) sera de j + 1 (indice j du caractère du motif + 1).
Si x (caractère du texte) est un caractère du motif, alors, pour la comparaison, on déplace le motif vers la droite pour que le x le plus à droite du x et le x du texte correspondent. Si ne n’est pas possible, on décale le motif de 1.

Exemple
On considère le motif “TAGGAC” et le texte “TAGTAGGACTGTACTAGGAC”.

On recherche les occurrences du motif dans le texte.

i = 0 :

Le dernier caractère du motif ne correspond pas au caractère G du texte. Or G est un caractère du motif. On aligne donc ce caractère et le dernier G du motif.

i = 2 :

Le dernier caractère du motif ne correspond pas au caractère A du texte. Or A est un caractère du motif. On aligne donc ce caractère et le dernier A du motif.

i = 3 :

Les comparaisons échouent au bout de 3 comparaisons. Dans le texte, on stoppe à la lettre C. Comme cette lettre n'apparait pas dans le début du motif, on décale le motif de 1 rang.

i = 4 :

Le dernier caractère du motif ne correspond pas au caractère T du texte. Or T est un caractère du motif. On aligne donc ce caractère et le dernier T du motif (qui est sa première lettre).

i = 9 :

Le dernier caractère du motif ne correspond pas au caractère G du texte. Or G est un caractère du motif. On aligne donc ce caractère et le dernier G du motif.

i = 11 :

Tous les caractères du motif correspondent aux caractères du texte à partir de i = 11. On a trouvé une occurrence du motif au bout de 13 comparaisons. On peut poursuivre la recherche si on le souhaite, pour trouver une deuxième occurence.

c. Programmation de l'algorithme de Boyer-Moore

Traiter le motif

Pour programmer l’algorithme de Boyer-Moore, on doit d’abord traiter le motif pour avoir des informations sur la position la plus à droite de chacun de ses caractères à partir d’un indice donné. Ces informations seront stockées dans un tableau de dictionnaires.

En Python, la fonction table_boyer_moore(motif) prend en paramètre le motif, et retourne le tableau dont chaque élément est un dictionnaire des positions des caractères les plus à droite pour chaque indice du motif donné.

Python	Explication
def table_boyer_moore(motif):	On définit la fonction.
d = [{} for i in range(len(motif))]	On initialise le tableau d avec des dictionnaires vides.
for j in range(len(motif)):	Pour chaque indice du motif j allant de 0 à len(motif)–1,
for k in range(j):	pour tout k allant de 0 à j–1, (on parcourt le motif)
d[j][motif[k]] = k	On attribue la valeur k à la clé motif[k] du (j+1)-ième dictionnaire du tableau d. (dans le tableau d[j], on associe au (k+1)-ème caractère du motif son indice k)
return d	on retourne le tableau d.

Déterminer le décalage à opérer

Ensuite, la fonction decalage(d, j, chr) prend en paramètres :

le tableau précédent d ;
l’indice j du motif qui correspond à l’indice du caractère du motif pour lequel la comparaison avec le texte a échoué ;
et chr le caractère du texte pour lequel la comparaison a échoué.

Cette fonction renvoie le décalage à opérer pour continuer l’algorithme de Boyer-Moore.

Python	Explication
def decalage(d, j, chr):	On définit la fonction decalage.
if chr in d[j]:	Si le caractère chr (caractère du texte pour lequel la comparaison a échoué) est une clé du dictionnaire d[j]
return j – d[j][chr]	on retourne j – d[j][chr] (l’écart entre j (l’indice d’arrêt de la comparaison dans le motif) et le décalage pour retrouver le caractère d’arrêt dans le texte **)
else:	Sinon
return j + 1	on retourne j + 1 (on décale d’un rang vers la droite).

** Explication
d[j][chr] correspond à l'indice du caractère chr dans le motif le plus près à gauche du (j+1)-ème caractère du motif.

Par exemple, pour le motif "caractere" :

d[4]['a'] vaut 3 car le dernier 'a' rencontré avant le 5^e caractère (‘t’) est d'indice 3.
d[2]['a'] vaut 1 car le dernier 'a' rencontré avant le 3^e caractère (‘r’) est d'indice 1.

Implémentation de l’algorithme de Boyer-Moore

Enfin, la fonction rech_boyer_moore(motif, texte) implémente l’algorithme de Boyer-Moore de recherche du motif dans le texte.

Python	Explication
def rech_boyer_moore(motif, texte):	On définit la fonction.
d = table_boyer_moore(motif) i = 0 reponse = []	On attribue à d la table de Boyer-Moore (qui donne la position de chaque élément du motif). On initialise la variable i (indice où on place le motif par rapport au texte) à 0 et reponse avec un tableau vide.
while i < len(texte) – len(motif):	Tant que i est strictement inférieur à len(texte)–len(motif),
k = 0	on initialise la variable k à 0. (k est le décalage que l’on réalisera. Par exemple, dans la recherche naïve, k vaut toujours 1. On avance le motif de 1 en 1.)
for j in range(len(motif)–1, –1, –1):	Pour j (indice dans le motif) allant de len(motif)–1 à 0 en décroissant de 1,
if texte[i + j] != motif[j]:	si le caractère du texte d’indice i+j ne correspond pas au caractère du motif d’indice j, alors
k = decalage(d, j, texte[i+j]) break	on attribue à k le décalage correspondant. (break signifie qu’on sort de la boucle)
if k == 0: reponse.append(i) k = 1	Si k est égal à 0, alors on ajoute i au tableau reponse, puis on attribue 1 à k (on avance le motif de 1).
i = i + k	on incrémente i (indice où on place le motif par rapport au texte) du décalage k.
return reponse	on retourne le tableau reponse.