IN101 - cours 06 - 16 octobre 2009
12 pages
Français

IN101 - cours 06 - 16 octobre 2009

-

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

Description

Un probl`eme concretUtilisation de fichiers 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 ...

Sujets

Informations

Publié par
Nombre de lectures 12
Langue Français
Des
logs
de
IN
serveur
101
14
web
-
Cours
octobre
2011
pr´esent´epar Matthieu Finiasz
ressemblent
a`
06
cela
Unprobl`emeconcret Utilisation de fichiers 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)"
On veut pouvoir facilement etefficacementtrouver : les lignes contenant une adresse IP, lesadressesIPayantacc´ed´e`aunepagedonne´e, laproportionderequeˆtesutilisantLinux... dans un fichier de plusieurs millions de lignes. La commandegreppermet de faire cela, mais comment ?
Des
logs
de
serveur
web
ressemblent
a`
cela
Unproble`meconcret Utilisation de fichiers 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
de
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 Garderlesinstantsquonavole´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´lalhep on cherches tous lesd´ealacsegs[0,nm] tels que :
j[0,m1]
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 Garderlesinstantsquonavol´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}
Lalgorithmenaı¨f
Complexite´danslepirecasΘ(nm). En moyennepene´delalledataiddelhalpt,beismaΘ(n), pourceproble`meonesttr`esrarementdansuncasmoyen!
Algorithme de Rabin-Karp Principe
Principe : on aime mieux manipuler des nombres, alphabet de tailledcodage du motif/texte en based.
On doit alors comparer les entiers :
m1 p=M[0] +M[1]×d+ ... +M[m1]×d,
etpourund´ecalagedes:
m1 ts=T[s] +T[s+ 1]×d+ ... +T[s+m1]×d.
Le point important est quets+1lemefaciduited´esedtnts:   tsT[s]ts m1m1 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´equencedADN: 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´sdesdie´rentes´etapes: calcul dehenΘ(logm)(ou simplementΘ(m)), calcul depett0enΘ(m), nmcalculs destsenΘ(1) doncΘ(nm)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 2produits possibles en tempsΘ(1). Sits=p.reierv´urpove¨ınasinoaparcamoialt1onf6552mod
Automates finis
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, simec12glat556sttr`eseorithmeecca:e contrairementa`lalgorithmenaı¨flepirecasnarrivepas... le modulo agit sur le motif completsujet`adesbiais.miosn
De´nitionformelle
Unautomate finimachine pouvant est une se trouver dans un   ensemblenidecongurationsinternesappele´ese´atts. Sonbut:reconnaıˆtreme´caniquementdesmots.  
Unautomatenid´eterministeestladonn´ede: Σun alphabet fini,{a,b} Qenust,ta´ednieblemns{1, 2, 3, 4} q0Qial,initetatun´1 FQun ensemble d’te´staxuan,{3} δ:Q×ΣQunefonction de transition.
a
b
1
4
b
a
a
b
2
3
a
b
Fonctionnement d’un automate
Principeedatomuteerrma´enal:q0, lit un mot deΣet suit la fonctiondetransition.Onregardesil´etatdarrive´eestdansF.
Dansl´etatqQ, en lisanttΣsnadessapetamotua,ltatl´e δ(q,t) et avance d’une case.
a
u
e
r
t ± q état
i
r
LelangageLreconnupar un automate est l’ensemble des mots qui lam`enedansun´etatnal: W L={WΣ,q0−→f,fF}
1
a
b
2
3
a
b
Exemple d’automate
Reconnaıˆtparexemplelesmotsab,aba,abbbetababbaa. L´etat4estune´atrtebut: cenestpasune´tatnal, on n’en ressort jamais. L’automate peut se simplifier.
a
b
1
4
b
a
a
b
2
3
a
b
Exemple d’automate
Reconnaˆıt par exemple les motsab,aba,abbbetababbaa. L´etat4estunebuttatr´e: cenestpasun´etatnal, on n’en ressort jamais. L’automate peut se simplifier.
1
a
b
2
3
a
b
Exemple d’automate
∗ ∗ ∗ Cet automate reconnaˆıt le langageL=ab(a|bb)=a(ba b)ba: absignifie unasuivi d’unb, (a|bb) signifieaoubb, asignifie un nombre quelconque dea, y compris 0, + asignifie un nombre strictement positif dea.