TD d’algorithmique numéro 13 - Recherche de motifs, suite

Daniel Hirschkoff et Natacha Portier semaine du 10 au 15 janvier 2000

Question 1 ⋆ Knuth Morris Pratt ⋆

Cet algorithme permet d’éviter le calcul de la fonction de transition de l’automate fini. On le remplace par le calcul d’une nouvelle fonction, la f onction préfixe, qui exprime la correspondance entre le motif et ses propres décalages.

Question 1.1 ⋆ définition de la fonction préfixe ⋆

La f onction préfixe π pour le motif P de longueur m est une fonction de {1; 2 … m} dans {0; 1 … m − 1} définie par :

π[q] = max{k | k < q et P_{k} ⊐ P_{q}}

Si les q premières lettres du motif ont déjà été trouvées dans le texte, c’est-à-dire s’il existe un décalage s tel que M[s + 1] … M[s + q] = P [1] … P [q] = P_{q}, alors le décalage s est potentiellement valide (il reste à vérifier que la fin du motif est éventuellement présente) et le prochain décalage potentiellement valide est s′ = s + (q − π[q]).

Calculer la fonction π pour le motif ababaca.

Question 1.2 ⋆ calcul de la fonction préfixe ⋆

Montrons la validité de la procédure :

Calcul Fonction Préfixe(P) := m:= longueur[P] π[1] := 0 k:= 0

 pour q de 2 à m

faire tant que k > 0 ∧ P [k + 1] ≠ P [q]

faire k:= π[k] si P [k + 1] = P [q] alors k:= k + 1 π[q] := k

Retourner π

On pose π^{∗}[q] = {q, π[q], π^{2}[q], …, π^{t}[q]}, la séquence s’arrêtant lorsque l’on atteint π^{t}[q] = 0.

1. Montrer que pour q = 1, 2, …, m:

π^{∗}[q] = {k : P_{k} ⊐ P_{q}} .

2. Montrer que pour q = 1, 2, …, m, si π[q] > 0 alors π[q] − 1 ∈ π^{∗}[q − 1].

Pour q = 2, 3, …, m on définit le sous ensemble E_{q−1} ⊆ π^{∗}[q − 1] par

E_{q−1} = {k | k ∈ π^{∗}[q − 1] et P [k + 1] = P [q]

3. Montrer que pour q = 2, 3, …, m:

π[q] = \{ \begin{matrix}0 & si E_{q−1} = ∅ \\ 1 + max\{k ∈ E_{q−1}\} & si E_{q−1} ≠ ∅ \end{matrix}

4. En déduire la correction de Calcul Fonction Préfixe.

Question 1.3 ⋆ complexité de la fonction préfixe ⋆

Utiliser une analyse amortie pour donner le temps d’exécution de la fonction Calcul Fonction Préfixe. On prendra comme potentiel la valeur de l’entier k.

Question 1.4 ⋆ procédure KMP ⋆

KMP(T,P) := n:= longueur[T] m:= longueur[P] π:= Calcul Fonction Préfixe(P) q:= 0

 pour i de 1 à n

faire tant que q > 0 ∧ P [q + 1] ≠ T [i]

faire q:= π[q] si P [q + 1] = T [i] alors q:= q + 1 si q = m alors Imprimer Le motif apparaît avec le décalage i − m

q:= π[q]

Utiliser un argument similaire à celui de la question précédente pour calculer le temps d’exécution du reste de la fonction KMP.

En déduire le temps d’exécution de l’algorithme.

Question 1.5 ⋆ Validité de l’algorithme de Knuth Morris Pratt ⋆

La procédure KMP simule la procédure de recherche par automate fini. On donne à q la valeur δ(q, T [i]) non pas en utilisant une valeur stockée mais en la recalculant si nécessaire.

Montrer que soit δ(q, T [i]) = 0 soit δ(q, T [i]) − 1 ∈ π^{∗}[q].

En déduire la correction de l’algorithme KMP.