Algo Boyer-Moore

·
Naif : une case Ra fois .
à On my .

Règle mauvais caractère :

·
Règle du bon suffixe :

Aligner caractère du Texte avec le même caractère

Aligner les caractères du suffixe qui se retrouve
dans le matif ailleurs dans le motif.

AGAGGCA + 1C A AGAGGA2CT
j à d
A
81) bundde & car on va
aligner n avec le mathe A e

regarde match "EAG"

AG)A 1. On re
qui

Et 3
. On suffire qui
sic'est t , on fait un sout de m
,
car a un contient "GAG" et pas (
un sait le T jamais re retrouver
que ra

le mot 3
. On cherche un suffire correspond à
dans .
m
qui un

préfixe "Ad" :

. On calcule
4 les sants :

de 2 préfixe à E suffixe
↑
A AGAGGA2CT
↑

&e
A À d
+ 3 A24A4
 Ex 1 :

Texte :
- AG(22 + &(422-122A212) -GAG)

Mot : A4((GAG

m = 8 n = 25

Table mauvais caractères :

Lettre : A
Motif : A4 (cGAG
~-
*

Lettre : &

At et il
lie
Matif : match

Lettre : &
Motif : A4 (cGAG
-

- 1

%
 Table do bon suffise :

· Pour C :

Ab((212

# faut aller à un prochain caractère

qui n'est pas un : ou fait bond de , 1

on se ramasse à G.

·
Pour EC

C est bon mais & pas bon .

# faut trouver un e suivi d'un caractère

autre que 8 .

~
Donc : A425610 C
---- + 4
-
car le prochain caractère est une
,
et
non un 1.

Pour Ac
AGS
·
:

+
g
Dansrewas on ship complètement Ra
chaine .

Pour AC :
I
G C &

% &
A

AC
Sc
C
g
S

S
-21
((215
-(22AGS
&

A((((125
On peut maintenant faire
l'algo :

%
AG(22 -1221212)c212)
T((22)
A(((412d MC : 8 -
2 =
6 BS : S
Ab((4A24 Mc = A = 2 -

0 = 2 BS 1 :

AG)C(12) Mc 283 1 =

- 1
A4c4162 MC = A = 2 -
4 = 0 = 1 BS = 5

Accue b
↑
 K MP : Knuft Morris Pratt

Le but c'est de parcourir la seule fois

séquence une .

trouver le
On vent donc plus long préfixe qui match le suffixe à toutes les opérations.

Ev : ABCDABD

AB se
répète e fois dans on
pert juste retourner dans la
séquence AB (first one) puis valider que le prochain
caractère match .

On doit faire la table du bun suffixe .

Ex : Ség : AGGG +G (12 + AG) AAA212(2)AT
Motif : AG (A&CAT

On calcule suit :
pi comme
-

Premier Caractère est .

0 Table bon suffire :

pi va être l'index de la prochaine

lettre qui a le même suffire lesi 912345678
que
-
Ex : pour a=1 esq ,
e est pareil que A ? Non doc O PAG (AG)A +

00012348
le caractère avec A jusqu'a
quion trouve on match.
an
Pi
·

compare
·
Quand on trouie un match pi 1 ,
=
.

Maintenant, pour les prochains aractères , un doit comparer avec le caractère 91 (ef
:

et pi sera + 1 à chaque match.

On fait la recherche caractère : (on commence de début

+
AGG + b (12 + AG)AAAGA2(AG)AT
↑ I
AG (AG)A + c- K

k= 2 et i= 3
# = & etk + 1 * 27) alors (1) 0
=

,
donc K 0
=
Université du Québec
École de technologie supérieure
Département de génie logiciel et des TI

LOG-320
Structures de données et
algorithmes
Recherche dans les chaînes
de caractères
 Recherche de chaînes de caractères
! Objectif:
Trouver un motif de
longueur M dans un
texte de longueur N
Typiquement: N >> M

" Exemple:
Motif:
bot t e

Texte:
Un e a i gu i l l e dans une bo t t e de f o i n

Correspondance 2
 Deux types de comparaison
! Recherche exacte d’un motif dans un texte
1. Approche naïve
2. Boyer-Moore
3. Knuth-Morris-Pratt (KMP)
4. Rabin-Karp

! Recherche approximative d’un motif dans

un texte c.à.d. que le motif ne sera pas
exactement celui retrouvé dans le texte, mais
similaire.
1. Distance de Levenshtein

3
 Algorithme naïf de matching exact
! Principe de l’algorithme naïf
– ! On compare chacune des lettres du motif avec le
texte
– ✅ Il y a correspondance si toutes les lettres sont
identiques
– ❌ Si une lettre ne correspond pas, on « décale » le
motif.

a c a a b c a c a a b c a c a a b c a c a a b c

a a b a a b a a b a a b
s=0 s=1 s=2 s=3

4
 Algorithme naïf de matching exact
⚙ Algorithme naïf:
RechercheNaïve(T[1..n],M[1..m])
1. Liste = {}
2. pour i = 1 à n-m
3. j=1
4. tant que j<m et T[i+j] == M[j]
5. j = j+1
6. si j == m
7. Liste = Liste U {i}
8. retourner Liste

# Quel est l’ordre asymptotique?

! Meilleur cas : O(n)
" Pire cas: O(n*m)
Texte: a a a a a a a a a a a a
Motif: a a a 5
Recherche dans les chaînes de caractères

ALGORITHME DE
BOYER-MOORE
6
 Algorithme de Boyer-Moore
# Intuition:
Un e a i g u i l l e d a n s u n e b o t t e d e f o i n
b o t t e
b o t t e

❓ Est-ce qu’il est possible d’éviter des comparaisons?

⚙ Algorithme Boyer-Moore:
• ! Commence la comparaison avec le dernier caractère du
motif
• " Si un caractère ou une portion du texte ne se retrouve pas
dans le motif, il est possible d’éviter plusieurs comparaisons.
http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/index.html
http://fr.wikibooks.org/wiki/Implémentation_d'algorithmes_classiques/Algorithmique_du_texte/Algorithme_de_Boyer-Moore

7
 Règle du mauvais caractère
! 1ère Heuristique: règle du mauvais caractère
Lorsqu’une discordance est détectée :
On déplace le motif pour que le caractère fautif dans le
texte soit aligné avec sa dernière apparition dans le motif
(s’il existe).
A G A G G C A T A C

A G G C A

A G G C A

$ Cas possibles :
- Si le caractère fautif n’apparaît pas du tout dans le motif
→ on peut sauter tout le motif.
- S’il apparaît plus tôt dans le motif → on aligne sur cette
position. 8
 Règle du mauvais caractère
⚙ Prétraitement – Règle du mauvais caractère
– ! Le déplacement optimal dépend uniquement du motif, pas du
texte.
– " Une table est calculée en prétraitement, basée sur l’alphabet
utilisé.

" Cette table indique, pour chaque caractère du motif, de

combien de positions on peut décaler le motif si ce caractère
provoque une discordance.

Motif: A G G C A

Table des mauvais A C G *

caractères : 4 1 2 5

9
 Règle du mauvais caractère (exemple)
Table des mauvais A C G *
Motif: A G G C A
caractères : 4 1 2 5

Texte : A G A T C A G G C A C

A G G C A
A G G C A
A G G C A
# Attention : le saut brut peut être trop grand
D’après la table, le saut proposé est de 5, car T n’apparaît pas dans le motif.

❗ Mais : le caractère fautif (T) ne se situe pas en fin de motif, mais au milieu.
→ Le saut brut fait passer à côté d’une potentielle correspondance.

% Ajustement du saut
➡ Il faut réduire le saut en tenant compte de la position du caractère fautif
dans le motif. 10
 Règle du mauvais caractère (exemple)
Table des mauvais A C G *
Motif: A G G C A
caractères : 4 1 2 5

Texte : A G A T C A G G C A

A G G C A

A G G C A

A G G C A (déplacement de 5-2=3)

A G G C A

11
 Algorithme de Boyer-Moore - Prétraitement

⚙ Algorithme pour construire la table des

mauvais caractères
ConstruireTableMauvais Caractère(M[1..m])
1. MC[1.. |S|] = m
2. pour i = m-1 à 1
3. si MC[M[i]] == m
4. MC[M[i]] = m-i
5. retourner MC
Σ ∶ ensemble des caractères possibles

# Ordre Asymptotique:
& O(|S|)

12
 Règle du bon suffixe
⚠ Limite de la règle du mauvais caractère
Parfois, cette règle ne propose pas le saut le plus long possible,
car elle ne tient pas compte de ce qui a déjà bien correspondu
dans le texte.
A G A A G A G A C T

C A G A G

C A G A G

# 2e heuristique – Règle du bon suffixe

Si une portion du motif (le suffixe) correspondait au
texte avant la discordance:
➡ On tente de replacer ce suffixe ailleurs dans le
motif pour éviter de tout recommencer.
$ Cela permet de recycler les correspondances
partielles,et de sauter plus loin que la règle du
mauvais caractère ne l’aurait permis. 13
 Règle du bon suffixe
! Exemple – Règle du bon suffixe
- Le suffixe AG correspond au texte.
- Mais il n’y a aucune autre occurrence de AG dans le motif.

A G G A G A G A C T

C A C A G

C A C A G
" Conséquence :
➡ On peut ignorer AG dans la suite de la recherche et décaler
le motif au-delà de cette portion, pour tester la prochaine
zone du texte.

# Ce cas illustre le saut maximal permis par la règle du bon suffixe

➡ très utile lorsque le motif ne contient pas de répétitions
internes.
14
 Règle du bon suffixe
' Suffixe qui est aussi un préfixe.
Une correspondance du suffixe GAG est trouvée dans le texte
Mais :
❌ GAG n’apparaît pas ailleurs dans le corps du motif.
✅ Une partie de GAG correspond à un préfixe du motif.
A A G A G G A G C T

A G G A G

A G G A G

! Conséquence :
- On ne peut pas décaler de 5,
- mais on peut décaler de 3 positions,
- pour aligner la fin du suffixe avec le début du motif (préfixe
correspondant).

15
 Règle du bon suffixe
Principe de la règle du bon suffixe:
On cherche à réutiliser le suffixe "cc", mais pas sur une
copie identique :
il faut que le caractère précédent soit différent de
celui qui a échoué.

Texte: ? ? ? ? X c c ? ? ?

Motif: Z c c Y c c avec Z ≠Y

En résumé:
✅Le suffixe « cc » correspond
⚠ Le caractère précédent doit être différent (Z ≠ Y)
! On cherche la prochaine occurrence de « cc »
dans le motif qui respecte cette contrainte. 16
 Prétraitement de la règle du bon suffixe
Prétraitement pour la règle du bon suffixe
Pour chaque suffixe de longueur 1 à M (où M est la longueur du motif) :
! On cherche à repositionner ce suffixe dans le motif, le plus à
gauche possible.
✅ Le caractère précédent le suffixe repositionné doit être différent
de celui qui précède le suffixe original.
Motif: A N P A N M A N
n suffixe Saut
1 N 1
2 AN 8
3 MAN 3
4 NMAN 6 Notez: X veut
5 ANMAN 6 dire précédé
6 PANMAN 6 par un autre
7 NPANMAN 6 symbole que X
8 ANPANMAN 6 17
 Algorithme de Boyer-Moore
⚙ Algorithme Boyer- Moore
BoyerMoore(T[1..N],M[1..m])
1. Liste = {}
2. BS[1..m] = ConstruireTableBonSuffixes(M)
3. MC[1..|Σ|] = ConstruireTableMauvaisCaractères(M)
4. i=1
5. tant que i ≤ n-m
$ Quel est l’ordre asymptotique?
6. j=m
% Meilleur cas: O(n/m + m + |Σ|)
7. tant que j>0 et T[i+j] == M[j]
& Pire cas: O(n*m + m + |Σ|)
8. j = j-1
Texte: a a a a a a a a a a a a
9. si j == 0
10. Liste = Liste U {i} Motif: a a a
11. i = i+1
12. sinon
13. i = i + Max(1,BS(j),MC(P[j]-j)
14. retourner Liste

18
 Algorithme de Boyer-Moore
Exercice:
#Appliquer l’algorithme de Boyer-Moore pour le texte et le
motif suivant:
Texte : Bess_knew_about_baobabs
Motif: baobab

$ Identifier
les étapes de comparaison et les décalages
proposés par Boyer-Moore.

[Levitin]

19
Tate : Bess-knew - about -
baobabs

Motif : ba ob a b
m = 6

Mauvais Caractères : Table des bons suffixes :

On compte à partir du début .

1. A est le length de No Sants ↑ étant le autre hose re

6 m
(ela que
=

& 51
ab >E
- ab ; on cherche caractère
jab5 précède de autre choser
que à.
donc Obab
bab5 Tu

/ aobab
Jaobab 3 >
-
Er : Tab ; best suffise et prefixe donc
saut de S :
bagal
Bess-knew - about -
baobabs
↑
b) a O b a b Osaut Selondon suff: 1saut son maurais caractère : 6 dans sart de 6
Ba ob a b ① BS 5 8 Mc 6 2 4
-
: :
- =

6 a ob à &
↓ OB M. baobab
 Ex 1 :

Texte :
AGC &2 + & (22 2122A212) -GAG)

Mot : A4((GAG

m = 8 n = 25

MC :

2548
Recherche dans les chaînes de caractères

ALGORITHME DE
KNUTH-MORRIS-PRATT
20
 Algorithme de Knuth-Morris-Pratt
! Objectif de l’algorithme KMP:
! Éviter les comparaisons inutiles
✅ On ne regarde pas chaque caractère du texte un par un.
" On effectue un prétraitement du motif à l’aide de la règle
du préfixe propre.
⚙ Ce prétraitement nous dit de combien reculer dans le motif
en cas de discordance.

! Concept de préfixe propre

! KMP utilise les plus longs préfixes propres
qui sont aussi suffixes.
" Un préfixe propre est un préfixe qui n’est ni
vide ni égal au motif complet.
21
 Aperçu de fonctionnement de KMP
A B C A B C D A B A B C D A B C D A B D E
A B C D A B D

La comparaison courante a causé une discordance.

– ❌ Le C et le D ne correspondent pas
– " Il faut donc déplacer le motif

22
 Aperçu de fonctionnement de KMP
A B C A B C D A B A B C D A B C D A B D E
A B C D A B D

La comparaison courante a causé une discordance.

– ❌ Le C et le D ne correspondent pas
– " Il faut donc déplacer le motif

– # Plutôt que de repartir à zéro, on se sert de ce qu'on a déjà vu : le

motif contient des répétitions qu’on peut exploiter.

23
 Aperçu de fonctionnement de KMP
A B C A B C D A B A B C D A B C D A B D E
A B C D A B D

La comparaison courante a causé une discordance.

– ❌ Le C et le D ne correspondent pas
– " Il faut donc déplacer le motif

– # Plutôt que de repartir à zéro, on se sert de ce qu'on a déjà vu : le

motif contient des répétitions qu’on peut exploiter.

On remarque que le suffixe de la partie qui correspond est aussi

préfixe du motif
– $ Ils’agit d’un préfixe propre
– % Le motif est déplacé afin d’aligner le préfixe propre avec le suffixe
qui correspond
– ⚙ Pour simplifier le calcul, la table des prefixes propres est calculée
en prétraitement

24
 Règle du préfixe propre
i

A B C A B C D A B A B C D A B C D A B D E
A B C D A B D

A B C D A B D

" Prétraitement pour construire k

Pour chaque position k, on détermine :
! PP[k] = longueur du plus long préfixe de P qui est aussi suffixe de P[1..k]
" Cette table permet, en cas de discordance, de savoir où reprendre la
comparaison dans le motif, sans tout recommencer.

!"#$%&#!"'("#[1. . ,]
A B C D A B D
0 0 0 0 1 2 0 25
 Règle du préfixe propre
⚙ Algorithme de prétraitement:
Calcul-Fonction-Préfixe( M[1..m])
1. Π [1] = 0 a b a b a c a
2. k=0
3. pour i = 2 à m
4. tant que k > 0 et M[k + 1] != M[i]
5. k = Π[k]
6. si M[k + 1] == M[i]
7. k = k+1
8. Π [i] = k i 1 2 3 4 5 6 7

9. retourner Π
p a b a b a c a

26
 Règle du préfixe propre
⚙ Algorithme de prétraitement:
Calcul-Fonction-Préfixe( M[1..m])
1. Π [1] = 0 a b a b a c a
2. k=0
k i
3. pour i = 2 à m
4. tant que k > 0 et M[k + 1] != M[i]
5. k = Π[k] # Étape 1: Π [1] = 0
6. si M[k + 1] == M[i]
7. k = k+1
8. Π [i] = k q 1 2 3 4 5 6 7

9. retourner Π
p a b a b a c a

Π 0

27
 Règle du préfixe propre
⚙ Algorithme de prétraitement:
Calcul-Fonction-Préfixe( M[1..m])
1. Π [1] = 0 a b a b a c a
2. k=0
k i
3. pour i = 2 à m
4. tant que k > 0 et M[k + 1] != M[i]
5. k = Π[k] # Étape 2: Π [2] = 0
6. si M[k + 1] == M[i]
7. k = k+1
8. Π [i] = k q 1 2 3 4 5 6 7

9. retourner Π
p a b a b a c a

Π 0 0

28
 Règle du préfixe propre
⚙ Algorithme de prétraitement:
Calcul-Fonction-Préfixe( M[1..m])
1. Π [1] = 0 a b a b a c a
2. k=0
k i
3. pour i = 2 à m
4. tant que k > 0 et M[k + 1] != M[i]
5. k = Π[k] # Étape 3: k=1
6. si M[k + 1] == M[i] Π [3] = 1
7. k = k+1
8. Π [i] = k q 1 2 3 4 5 6 7

9. retourner Π
p a b a b a c a

Π 0 0 1

29
 Règle du préfixe propre
⚙ Algorithme de prétraitement:
Calcul-Fonction-Préfixe( M[1..m])
1. Π [1] = 0 a b a b a c a
2. k=0
k i
3. pour i = 2 à m
4. tant que k > 0 et M[k + 1] != M[i]
5. k = Π[k] # Étape 4: k=2
6. si M[k + 1] == M[i] Π [4] = 2
7. k = k+1
8. Π [i] = k q 1 2 3 4 5 6 7

9. retourner Π
p a b a b a c a

Π 0 0 1 2

30
 Règle du préfixe propre
⚙ Algorithme de prétraitement:
Calcul-Fonction-Préfixe( M[1..m])
1. Π [1] = 0 a b a b a c a
2. k=0
k i
3. pour i = 2 à m
4. tant que k > 0 et M[k + 1] != M[i]
5. k = Π[k] # Étape 5: k=3
6. si M[k + 1] == M[i] Π [5] = 3
7. k = k+1
8. Π [i] = k q 1 2 3 4 5 6 7

9. retourner Π
p a b a b a c a

Π 0 0 1 2 3

31
 Règle du préfixe propre
⚙ Algorithme de prétraitement:
Calcul-Fonction-Préfixe( M[1..m])
1. Π [1] = 0 a b a b a c a
2. k=0
k i
3. pour i = 2 à m
4. tant que k > 0 et M[k + 1] != M[i]
5. k = Π[k] # Étape 6: k=1
6. si M[k + 1] == M[i]
7. k = k+1
8. Π [i] = k q 1 2 3 4 5 6 7

9. retourner Π
p a b a b a c a

Π 0 0 1 2 3

32
 Règle du préfixe propre
⚙ Algorithme de prétraitement:
Calcul-Fonction-Préfixe( M[1..m])
1. Π [1] = 0 a b a b a c a
2. k=0
k i
3. pour i = 2 à m
4. tant que k > 0 et M[k + 1] != M[i]
5. k = Π[k] # Étape 7: k=0
6. si M[k + 1] == M[i] Π [6] = 0
7. k = k+1
8. Π [i] = k q 1 2 3 4 5 6 7

9. retourner Π
p a b a b a c a

Π 0 0 1 2 3 0

33
 Règle du préfixe propre
⚙ Algorithme de prétraitement:
Calcul-Fonction-Préfixe( M[1..m])
1. Π [1] = 0 a b a b a c a
2. k=0
k i
3. pour i = 2 à m
4. tant que k > 0 et M[k + 1] != M[i]
5. k = Π[k] # Étape 8: k=1
6. si M[k + 1] == M[i] Π [7] = 1
7. k = k+1
8. Π [i] = k q 1 2 3 4 5 6 7

9. retourner Π
p a b a b a c a

Π 0 0 1 2 3 0 1

34
 Algorithme de Knuth-Morris-Pratt
⚙ Algorithme Knuth-Morris-Pratt:
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
2. q=0
3. pour i = 1 à n
4. tant que q > 0 et M[q + 1] != T[i]
5. q = Π[q]
6. si M[q + 1] == T[i]
7. q = q+1
8. si q == m // Motif trouvé
9. afficher M
10. q = Π[q]

35
 Algorithme de Knuth-Morris-Pratt
Exemple:
Texte : T
b a c b a b a b a b a c a c a

Motif: M
a b a b a c a

Table des préfixes propres :

k 1 2 3 4 5 6 7

p a b a b a c a

Π 0 0 1 2 3 0 1

36
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que k > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 1: i = 1, i = 0 9. afficher M
10. k = Π[k]
compare M[1] avec T[1]
i

b a c b a b a b a b a c a a b

a b a b a c a

k
M[1] différent T[1]. On incrémente i=> ‘M’ se déplace d’une position à droite.

37
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que k > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 2: i = 2, k = 0 9. afficher M
10. k = Π[k]
compare M[1] avec T[2]
i

b a c b a b a b a b a c a a b

a b a b a c a

k
M[2] = T[1]. On incrémente i et k

38
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que k > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 3: i = 3, k = 1 9. afficher M
10. k = Π[k]
compare M[2] avec T[3]
i

b a c b a b a b a b a c a a b

a b a b a c a

k
M[2] différent T[3]. k devient 0 => ‘M’ se déplace de deux positions à droite.

39
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que k > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 4: i = 4, k = 0 9. afficher M
10. k = Π[k]
compare M[1] avec T[4]
i

b a c b a b a b a b a c a a b

a b a b a c a

k
M[1] différent T[4]. On incrémente i=> ‘M’ se déplace d’une position à droite

40
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que k > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 5: i = 5, k = 0 9. afficher M
10. k = Π[k]
compare M[1] avec T[5]
i

b a c b a b a b a b a c a a b

a b a b a c a

k
M[1] = T[5]. On incrémente i et k

41
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que k > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 6: i = 6, k = 1 9. afficher M
10. k = Π[k]
compare M[2] avec T[6]
i

b a c b a b a b a b a c a a b

a b a b a c a

k
M[2] = T[6]. On incrémente i et k

42
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que k > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 7: i = 7, k = 2 9. afficher M
10. k = Π[k]
compare M[3] avec T[7]
i

b a c b a b a b a b a c a a b

a b a b a c a

k
M[3] = T[7]. On incrémente i et k

43
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que k > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 8: i = 8, k = 3 9. afficher M
10. k = Π[k]
compare M[4] avec T[8]
i

b a c b a b a b a b a c a a b

a b a b a c a

k
M[4] = T[8]. On incrémente i et k

44
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que k > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 9: i = 9, k = 4 9. afficher M
10. k = Π[k]
compare M[5] avec T[9]
i

b a c b a b a b a b a c a a b

a b a b a c a

k
M[5] = T[9]. On incrémente i et k
45
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que k > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 10: i = 10, k = 5 9. afficher M
10. k = Π[k]
compare M[6] avec T[10]
i

b a c b a b a b a b a c a a b

a b a b a c a

k
M[6] est différent de T[10]. k devient 3 => ‘M’ se déplace de 2 positions à droite)

46
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que k > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 10: i = 10, k = 3 9. afficher M
10. k = Π[k]
compare M[4] avec T[10]
i

b a c b a b a b a b a c a a b

a b a b a c a

k
M[5] = T[10]. On incrémente i et k

47
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que k > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 11: i = 11, k = 4 9. afficher M
10. k = Π[k]
compare M[5] avec T[11]
i

b a c b a b a b a b a c a a b

a b a b a c a

k
M[5] = T[11]. On incrémente i et k

48
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que k > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 12: i = 12, k = 5 9. afficher M
10. k = Π[k]
compare M[6] avec T[12]
i

b a c b a b a b a b a c a a b

a b a b a c a

k
M[6] = T[12]. On incrémente i et k

49
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 13: i = 13, k = 6 9. afficher M
10. k = Π[k]
compare M[7] avec T[13]
i

b a c b a b a b a b a c a a b

a b a b a c a

k
M[7] = T[13]. On incrémente i et k

50
 Algorithme de Knuth-Morris-Pratt
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
k 1 2 3 4 5 6 7 2. k=0
3. pour i = 1 à n
p a b a b a c a 4. tant que k > 0 et M[k + 1] != T[i]
Π 0 0 1 2 3 0 1 5. k = Π[k]
6. si M[k + 1] == T[i]
7. k = k+1
8. si k == m // Motif trouvé
# Étape 13: i = 13, k = 7 9. afficher M
10. k = Π[k]
k = m => Motif trouvé
i

b a c b a b a b a b a c a a b

a b a b a c a

51
 Algorithme de Knuth-Morris-Pratt
⚙ Algorithme Knuth-Morris Pratt:
KMP( T[1..n],M[1..m])
1. Π = Calcul-Fonction-Prefix(M)
2. q=0
3. pour i = 1 à n
4. tant que q > 0 et M[q + 1] != T[i]
5. q = Π[q]
6. si M[q + 1] == T[i]
7. q = q+1
8. si q == m // Motif trouvé
9. afficher M
10. q = Π[q]

$ Quel est l’ordre asymptotique?

# O(n+m)
52
Recherche dans les chaînes de caractères

ALGORITHME DE
RABIN-KARP
53
 Rabin-Karp
! Principe de l’algorithme Rabin-Karp
L’algorithme utilise une technique de hachage pour détecter
rapidement les endroits où le motif pourrait apparaître dans
le texte.

! Tous les caractères sont convertis en chiffres en base d.

! On calcule une valeur de hachage (h-code) pour :
• le motif
• chaque sous-séquence de longueur m du texte.
! Si les hachages sont différents, on passe à la sous-
séquence suivante.
! Si les hachages sont identiques, on effectue une
comparaison caractère par caractère.
! Pour éviter les débordements, les hachages sont
toujours pris modulo un nombre premier q.

54
 Algorithme Rabin-Karp
Texte:
2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

Motif:
3 1 4 1 5

" Au lieu de comparer les caractères un à un, on traite le motif

comme un nombre.

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

23590 ≠ 31415

55
 Algorithme Rabin-Karp
Texte:
2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

Motif:
3 1 4 1 5

Au lieu de comparer les caractères, on considère le motif comme un

nombre.

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

35902 ≠ 31415

56
 Algorithme Rabin-Karp
Texte:
2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

Motif:
3 1 4 1 5

Au lieu de comparer les caractères, on considère le motif comme un

nombre.

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

59023 ≠ 31415

57
 Algorithme Rabin-Karp
Texte:
2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

Motif:
3 1 4 1 5

Au lieu de comparer les caractères, on considère le motif comme un

nombre.

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

90231 ≠ 31415

58
 Algorithme Rabin-Karp
Texte:
2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

Motif:
3 1 4 1 5

Au lieu de comparer les caractères, on considère le motif comme un

nombre.

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

2314 ≠ 31415

59
 Algorithme Rabin-Karp
Texte:
2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

Motif:
3 1 4 1 5

Au lieu de comparer les caractères, on considère le motif comme un

nombre.

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

23141 ≠ 31415

60
 Algorithme Rabin-Karp
Texte:
2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

Motif:
3 1 4 1 5

Au lieu de comparer les caractères, on considère le motif comme un

nombre.

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

31415 = 31415

61
 Algorithme Rabin-Karp
2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

31415

❓ Comment éviter de recalculer toute la valeur du texte à

chaque décalage ?

" # Une fenêtre glissante est utilisée

on retire la contribution du premier caractère, on ajoute
le suivant, et on met à jour en temps constant.

14152 = (31415 – 3 * 10000) * 10 + 2

= (1415) * 10 + 2
= 14150 + 2
62
 Rabin-Karp - Quelques formules utiles
2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

$ Supposons une chaîne de caractères T[1..n] et un motif M[1..m].

% On peut représenter chaque sous-chaîne T[i..i+m-1] comme un

nombre en base b :
!! = #" $ % & + ( − 1 + ## $ % & + ( − 2 + ⋯ + #$%# $ % &

⏩ Le motif est décalé dans le texte en appliquant l’opération suivante:

!!&# = # $ (!! − #$%# $ % & ) + % & + (

Décale le motif Élimine le nombre le Additionne le nombre le

de un élément plus à gauche plus à droite

⚙ Grâce à une formule de mise à jour, on évite de tout recalculer à

63
chaque décalage du motif.
 Algorithme Rabin-Karp
2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

❓ Si on connaît le h-code de 31415 modulo q, peut-on s’en servir pour

calculer celui de 14152?
" Autrement dit : peut-on dériver le code suivant à partir de celui déjà connu ?

.!"# = (1 2 .! − 4 % 2 1$%# mod 8 + T[i+m]) mod q

Décale le motif de Enlève le nombre le Additionne le nombre
un élément plus à droite. le plus à gauche
Exemple:

3 1 4 1 5 2 14152 = [10*(31415 - 3*10000)+2] % 13

= [10*(7-3*3)+2)] % 13
= 8 % 13
64
7 8
 Rabin-Karp - exemple
Exemple en utilisant h-code = mod(13)
Recherche du motif : 31415 = 7 mod (13)
2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1

8 9 3 11 0 1 7 8 4 5 10 11 7 9 11
Bonne Mauvaise
correspondance correspondance

[CLRS]

65
 Algorithme de Rabin-Karp
⚙ Algorithme Rabin-Karp:
Rabin-Karp( T[1..n],M[1..m],d,q)
1. h = dm-1 mod q
2. p=0
3. t =0
4. pour i = 1 à m
5. p = (d*p + M[i]) mod q
6. t = (d*t) + T[i]) mod q
7. pour i = 1 à n-m
8. si p == t
9. si M[1..m] == T[i..i+m-1] // Motif trouvé
10. afficher “Motif trouvé à s”
11. si i < n-m
12. t = (d*(t-T[i]*h) + T[i+m]) mod q

$ Quel est l’ordre asymptotique?

O(n+m)
66
Comparaison des algorithmes

⚙ Algorithme $ Complexité " Espace

$ Meilleur cas % Pire cas Mémoire

Naïf O(n) O(n*m) O(1)

Boyer-Moore O(n/m+m+|&|) O(n*m+m+|&|) O(m+|&|)
Knuth-Morris-Pratt O(n+m) O(n+m) O(n)
Rabin-Karp O(n) O(n+m) O(1)

❓ Lequel est le plus efficace?

67
Recherche dans les chaînes de caractères

Distance d’édition minimale

68
 À quel point deux chaînes sont similaires?
' Correction de l’orthographe ( Bio-informatique
Le mot écrit est « graffe » Alignement de séquences de nucléotides
Lequel est le plus proche?
• graff AGGCATATTGCGGATAAGTAGG
• greffe ATGGTATATTGGATGAGCGTACG
• giraffe
• gaffé
) Alignement possible:
• gaffe

A- GGCATATTGCGGATAA - - GTAGG
* Autres applications:
ATGGTATATTG - - GATGAGCGTACG
• Traduction automatique
• Reconnaissance de la parole
• Extraction d’information

69
 Recherche approximative de chaînes

$ Concept de distance d’édition

% La distance entre deux chaînes correspond au
nombre minimum de transformations à effectuer
pour passer de l’une à l’autre.
& Chaque transformation a un coût, et on cherche la
suite la moins coûteuse.
' Distance de Levenshtein
Nombre minimal d’opérations nécessaires :
✏ Substitution
➕ Insertion
❌ Suppression

70
 Distance d’édition minimale (exemple)
Considérer les séquences de nucléotides suivantes:
AGC
AGGC

Un alignement possible est:

AG–C
| | |
AGGC

Pour évaluer le coût d’un alignement, nous pouvons utiliser les coûts suivants:
➕ Insertion -2
❌ Suppression -2
✏ Substitution -1
✅ Correspondance 1
Donc l’alignement aurait un coût de 1+1-2+1=1.

71
 Distance d’édition minimale (exemple)
+ Initialisation Insertion du symbole
s1 par rapport à S1 .
Aucun symbole de S2,
Φ A G C
le A de S1 est utilisé
Φ 0 -2 -4 -6

A -2
s2 G -4

G -6
Suppression du symbole
C -8
par rapport à S1 .
➕ Insertion -2 Aucun symbole de S1,
❌ Suppression -2 le A de S2 est utilisé
✏ Substitution -1
✅ Correspondance 1 72
 Distance d’édition minimale (exemple)
➕ Insertion -2
, Remplir la matrice D(i,j): ❌ Suppression -2
Transformation: ✏ Substitution -1
s1
Le A de S1 et celui ✅ Correspondance 1
Φ A G C
de S2 sont utilisés.
Φ 0 -2 -4 -6
Suppression:
Aucun symbole de S1,
A -2 le A de S2 est utilisé
s2 G -4

G -6

C -8
Insertion:
Aucun symbole de S2,
le A de S1 est utilisé
73
 Distance d’édition minimale (exemple)
➕ Insertion -2
, Remplir la matrice D(i,j): ❌ Suppression -2
✏ Substitution -1
s1
✅ Correspondance 1
Φ A G C

Φ 0 -2 -4 -6

A -2 1 -4
-4
s2 G -4

G -6

C -8

74
 Distance d’édition minimale (exemple)
➕ Insertion -2
, Remplir la matrice D(i,j): ❌ Suppression -2
✏ Substitution -1
s1
✅ Correspondance 1
Φ A G C

Φ 0 -2 -4 -6

A -2 1
s2 G -4 #
%
% D(i −1, j) + coût d'insertion
G -6 %
%
D(i, j) = max $ D(i, j −1) + coût de suppression
%
C -8 % #% substitution si S (i) ≠ S ( j)
1 2
% D(i −1, j −1) + $
% %& correspondance si S 1 (i) = S 2 ( j)
&

75
 Distance d’édition minimale (exemple)
➕ Insertion -2
, Remplir la matrice D(i,j): ❌ Suppression -2
✏ Substitution -1
s1
✅ Correspondance 1
Φ A G C

Φ 0 -2 -4 -6

A -2 1 -1 -3
s2 G -4 -1 2 0

G -6 -3 0 1

C -8 -5 -2 1

76
 Distance d’édition minimale (exemple)
- Retrouver l’alignement (séquence d’édition)
s1
Φ A G C

Φ 0 -2 -4 -6

A -2 1 -1 -3
s2 G -4 -1 2 0

G -6 -3 0 1

C -8 -5 -2 1

77
 Distance d’édition minimale (exemple)
- Retrouver l’alignement (séquence d’édition)

s1 Deux alignements possibles:

Φ A G C AG–C A–GC
Φ 0 -2 -4 -6 | | | | | |
AGGC AGGC
A -2 1 -1 -3
s2 G -4 -1 2 0

G -6 -3 0 1

C -8 -5 -2 1

78