INFO-4xx-ALGO2-Notes de cours

Description

IF4 ALGO2Algorithmiquelinéaireetautres.NotesrédigéesparDartiguelongueGilleser1 avril2006TABLEDESMATIÈRESTabledesmatièresI Recherchesdemotifs 51 Recherchedemotifs 71.1 Algorithmenaïf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2passinaïf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3 Approcheparautomatesfinis . . . . . . . . . . . . . . . . . . . . . . . . . . 81.4 RechercheparAutomateFini(RAF) . . . . . . . . . . . . . . . . . . . . . . 91.4.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.4.2 Constructiondel’automateetpreuve . . . . . . . . . . . . . . . . . 91.4.3 Significationdesétats . . . . . . . . . . . . . . . . . . . . . . . . . . 101.4.4 Constructiondel’automate . . . . . . . . . . . . . . . . . . . . . . . 101.4.5 Preuvedel’algorithmeRAFetconstructiondeδ . . . . . . . . . . . 101.4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.4.7 Calculeffectifdedelta . . . . . . . . . . . . . . . . . . . . . . . . . . 111.5 AlgorithmeKMP(Knuth Morris Pratt) . . . . . . . . . . . . . . . . . . . . 121.6MP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.6.1 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.7 ConstructiondeF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13TraitementdeséquencesPage3TABLEDESMATIÈRESPage4PremièrepartieRecherchesdemotifsPage5CHAPITRE1. ...

Informations

• Publié par: Ormo
• Nombre de lectures: 38
• Langue: Français

Extrait

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ÈME 1.4 x),a) T HÉ ti[T∙0∙∙ 5.1.)( os t∀ 0 eA ? x∈φ(t:=q)=)ax(φ(δ∈a∀,(φ,A url’alpoatfind’ét r e ce nfidiametuaotnmMue,xtteun1]n−noitcnofalφ.fito noA:7 ? Q→uq,itàuotmotx,associel’é fitatφlan’ledotuatemat u es fonetinc trarvaiometotiléusprx.Plemenécis q)x(φtatnietta’uomut’atlèspreaat xfifuxederac)sa q M≤σa)xa M (iσssM qM (iaosanua noed M σ m )rdéfiniti(M q a)(pa é’dnoitcnofaL.inefiatomutna)u,δ,F,Q 0 q(=,AioRt ax S )=σ M (M q a)cσ M (adon 1(q+mmle)Se1 q siM =rtix( M σod)a ≤r cnM q asuffixedexa.SoMcs q fuxfidexeodcn 2)meem(lσ M r<ncdo fifus r Mcn .a q M edexexaafixedetdolorsdexefuxfis r fueaMt amotua’l )a, infiet {z i | (T=σ mmlear } pyhop3etederehtsèrencécur σ(T i e a)=) 1+ i T=)sn(φoposS ) pu =σ(q 0 =0()==,φ )a i T(σ=) 1+i T(φ, 1i+ =Ttaoi q S )=T i σ( (φ i T 1+ =) afludtφe,a)pardé=δ(φ(T i ) itcuednoocrartsn q | (M } p {z q,δ(=σa) itprdéfinemmeécédehedehcrqleu(Met (I,φ1]n− i )(T=σ i ) :ano,)tn ∙∙∙0[∈i∀ rterlapreuveenefoNsulaolsnnepaopncreures i= i. T 0 0, 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 ? A M σ=qa)x(srol∀a 3) ,∀∈AA ? x∈M∈,∀ HCME]A =q M σx(d)no σ M (xa)=σ M (M q a) [S MEEM L.5(3.1.4