Next PDF List

Algorithmicsfor BiologyJean-PaulCometComplexityPat.

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences25/112Finite-state automatonAfinite automatonis a quintupletM= (Q,q0,A,Σ,δ)Q: finite set of statesq0: initial stateA?Q: set of final statesΣ : finite alphabetδis a function fromQ×Σ inQcalled the transition function.Thesuffix functionassociated with a patternP[1 m] :σ: Σ?-→ {0,1, ,m}t-→σ(x) = max{k|P[1 k]suffix oft}(1)The numberσ(t) is the size of the largest prefix of the pattern being searchedfor, which is the suffix of the textt.Example :ForP=ab, one haveσ(?) = 0,σ(ccaca) = 1,σ(ccab) = 2.Ifxis suffix ofy,σ(x)≤σ(y).bis suffix ofab,σ(b)≤σ(ab)ais suffix ofaa,σ(a)≤σ(aa).Automaton associated with a pattern.This is the automaton for which we are instateqif and only if the largest prefix we have just read isP[1 q].Q={0,1, ,m}q0={0}A={m}δ(q,a) =σ(Pqa) maximum suffix of the concatenation ofPqwitha.Algorithmicsfor BiologyJean-PaulCometComplexityPat.

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences26/112Finite-state automatonExample :Search for patternababaca012345 67a aaaabab cabcabcbccbcbcbcOnce the automaton has been constructed, the text traversal algorithm is asfollows :1defFinateAutomatonSearch(T, delta , m)2n =len(T);3q = 0 ;4for(i=1; i<=n; i++) {5q = delta (q,T[i]);6ifq = m then7print(??The pattern appears with the offset??, i-m);8}Complexity :O(n)Unroll the automaton with the stringababacaba.Algorithmicsfor BiologyJean-PaulCometComplexityPat.

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences27/112Computing the transition function.The idea is based on the meaning of the different states of the automaton :stateicorresponds to the state where the firstiletters of the searchedpattern have just been read.

To build the automaton, we go through all the statesof the automaton (from 0 ton, wherenis the length of the word we"re lookingfor) and for each statei, we go through each letter a of the alphabet.

We thencalculate the longest prefix of the pattern that is a suffix ofP[1 i].a.

The lengthof this suffix gives the arrival state of the transition starting fromivia lettera.1defTransition_Function_computation (P, Sigma)2m =len(P);3forqinr ange(m):4forainSigma :5k =min(m,q+1);6while(P[1 k]isn ota suffixe of P_q.a ) :7k--;8delta(q,a) = k;9return(delta);For this function to be correct, the following convention must be used :εis thesuffix for all strings.Complexity analysis :lines 6-7 :O(m2)line 4 :O(|Σ|)line 3 :O(m)Global complexity :O(m3|Σ|)We can do faster.Algorithmicsfor BiologyJean-PaulCometComplexityPat.

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences28/112Example : building the automaton for pattern AABqakPkPq.asuffixδq=0Amin(m,q+ 1) =min(3,1) = 1AAyes1B1ABno0εByes0q=1Amin(m,q+ 1) =min(3,2) = 2AAAAyes2B2AAABno1AABno0εAByes0q=2Amin(m,q+ 1) =min(3,3) = 3AABAAAno2AAAAAyes2B3AABAAByes3q=3Amin(m,q+ 1) =min(3,4) = 3AABAABAno2AAAABAno1AAABAyes1B3AABAABBno2AAAABBno1AAABBno0εAABByes00 1 2 3^AAA BA^AA^[A,B]^AAlgorithmicsfor BiologyJean-PaulCometComplexityPat.

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences29/112Algorithme de Knuth-Morris-PrattCet algorithme permet d"avoir une complexit´e en Θ(n+m) en´evitantenti`erement de construire la fonction de transitionδ.

Il calcule une fonctionauxiliaireπ[1 m] pr´ecalcul´ee`a partir du motif enO(m).

Le tableauπpermet`a lafonction de transitionδd"ˆetre calcul´ee au vol quand c"est n´ecessaire.Fonction pr´efixe d"un motif :Correspondance entre le motif et ses propresd´ecalages.Patterna ab a b c aPatterna ab a b c aTextebaba a ass'=== === = =P3Question :comment calculers?pour que le d´ecalage ne soit pas invalide?R´eponse :Trouver un suffixePkdePqqui soit pr´efixe deP.La fonction pr´efixe pour un motifP:Π :{1,2 m} -→ {0,1 m-1}q-→Π[q] =max{k/k

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences30/112Intuition pour la calcul de la fonction pr´efixeOn construit le tableau Π en partant de l"indice 0.

L"initialisation estsimple : Π[1] = 0Supposons maintenant qu"on ait calcul´e Π[i] dei= 1`aq-1.

Pour calculerΠ[q] on a la situation suivante :qq-1kk+1=totocommekest le plus long pr´efixe qui est suffixe dePq-1, le plus long pr´efixequi est aussi suffixe dePqne peut pasˆetre plus long quePk+1.

De plus on aP[k+ 1] =P[q]??Π[q] =k+ 1siP[k+ 1]?=P[q], il faut chercher le plus grand pr´efixe-suffixe dePq.

Si onregarde pas la derni`ere lettre, le plus grand pr´efixe-suffixe dePqest aussisuffixe dePk. Or on connait le plus grand pr´efixe-suffixe dePk, c"est Π[k]d´ej`a construit.

Une fois que l"on aPΠ[k], il faut v´erifier qu"il peutˆetre´etendu`a la lettre d"apr`es.Algorithmicsfor BiologyJean-PaulCometComplexityPat.

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences31/112Algorithme pour le Calcul de la fonction pr´efixe1Calcul_Fonction_pr´efixe(P)2m =long(P);3pi[1] = 0;4k = 0;5for(q=2; q<=m ; q++) {6while(k>0)andP[k+1] != P[q]:7{8k=pi[k];9}10ifP[k+1] == P[q] then k++;11pi[q] = k;12}13return(pi);Algorithmicsfor BiologyJean-PaulCometComplexityPat.

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences32/112Exemple 11 2 3 4 5 6 7 8 9 10a b a b a b a b c aConstruisons Π :Π : 1 2 3 4 5 6 7 8 9 100012345601q= 2,k= 0pas de while (k=0) ifP[1] =P[2](a =b)?non,k= 0 =?Π[2] = 0q= 3,k= 0pas de while (k=0) ifP[1] =P[3](a =a)?oui,k= 1 =?Π[3] = 1q= 4,k= 1pas de while (P[k+1]=P[q]) ifP[2] =P[4](b =b)?oui,k= 2 =?Π[4] = 2q= 5,k= 2pas de while (P[k+1]=P[q]) ifP[3] =P[5](a =a)?oui,k= 3 =?Π[5] = 3q= 6,k= 3pas de while (P[k+1]=P[q]) ifP[4] =P[6](b =b)?oui,k= 4 =?Π[6] = 4q= 7,k= 4pas de while (P[k+1]=P[q]) ifP[5] =P[7](a =a)?oui,k= 5 =?Π[7] = 5q= 8,k= 5pas de while (P[k+1]=P[q]) ifP[6] =P[8](b =b)?oui,k= 6 =?Π[8] = 6q= 9,k= 6entr ´ee dans le whilewhileP[7]?=P[9]( a?=c)k= Π[6] = 4whileP[5]?=P[9]( a?=c)k= Π[4] = 2whileP[3]?=P[9]( a?=c)k= Π[2] = 0ifP[1] =P[9](a =c)?non,k= 0 =?Π[9] = 0q= 10,k= 0pas de while (k=0 & P[k+1]=P[q]) ifP[1] =P[10](a=a) ?oui,k= 1 =?Π[10] = 1Algorithmicsfor BiologyJean-PaulCometComplexityPat.

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences33/112Exemple 2consid´erons le motif suivant :1 2 3 4S N N SConstruisons la fonction Π :Π : 1 2 3 40001q= 2,k= 0pas de while (k=0) ifP[1] =P[2]( S?=N)?non =?Π[2] = 0q= 3,k= 0pas de while (k=0) ifP[1] =P[3]( S?=N)?non =?Π[3] = 0q= 4,k= 0pas de while (k=0) ifP[1] =P[4]( S=S)?oui,k= 1 =?Π[4] = 1Algorithmicsfor BiologyJean-PaulCometComplexityPat.

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences34/112Validit´e de la fonction pr´efixe.Soitπ?[q] ={q,π[q],π2[q], πt[q]}o`utest le premier entier tel queπt[q] = 0.LemmaSoit P un motif de longueur m et de fonction prefixeπ.

Alors, pour q= 1,2, m,on aπ?[q] ={k|Pksuffixe dePq}D´emonstration :1Premier sens :i?π?[q]?Pisuffixe dePq.Sii?π?[q],?u|πu[q] =ipouru= 0,i=qet doncPi=PqetPiest suffixe dePqsupposonsPπu[q]suffixe dePqpour toutu

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences34/112Validit´e de la fonction pr´efixe.Soitπ?[q] ={q,π[q],π2[q], πt[q]}o`utest le premier entier tel queπt[q] = 0.LemmaSoit P un motif de longueur m et de fonction prefixeπ.

Alors, pour q= 1,2, m,on aπ?[q] ={k|Pksuffixe dePq}D´emonstration :2Montrons que :{k|Pksuffixe dePq} ?π?[q]P arl"absurde : On suppose qu"il existe un entier dans l"ensemble{k|Pksuffixe dePq} \π?[q].On appellejla plus grande des valeurs.Commeq?π?[q]? {k|Pksuffixe dePq} ?jj)Orjest la plus grande valeur de{k|Pksuffixe dePq} \π?[q]On devrait alors avoirπ[j?] =jet doncj?π?[q].Contradiction.?Algorithmicsfor BiologyJean-PaulCometComplexityPat.

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences35/112Validit´e de la fonction pr´efixe.LemmaSoit P un motif de longueur m et de fonction prefixeπ.

Pour q= 1,2, ,m,siπ[q]>0alorsπ[q]-1?π?[q-1].D´emonstration :Sik=π[q]>0 alorsPksuffixe dePq.DoncPk-1suffixe dePq-1(en supprimant le dernier caract`ere dePketPq)D"apr`es le lemme pr´ec´edent :k-1?π?[q-A].?Pourq= 2,3, ,m, on d´efinit le sous ensembleEq-1?π?[q-1] par :Eq-1={k|k?π?[q-1]etP[k+ 1] =P[q]}Intuitivement,Eq-1est constitu´e des valeursk?π?[q-1] telles qu"il estpossible d"´etendrePk`aPk+1et d"obtenir un suffixe dePq.Algorithmicsfor BiologyJean-PaulCometComplexityPat.

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences36/112Validit´e de la fonction pr´efixe.corrolarySoit P un motif de longueur m et de fonction prefixeπ.

Pour q= 2,3, ,m,π[q] = 0siEq-1={}π[q] = 1 + max{k?Eq-1}siEq-1?={}D´emonstration :Sir=π[q]>0 alorsPrsuffixe dePq.Etr≥1?P[r] =P[q]D"apr`es le lemme pr´ec´edent, sir≥1, on a :r= 1 + max{k?π?[q-1]|P[k+ 1] =Pq]????Eq-1}Sir= 0, il n"existe aucunk?π?[q-1] pour lequel on peut´etendrePk`aPk+1pour obtenir un suffixe dePq, puisqu"on aurait dans ce casπ[q]>0.DoncEq-1={}?Algorithmicsfor BiologyJean-PaulCometComplexityPat.

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences37/112Validit´e de l"algorithme :1π[1] = 0 correct carπ[q]

MatchingRabin-KarpAntomataKMPBMGraphsDyn.Prog.Sequences38/112Proc´edure globale1KMP1(T,P)2n =long[T];3m =long[P];4PI = Calcul_fonct_prefixe(P);5q = 0 ;67Pour i=1 `a n faire8tant que q>0 & P[q+1]!=T[i]9q = PI[q];10si P[q+1]=T[i]:11q = q+112si q = m alors13print(??hit en??, i-m);14q = PI[q];1KMP2(T,P)2n =long[T];3m =long[P];4PI = Calcul_fonct_prefixe(P);5i = q = 0 ;67tant que (i

La deuxi`eme version g`ere dans une seule boucledeux indices : un indice qui indique l"avancement dans le texte et un autre pourrepr´esenter l"avancement dans le motif.Analyse de la complexit´e :n´ecessite l"analyse amortie