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 ?
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.
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.reifierv´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`eseorithmeecffica:e contrairementa`l’algorithmenaı¨flepirecasn’arrivepas... le modulo agit sur le motif completsujet`adesbiais.miosn
De´finitionformelle
Unautomate finimachine pouvant est une se trouver dans un ensemblefinideconfigurationsinternesappele´ese´atts. Sonbut:reconnaıˆtreme´caniquementdesmots.
∗ 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.
a
u
e
r
t ± q état
i
r
LelangageLreconnupar un automate est l’ensemble des mots qui l’am`enedansun´etatfinal: W ∗ L={W∈Σ,q0−→f,f∈F}
1
a
b
2
3
a
b
Exemple d’automate
Reconnaıˆtparexemplelesmotsab,aba,abbbetababbaa. L’´etat4estune´atrtebut: cen’estpasune´tatfinal, 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: cen’estpasun´etatfinal, 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.