Algorithme de Boyer Moore.

Rechercher une chaîne dans une autre.

L'algorithme de Boyer Moore permet de trouver "rapidement" si une suite de caractère apparaît dans un texte, cela à plusieurs intérêt par exemple :

On peut faire un chercher-remplacer dans un traitement de texte.

L'ADN est formée d'un grand nombre de brins de trois types différents, la recherche génétique cherche des suites de brins AdenineThymineGuanineCytosine.

image prise sur Wikipédia, CC BY-SA 3.0, Lien

On dispose de deux chaines, une le "motif" de longueur len(motif) contient ce qu'on cherche, l'autre le "texte" de longueur len(texte) est l'endroit où on effectue la recherche.

Exemple

Pour illustrer les algorithmes dans les exemples, rentrer le texte.

Entrer le motif à chercher :

Algorithme naïf

Algorithme

On affecte 0 à une variable i
On affecte 0 à une variable compteur
Tant que i ≤ len(texte)-len(motif) :

On affecte 0 à une variable j
Tant que j < len(motif) :

Si la (i+j) ième lettres de texte n'est pas égal à j ième lettre de motif alors on quitte la boucle.
On augmente j de 1.

Si j est égal à len(motif) alors on augmente le compteur de 1.
On augmente i de 1.

On retourne le compteur

Exemple

matrice

Méthode naive : i = 0
j = 0
nombre de comparaisons =
nombre de correspondances = 0

Le nombre de comparaison dans le meilleur des cas est de len(texte)-len(motif) + 1 (soit O(len(texte)-len(motif)) dans le pire des cas il est borné par len(texte) × len(motif).

Exemple

Compléter l'algorithme de l'epreuve pratique :

Modifier le programme pour qu'il compte les occurences.

Algorithme de Boyer-Moore.

Présentation.

Algorithme

On affecte len(motif) - 1 à une variable i
On affecte 0 à une variable compteur
Tant que i < len(texte) :

On affecte 0 à une variable j
Tant que j < len(motif) :

Si la (i-j) ième lettres de texte n'est pas egal à (len(motif) - j) ième lettre de motif alors on quitte la boucle.
On augmente j de 1.

Si j est égal à len(motif) alors on augmente le compteur de 1.
On augmente i comme l'indique la table de décalage.

On retourne le compteur

Remarque

Dans l'algorithme de Boyer Moore, on effectue les comparaisons en partant de la fin et en reculant.

Il reste à définir cette table de décalage, on donnera plusieures versions mais seule la première semble être au programme.

Version simple

Idée

Imaginons que l'on cherche le motif maman dans le texte, on commence par la fin, on compare le n avec le caractère de la position i si celui-ci est m alors il n'y a pas correspondance mais de combien doit se décaler ?

Si on se déplace de 1, le a va se retrouver en face du m et la correspondance ne va pas marcher :

-4	-3	-2	-1	0	1	2	3
				m
	m	a	m	a	n

Si on se déplace de 2 le m se retrouve en face du m et on peut espérer une correspondance.

-4	-3	-2	-1	0	1	2	3
				m
		m	a	m	a	n

Envisageons un deuxième cas le caractère i du texte est un n, le caractère i -1 est un a et le caractère i -2 est un z, le z n'est pas dans maman ! On peut alors décaler maman de 3.

-4	-3	-2	-1	0	1	2	3
		z	a	n
			m	a	m	a	n

Pour voir le décalage appuyer sur la case du tableau, par exemple si vous appuyer sur m de recul j = 1, vous avez le décalage de i à effectuer.

Implémentation.

Dans cette version de Boyer Moore il n'est pas nécessaire d'avoir un tableau deux dimensions, un simple dictionnaire D suffit.

Pour chaque lettre du motif on cherche de combien il est distant de la fin :

Lettre	distance
m	2
a	1
n	0

Maintenant le décalage dépend de j :

Trois cas de figures

Si texte[i - j] est égal à motif[len(motif) - j], c'est que c'est très bien et on augmente j de 1 et si on arrive à la fin du motif on a trouvé une occurrence.
Si texte[i-j] est une lettre du motif mais pas celle qu'il faut alors deux cas :
1. Soit j est supérieur au nombre indiqué D[texte[i-j]], et on décale i de 1.
2. Soit j est inférieur au nombre indiqué, on décale i de D[texte[i-j]] - j.
Si texte[i-j] n'est pas une lettre du motif on décale i de len(motif) - j.

Exemple

matrice

Méthode Boyer : i = 0
j = 0
nombre de comparaisons =
nombre de correspondances = 0

Exercice

Trouver la table des caractères précédents de erreur.

Lettre	distance
e
r
u

Compléter la table de décalage de erreur.

recul	5	4	3	2	1	0
e
r
u
autre

Trouver la table des caractères précédents de barbapapa.

Lettre	distance
b
a
r
p

Compléter la table de décalage de barbapapa.

recul	8	7	6	5	4	3	2	1	0
b
a
r
p
autre

Faire une fonction en Python qui va retourner le dictionnaire des derniers caractères d'un mot donné.
Faire une fonction en Python qui a un motif donné va donner le dacalage en suivant l'algorithme de Boyer Moore simple.
Implémenter l'algorithme de Boyer Moore simple.

Version plus

Dans la version précédente on cherche la dernière apparition d'un caractère et si on l'a passé alors on avance de 1.

Regardons la cas si dessous :

-7	-6	-5	-4	-3	-2	-1	0	1	2
					a	a	r
z	a	n	z	i	b	a	r

Dans la version précédente l'erreur (le a à la place du b) va entrainer un déplacement de 1 (car on a déjà dépasser le dernier a).

-7	-6	-5	-4	-3	-2	-1	0	1	2
					a	a	r
	z	a	n	z	i	b	a	r

Mais on sait déjà que le résultat ne va pas marcher car le a se trouve en face du i, on peut le déplacer de jusqu'au a précédant.

-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4
					a	a	r
				z	a	n	z	i	b	a	r

Implémentation

L'implémentation est plus difficile, il faut pour chaque valeur de j un dictionnaire où on donne la distance à la lettre précédente.

Exemple

matrice

Méthode Boyer évoluée : i = 0
j = 0
nombre de comparaisons =
nombre de correspondances =0

Exercice

Compléter la table de décalage de erreur avec la version plus de Boyer Moore.

recul	5	4	3	2	1	0
e
r
u
autre

Compléter la table de décalage de barbapapa.

recul	8	7	6	5	4	3	2	1	0
b
a
r
p
autre

Faire une fonction en Python qui a un motif donné va donner le décalage en suivant l'algorithme de Boyer Moore plus.
Implémenter l'algorithme de Boyer Moore plus.

Version finale

Idée

Dans les versions précédentes on ne considère que la case i - j du texte et on effectue un décalage du motif pour que la correspondance à cette case marche, mais regardons le cas suivant :

-7	-6	-5	-4	-3	-2	-1	0	1	2
						b	r
z	a	n	z	i	b	a	r

Dans les versions précédentes le décalage donne :

-7	-6	-5	-4	-3	-2	-1	0	1	2
						b	r
	z	a	n	z	i	b	a	r

Et on refait le test de savoir si il y a correspondance à partir de la case 1, peut être que le texte correspond (on a un r) par contre quand j = 1 on va comparer r avec a et on n'obtiendra pas de correspondance ! Et en réalité on pouvait en être sur à l'avance.

Voilà ce que donne la matrice de decalage :

Implémentation

Il faut pour toutes les valeurs de j (de 0 à len(motif) -1) construire un dictionnaire avec pour clef les lettres (ou autre) et indiquer le minimum de de combien il faut décaler pour avoir une correspondance. Essayons pour j = 3 avec la lettre m, si on est arrivé jusque là ca veut dire qu'il y a correspondance du mot avec le motif pour j = 0,1,2,3.

-4	-3	-2	-1	0	1	2	3	4	5
	m	m	a	n
m	a	m	a	n

Avec les versions de Boyer Moore précédente la décalage est de 1, mais la correspondance ne peut pas se faire.

Décalage de un.

-4	-3	-2	-1	0	1	2	3	4	5
	m	m	a	n
	m	a	m	a	n

Pareil pour deux :

-4	-3	-2	-1	0	1	2	3	4	5
	m	m	a	n
		m	a	m	a	n

Pareil pour trois :

-4	-3	-2	-1	0	1	2	3	4	5
	m	m	a	n
			m	a	m	a	n

Pareil pour quatre :

-4	-3	-2	-1	0	1	2	3	4	5
	m	m	a	n
				m	a	m	a	n

Il faut donc décaler de cinq :

-4	-3	-2	-1	0	1	2	3	4	5
	m	m	a	n
					m	a	m	a	n

Regardons le motif tintin,si pour j = 4 on trouve un z avec les versions précédentes on décale de 2 :

-5	-4	-3	-2	-1	0	1	2	3
	z	n	t	i	n
		t	i	n	t	i	n

Mais on sait à l'avance que cela ne va pas aller, il faut décaler de 3 !

-5	-4	-3	-2	-1	0	1	2	3
	z	n	t	i	n
			t	i	n	t	i	n

Exemple

Essayer

matrice

Méthode Boyer évoluée : i = 0
j = 0
nombre de comparaisons =
nombre de correspondances = 0

Exercice

Compléter la table de décalage de erreur avec la version finale de Boyer Moore.

recul	5	4	3	2	1	0
e
r
u
autre

Compléter la table de décalage de barbapapa.

recul	8	7	6	5	4	3	2	1	0
b
a
r
p
autre

Faire une fonction en Python qui a un motif donné va donner le décalage en suivant l'algorithme de Boyer Moore finale.
Implémenter l'algorithme de Boyer Moore finale.