La lecture en ligne est gratuite
Télécharger
IF4-ALGO2 Algorithmique linéaire
et
autres.
Notes rédigées par Dartiguelongue Gilles
1
er
avril 2006
Table des matières
TABLE DES MATIÈRES
I Recherches de motifs 5 1 Recherche de motifs 7 1.1 Algorithme naïf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Algorithme pas si naïf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Approche par automates finis . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Recherche par Automate Fini (RAF) . . . . . . . . . . . . . . . . . . . . . . 9 1.4.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4.2 Construction de l’automate et preuve . . . . . . . . . . . . . . . . . 9 1.4.3 Signification des états . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4.4 Construction de l’automate . . . . . . . . . . . . . . . . . . . . . . . 10 1.4.5 Preuve de l’algorithme RAF et construction de δ . . . . . . . . . . . 10 1.4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4.7 Calcul effectif de delta . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5 Algorithme KMP (Knuth-Morris-Pratt) . . . . . . . . . . . . . . . . . . . . 12 1.6 Algorithme MP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.6.1 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.7 Construction de F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Traitement de séquences
Page 3
TABLE
Page
4
DES
MATIÈRES
Première
Recherches
partie
de
motifs
Page
5
Chapitre 1
Recherche de motifs
CHAPITRE 1. RECHERCHE DE MOTIFS
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
ORÈME1.4x),a)THÉti[T05.1.)(ost0eA?xφ(t:=q)=)ax(φ(δa,(φ,AurlalpoatndétrecendiametuaotnmMue,xtteun1]nnoitcnofalφ.fitonoA:7?Quq,itàuotmotx,associelétatφlanledotuatematuesfonetinctrarvaiometotiléusprx.Plemenécisq)x(φtatniettauomutatlèspreaatxfuxederac)saqMσa)xaM(iσssMqM(iaosanuanoedMσm)rdéniti(Mqa)(paédnoitcnofaL.ineatomutna)u,δ,F,Q0q(=,AioRtaxS)=σM(Mqa)cσM(adon1(q+mmle)Se1qsiM=rtix(Mσod)arcnMqasufxedexa.SoMcsqfuxdexeodcn2)meem(lσMr<ncdofusrMcn.aqMedexexaaxedetdolorsdexefuxsrfueaMtamotual)a,inet{zi|(T=σmmlear}pyhop3etederehtsèrencécurσ(Tiea)=)1+iT=)sn(φoposS)pu=σ(q0=0()==,φ)aiT(σ=)1+iT(φ,1i+=TtaoiqS)=Tiσ((φiT1+=)afludtφe,a)pardé=δ(φ(Ti)itcuednoocrartsnq|(M}p{zq,δ(=σa)itprdénemmeécédehedehcrqleu(Met(I,φ1]ni)(T=σi):ano,)tn0[irterlapreuveenefoNsulaolsnnepaopncreuresi=i.T00,tceftnaurenurucé
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]
CHAPITRE 1. RECHERCHE DE MOTIFS
is?AMσ=qa)x(srola3),AA?xM,HCME]A=qMσx(d)noσM(xa)=σM(Mqa)[SMEEML.5(3.1.4