Boyer-Moore [SuitableStuff]

- Boyer-Moore
  - Algorithme de Boyer-Moore

Boyer-Moore

Algorithme de Boyer-Moore

Recherche d'une chaîne dans un texte
Quelle complexité pour l'algorithme « standard » ? ¹⁾
Algorithme	Temps Pre-traitement	Temps d'Appareillement
Naïf	0	O((n-m+1) m )
Rabin-Karp	θ(m)	O((n-m+1) m )
Automate E.F.	O(m\|∑\|)	θ(n)
Knuth-Morris-Pratt	θ(m)	θ(n)
Boyer-Moore	O(n/m) au mieux O(m+n) au pire

[Comment] Peut-on mieux faire ?

Algo de Knuth Pratt Morris

Si mon tonton tond tontonton Tontonton ?

Quand on arrive sur tonton, alors, on peut se déplacer de 7 caractères car « tonton_ » ne fait pas partie de tontonton.

Boyer-Moore

Recherche du texte « Boyer-Moore » dans cette chaîne. Algorithme standard : 32 comparaisons. Boyer-Moore : 13 !

Recherche du texte « Boyer-Moore » dans cette chaîne.
Boyer-Moore
           Boyer-Moore
                     Boyer-Moore

Un peu moins simple qu'il n'y paraît Pour « Boyer-Moore », création d'un tableau :

B	y	–	M	o	r
10	8	5	4	2	1	et 11 pour tous les autres caractères.

C'est le « bad character shift ».

Mais il faut un 2è tableau, car on peut tomber sur un suffixe existant !

Ex : si ton tonton tond montonton alors…

Recherche de montonton

Rencontre d'un suffixe existant

Deux cas :

la chaîne recherchée ne commence pas comme elle finit

S

i

t

o

n

t

o

n

t

o

n

t

o

n

d

m

o

n

t

o

n

t

o

n

m

o

n

t

o

n

t

o

n

m

o

n

t

o

n

t

o

n

on peut s'aligner sur le 2è ton

m

o

n

t

o

n

t

o

n

m

o

n

t

o

n

t

o

n

m

o

n

t

o

n

t

o

n

m

o

n

t

o

n

t

o

n

la chaîne recherché commence comme elle finit :

S	i		t	o	n		t	o	n	r	o	n	r	o	n	d	m	o	n	t	o	n	t	o	n
o	n	t	o	n	t	o	n
		o	n	t	o	n	t	o	n
					o	n	t	o	n	t	o	n
									o	n	t	o	n	t	o	n

⇒ Il faut donc calculer un 2è tableau

Le tableau contient autant de lignes que de caractères dans le mot à rechercher et dit de combien on peut se déplacer si une sous-chaine est trouvée.

ndx	ontonton
0	n	1
1	on	8
2	ton	6
3	nton	6
4	onton	6
5	tonton	6
6	ntonton	6
7	ontonton	6

Complexité de Boyer-Moore

Meilleur des cas : 0(m/n) avec m la taille du mot à chercher et n la taille du texte.
Pire des cas : O(m+n)‏

¹⁾ Source : Cormen, Leiserson, Rivest & Stein, “Introduction to Algorithms, Second Edition”