12 pages

Français

IN101 - cours 06 - 16 octobre 2009

Suen - Matthieu Finiasz

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

12 pages

Français

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

A propos
Informations
Extrait

Description

Un probl`eme concretUtilisation de ﬁchiers de logDes logs de serveur web ressemblent `a cela :IN 101 - Cours 06127.0.0.1 - - [13/Oct/2010:09:40:02 +0000] "GET /server-status?auto HTTP/1.1" 200 439 "-" "libwww-perl/5.836"182.46.10.154 - - [13/Oct/2010:09:40:07 +0000] "POST /m HTTP/1.1" 200 20 "http://site.com/" "Mozilla/5.0 (Windows; U;Windows NT 6.0; fr; rv:1.9.1.13) Gecko/20100914 Firefox/3.5.13 ( .NET CLR 3.5.30729; .NET4.0C)" - - [13/Oct/2010:09:40:08 +0000] "POST /m HTTP/1.1" 200 854 "http://site.com/" (Windows; U;14 octobre 2011Windows NT 6.0; fr; rv:1.9.1.13) Firefox/3.5.13 ( .NET CLR .NET4.0C)"182.53.208.200 - - [13/Oct/2010:09:40:27 +0000] "POST /m HTTP/1.1" 200 1112 "http://site.com/" "Mozilla/5.0 (Windows; U;Windows NT 5.1; fr; rv:1.9.2.10) Gecko/20100914 Firefox/3.6.10"182.46.10.154 - - [13/Oct/2010:09:41:07 +0000] "GET /gt?tb=676&a=head HTTP/1.1" 200 9462 "http://site.com/" "Mozilla/5.0 (Windows; U;Windows NT 6.0; fr; rv:1.9.1.13) Firefox/3.5.13 ( .NET CLR 3.5.30729; .NET4.0C)"184.7.230.122 - - [13/Oct/2010:10:42:24 +0000] "GET /thumb?i=13622448 HTTP/1.1" 200 6805 "Mozilla/5.0 (Windows; U;Windows NT 5.1; fr; rv:1.9.2.10) Gecko/20100914 Firefox/3.6.10 GTB7.1 ( .NET CLR 3.5.30729)" - - +0000] "GET /thumb?i=13622349 HTTP/1.1" 200 7094 "http://site.com/" "Mozilla/5.0 (Windows; U;Windows NT 5.1; fr; rv:1.9.2.10) Firefox/3.6.10 GTB7.1 ( .NET CLR 3.5.30729)"184.7.230.122 - - [13/Oct/2010:10:48:35 +0000] "GET /m ...

Informations

Publié par	Suen
Nombre de lectures	12
Langue	Français

Extrait

Des

logs

serveur

101

web

Cours

octobre

2011

pr´esent´epar Matthieu Finiasz

ressemblent

cela

Unprobl`emeconcret Utilisation de ﬁchiers de log

On veut pouvoir facilement eteﬃcacementtrouver : les lignes contenant une adresse IP, lesadressesIPayantacc´ed´e`aunepagedonne´e, laproportionderequeˆtesutilisantLinux... dans un ﬁchier de plusieurs millions de lignes. La commandegreppermet de faire cela, mais comment ?

Des

logs

serveur

web

ressemblent

cela

Unproble`meconcret Utilisation de ﬁchiers de log

127.0.0.1 - - [13/Oct/2010:09:40:02 +0000] "GET /server-status?auto HTTP/1.1" 200 439 "-" "libwww-perl/5.836" 182.46.10.154 - - [13/Oct/2010:09:40:07 +0000] "POST /m HTTP/1.1" 200 20 "http://site.com/" "Mozilla/5.0 (Windows; U; Windows NT 6.0; fr; rv:1.9.1.13) Gecko/20100914 Firefox/3.5.13 ( .NET CLR 3.5.30729; .NET4.0C)" 182.46.10.154 - - [13/Oct/2010:09:40:08 +0000] "POST /m HTTP/1.1" 200 854 "http://site.com/" "Mozilla/5.0 (Windows; U; Windows NT 6.0; fr; rv:1.9.1.13) Gecko/20100914 Firefox/3.5.13 ( .NET CLR 3.5.30729; .NET4.0C)" 182.53.208.200 - - [13/Oct/2010:09:40:27 +0000] "POST /m HTTP/1.1" 200 1112 "http://site.com/" "Mozilla/5.0 (Windows; U; Windows NT 5.1; fr; rv:1.9.2.10) Gecko/20100914 Firefox/3.6.10" 182.46.10.154 - - [13/Oct/2010:09:41:07 +0000] "GET /gt?tb=676&a=head HTTP/1.1" 200 9462 "http://site.com/" "Mozilla/5.0 (Windows; U; Windows NT 6.0; fr; rv:1.9.1.13) Gecko/20100914 Firefox/3.5.13 ( .NET CLR 3.5.30729; .NET4.0C)" 184.7.230.122 - - [13/Oct/2010:10:42:24 +0000] "GET /thumb?i=13622448 HTTP/1.1" 200 6805 "http://site.com/" "Mozilla/5.0 (Windows; U; Windows NT 5.1; fr; rv:1.9.2.10) Gecko/20100914 Firefox/3.6.10 GTB7.1 ( .NET CLR 3.5.30729)" 184.7.230.122 - - [13/Oct/2010:10:42:24 +0000] "GET /thumb?i=13622349 HTTP/1.1" 200 7094 "http://site.com/" "Mozilla/5.0 (Windows; U; Windows NT 5.1; fr; rv:1.9.2.10) Gecko/20100914 Firefox/3.6.10 GTB7.1 ( .NET CLR 3.5.30729)" 184.7.230.122 - - [13/Oct/2010:10:48:35 +0000] "GET /m?_=1286966914300&mt=feed&f=a_refresh&tm=1286966735&mid=5228&mid=5202&mid=5246&m 184.7.230.122 - - [13/Oct/2010:10:48:35 +0000] "POST /m HTTP/1.1" 200 695 "http://site.com/" "Mozilla/5.0 (Windows; U; Windows NT 5.1; fr; rv:1.9.2.10) Gecko/20100914 Firefox/3.6.10 GTB7.1 ( .NET CLR 3.5.30729)" 182.53.208.200 - - [13/Oct/2010:11:25:05 +0000] "POST /m HTTP/1.1" 200 1038 "http://site.com/" "Mozilla/5.0 (Windows; U; Windows NT 5.1; fr; rv:1.9.2.10) Gecko/20100914 Firefox/3.6.10" 184.7.230.122 - - [13/Oct/2010:11:25:35 +0000] "POST /m HTTP/1.1" 200 689 "http://site.com/" "Mozilla/5.0 (Windows; U; Windows NT 5.1; fr; rv:1.9.2.10) Gecko/20100914 Firefox/3.6.10 GTB7.1 ( .NET CLR 3.5.30729)" 191.21.9.195 - - [13/Oct/2010:11:42:22 +0000] "GET /fav?i=4102 HTTP/1.1" 304 - "http://site.com/" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.10) Gecko/20100914 Firefox/3.6.10" 191.21.9.195 - - [13/Oct/2010:11:42:22 +0000] "GET /thumb?i=13612162 HTTP/1.1" 304 - "http://site.com/" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.10) Gecko/20100914 Firefox/3.6.10" 182.24.187.141 - - [13/Oct/2010:12:13:32 +0000] "GET /thumb?i=13622016 HTTP/1.1" 200 2645 "http://site.com/" "Mozilla/5.0 (Windows; U; Windows NT 6.1; fr; rv:1.9.2.3) Gecko/20100401 Firefox/3.6.3" 182.24.187.141 - - [13/Oct/2010:12:13:32 +0000] "GET /thumb?i=13622463 HTTP/1.1" 200 5960 "http://site.com/" "Mozilla/5.0 (Windows; U; Windows NT 6.1; fr; rv:1.9.2.3) Gecko/20100401 Firefox/3.6.3" 182.24.187.141 - - [13/Oct/2010:13:02:25 +0000] "POST /m HTTP/1.1" 200 1262 "http://site.com/" "Mozilla/5.0 (Windows; U; Windows NT 6.1; fr; rv:1.9.2.3) Gecko/20100401 Firefox/3.6.3" 182.24.187.141 - - [13/Oct/2010:13:02:28 +0000] "POST /m HTTP/1.1" 200 20 "http://site.com/" "Mozilla/5.0 (Windows; U; Windows NT 6.1; fr; rv:1.9.2.3) Gecko/20100401 Firefox/3.6.3"

Recherche

motifs

Descriptionduproble`me

On veut savoir si un certainmotifMapparaˆıt dans untexteT souvent, trouvertoutes les instancesdu motif et leurspositions.

Motif :M="our". Texte :T=

Partir un jour sans retour, Effacer notre amour, Sans se retourner ne pas regretter Garderlesinstantsqu’onavole´s. Partir un jour sans bagages, Oublier ton image, Sans se retourner ne pas regretter Pensera`demain,recommencer.

Descriptionduprobl`eme

Plus formellement, on a un alphabet (bits,char...) et deux tableaux TetMde taillenetmeb´atemetndscedte´l’alhep on cherches tous lesd´ealacsegs∈[0,n−m] tels que :

∀j∈[0,m−1]

M[j] =T[s+j]

Applications : traitement de texte, la commandegrep, recherchedes´equencesdeg`enes...

Descriptionduproble`me

On veut savoir si un certainmotifMıtaˆnsdaaunrapptexteT souvent, trouvertoutes les instancesdu motif et leurspositions.

Motif :M="our". Texte :T=

Partir un joursans retour, Effacer notre amour, Sans se retourner ne pas regretter Garderlesinstantsqu’onavol´es. Partir un joursans bagages, Oublier ton image, Sans se retourner ne pas regretter Penser`ademain,recommencer.

Pour chaques,etnolets.fomitalit’´egecle´eav

1for (ints=0; s<n-m+1; s++) { 2for (intj=0; j<m; j++) { 3if (M[j] != T[s+j]) { 4break; 5} 6} 7if (j == m) { printf("%d\n", s); 8 } 9 10}

L’algorithmenaı¨f

Complexite´danslepirecasΘ(nm). En moyennepene´del’alledataiddelhalpt,beismaΘ(n), pourceproble`meonesttr`esrarementdansuncasmoyen!

Algorithme de Rabin-Karp Principe

Principe : on aime mieux manipuler des nombres, alphabet de tailledcodage du motif/texte en based.

On doit alors comparer les entiers :

m−1 p=M[0] +M[1]×d+ ... +M[m−1]×d,

etpourund´ecalagedes:

m−1 ts=T[s] +T[s+ 1]×d+ ... +T[s+m−1]×d.

Le point important est quets+1lemefaciduited´esedtnts:   ts−T[s]ts m−1m−1 ts+1= +dT[s+m] = +dT[s+m]. d d

Algorithme de Rabin-Karp Code

1voidRabin_Karp (int*T,intn,int*M,intm,intd) { 2inti,h,p,t; 3/* on calcule d^(m-1) une fois pour toute */ 4h = pow(d,m-1); 5/* on calcule p */ 6p=0; 7for (i=m-1; i>=0; i--) { 8p = M[i] + d*p; 9} 10/* on calcule t_0 */ 11t=0; 12for (i=m-1; i>=0; i--) { 13t = T[i] + d*t; 14} 15ouslstetonte/*/*gasecelase´d 16for (i=0; i<n-m; i++) { 17if (t == p) { 18Motiftroprintf("opisitnovue´a`al)i,"n\d%; 19} 20t = (t/d) + h*T[i+m]; 21} 22if (t == p) { 23pf("Mrinttrouotif`e´vpalatiso%noin"d\-m,n); 24} 25}

Algorithme de Rabin-Karp Exemple

Recherchedes´equenced’ADN: l’alphabet est{A,T,C,G}etd= 4. on choisit :A= 0,T= 1,C= 2 etG= 3.

On prendT=ATACGGACTetM=GGA on trouve alors :

2 p= 3 + 3×d+ 0×d=15 2 t0= 0 + 1×d+ 0×d= 4 2t02 t1= 1 + 0×d+ 2×d= 33 = + 2×d d 2t12 t2+ 2= 0 ×d+ 3×d= 56 = + 3×d d t 222 t3= 2 + 3×d+ 3×d= 62 = + 3×d d 2t32 t4+ 3= 3 ×d+ 0×d=15= + 0×d d 2t42 t5+ 0= 3 ×d+ 2×d= 35 = + 2×d d 2t2 5 t6= 0 + 2×d+ 1×d= 24 = + 1×d d

Algorithme de Rabin-Karp Analysedecomplexit´e

Complexite´sdesdiﬀe´rentes´etapes: calcul dehenΘ(logm)(ou simplementΘ(m)), calcul depett0enΘ(m), n−mcalculs destsenΘ(1) doncΘ(n−m)au total.

Complexit´eglobaledanslepirecasoptimale:Θ(n).

onconsid`erequetouslescalculssefontenΘ(1).

Algorithme de Rabin-Karp Complexite´“re´elle”

m Plusdest grand, plus les calculs sont longs : m32 sid<2 les calculs sont enΘ(1) (sur un CPU 32 bits), m sinonlacomplexite´estΘ(log(d)) =Θ(mlogd) logdt´xia¨ene:ıvrterevuoocalelpmestconstantetonΘ(nm).

Pourame´liorercelaonfaitlescalculsmodulounentieradapt´e comme 65521 : nombre premier, 16 plus petit que 2produits possibles en tempsΘ(1). Sits=p.reiﬁerv´urpove¨ınasinoaparcamoialt1onf6552mod

Automates ﬁnis

Algorithme de Rabin-Karp avec modulo

Code similaire avec des modulo en plus.

(cf.poly p.111-112)

Complexite´: dans le pire cas :Θ(nm) otsuelmsdoulosont´egaux... en moyenne :Θ(nm)aussi ! n essat´erteinstannocenucevatn:en+m×(Nsol+ ). 65521

En pratique, simec12glat556sttr`eseorithmeecﬃca:e contrairementa`l’algorithmenaı¨flepirecasn’arrivepas... le modulo agit sur le motif completsujet`adesbiais.miosn

De´ﬁnitionformelle

Unautomate ﬁnimachine pouvant est une se trouver dans un   ensembleﬁnideconﬁgurationsinternesappele´ese´atts. Sonbut:reconnaıˆtreme´caniquementdesmots.  

Unautomateﬁnid´eterministeestladonn´ede: Σun alphabet ﬁni,{a,b} Qenust,ta´ed’nieﬁblemns{1, 2, 3, 4} q0∈Qial,initetatun´1 F⊂Qun ensemble d’te´ﬁstaxuan,{3} δ:Q×Σ→Qunefonction de transition. 

Fonctionnement d’un automate

∗ Principeedatomuteerrma´ena’l:q0, lit un mot deΣet suit la fonctiondetransition.Onregardesil’´etatd’arrive´eestdansF.

Dansl’´etatq∈Q, en lisantt∈Σsnadessapetamotu’a,ltatl’´e δ(q,t) et avance d’une case.

t ± q état

LelangageLreconnupar un automate est l’ensemble des mots qui l’am`enedansun´etatﬁnal: W ∗ L={W∈Σ,q0−→f,f∈F}

Exemple d’automate

Reconnaıˆtparexemplelesmotsab,aba,abbbetababbaa. L’´etat4estune´atrtebut: cen’estpasune´tatﬁnal, on n’en ressort jamais. L’automate peut se simpliﬁer.

Exemple d’automate

Reconnaˆıt par exemple les motsab,aba,abbbetababbaa. L’´etat4estunebuttatr´e: cen’estpasun´etatﬁnal, on n’en ressort jamais. L’automate peut se simpliﬁer.

Exemple d’automate

∗∗ ∗ ∗ Cet automate reconnaˆıt le langageL=ab(a|bb)=a(ba b)ba: absigniﬁe unasuivi d’unb, (a|bb) signiﬁeaoubb, ∗ asigniﬁe un nombre quelconque dea, y compris 0, + asigniﬁe un nombre strictement positif dea.