Problème : – soit A un alphabet (ensemble fini de symboles) – T ∈ A ? séquence ou "texte" – M ∈ A ? "motif", avec | M | < | T | Exemple :
0 1 2 3 4 5 6 7 8 9 10 11 T = a a b a c a a b b a c a M = b a c
On recherche les occurences de M dans T et plus précisement, les indices k tels que ∀ i = { 0 ∙ ∙ ∙ m − 1 } , M [ i ] = T [ k + i ] avec m = | M | . Ici, la solution est { 2 , 8 } .
1.1 Algorithme naïf
On va tout d’abord essayer la manière directe : la force brute. Données T , M , n = card ( T ) , m = card ( M ) .
Pour k=0 à n-m; faire i=0; Tant que (i<m) et (T[k+i]==M[i]) i++; si (i==m) afficher(k); Fin tant que Fin pour
Page 7
CHAPITRE 1. RECHERCHE DE MOTIFS
La complexité de cet algorithme est en O ( n ∗ m ) . Le pire cas pour cet algorithme est celui ou T = a ∙ ∙ ∙ a et M = a ∙ ∙ ∙ a
1.2 Algorithme pas si naïf
Considérons le cas particulier où on suppose que les caractères du motif sont tous distincts. On élabore alors le nouvel algorithme suivant : Données T , M , n = | T | , m = | M | .
k=0 Tant que k<=n-m Tant que (k<=n-m) et (T[k+i]==M[i]) i++; si (i==m) afficher(k); k = k+i; Fin tant que Fin tant que
1.3 Approche par automates finis
L’idée est de construire un automate à partir du motif et d’utiliser cet automate pour filtrer le texte. Le problème qui se pose alors est de construire l’automate. Prenons un exemple relativement simple. Soit le mot à reconnaître M = ababaca , on peut voir l’auto-mate reconnaissant M sur la figure 1.1 . Les transitions qui ne figurent pas sur le schéma renvoient à l’état 0.
0 1 2 3 4 5 6 7 a 1 1 3 1 5 1 7 1 b 0 2 0 4 0 4 0 2 c 0 0 0 0 0 6 0 0 Notations : – AF = ( Q, q 0 , F, A, δ ) Page 8
– A l’alphabet – Q ensemble des états ( Q = { 0 ...m } ) – q 0 état initial q 0 = 0 – F ensemble des états terminaux F = { n } – δ fonction de transition Q × A 7→ Q
CHAPITRE 1. RECHERCHE DE MOTIFS
F IG . 1.1 – Automate fini de reconnaissance du motif M = ababaca
1.4 Recherche par Automate Fini (RAF)
1.4.1 Algorithme
Données : T , n , m , δ .
q=0 pour i de 0 à n-1; faire q = δ ( q, T[i] ) si q==m alors afficher(i-m); fin pour
1.4.2 Construction de l’automate et preuve
Rappels : Soient ( x, y ) ∈ A ? – x facteur de y si ∃ u, v ∈ A ? /y = uxv – x préfixe de y si ∃ v ∈ A ? /y = xv – x suffixe de y si ∃ u ∈ A ? /y = ux Soit T ∈ A ? , on note T r = T [0 ∙ ∙ ∙ n − 1] le préfixe de T de longueur r .
Page 9
CHAPITRE 1. RECHERCHE DE MOTIFS
1.4.3 Signification des états L’état courant est 4 implique que les 4 derniers caractères de T correspondent aux 4 premiers caractères de M . Autrement dit, M 4 est suffixe de T k . De plus, M 4 est le plus grand préfixe de M qui soit suffixe de T . Définition : Soit M ∈ A ? , on définit σ M : A ? 7→ { 0 ∙ ∙ ∙ m } ∀ x ∈ A ? , σ M ( x ) = max { i/M i suf f ixe de x } σ M ( x ) est la longueur du plus long préfixe de M qui est en un suffixe de x . Exemple : M = ab σ M ( ) = 0 σ M ( ccaca ) = 1 σ M ( ccab ) = 2 . Propriétés : ( n = | M | ) – σ M ( x ) = m ⇔ M suffixe de x – x suffixe de y ⇒ σ M ( x ) ≤ σ M ( y )
1.4.4 Construction de l’automate
Exemple :
∀ q ∈ Q, ∀ a ∈ A, δ ( q, a ) = σ M ( M q a )
δ (2 , a ) = σ M ( M 2 a ) = σ M ( aba ) = 3 δ (2 , b ) = σ M ( M 2 b ) = σ M ( aab ) = 0 δ (5 , b ) = σ M ( M 5 b ) = σ M ( | ab { a z ba } b ) = 4 M 5
1.4.5 Preuve de l’algorithme RAF et construction de δ L EMME 1.4.5.1 (1) ∀ M ∈ A ? , ∀ a ∈ A, ∀ x ∈ A ? σ M ( xa ) ≤ σ M ( x ) + 1 [SCHEMA] Si r = 0 alors 0 < σ M ( x ) + 1 (car ∀ x, σ M ( x ) ≥ 0 ). Sinon M r est suffixe de xa donc M r suffixe de x , or σ M ( x ) = plus grand k tel M k suffixe de r ⇒ r − 1 ≤ T M ( x ) L EMME 1.4.5.2 (2) ∀ x, y, w ∈ A ? si x suffixe de w et y suffixe de w et si | x | ≤ | y | alors x suffixe de y . [SCHEMA] Page 10
1.4.6 Conclusion Si l’automate fini rentre dans l’état q , q est la plus grande valeur telle que M q est suffixe de T i . Donc chaque fois qu’on entrera dans l’état q = m , on aura reconnu une occurence du motif (et seulement dans ce cas). La méthode (RAF + construction AF) est donc correcte.
Page 11
1.4.7 Calcul effectif de delta Regardons l’algorithme naïf de construction de δ . Données : A , M , m = | M | , résultat δ [AJOUTER LES COMPLÉXITÉS]