Algorithme de Knuth-Morris-Pratt

Exemple d'une recherche de la chaîne $P$ "longs des" dans le texte $T$ "les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone."

En informatique, l'algorithme de Knuth-Morris-Pratt (ou d'une manière plus courte l'algorithme KMP) est un algorithme de recherche de sous-chaîne de caractères. Il permet de trouver les occurrences d'une chaîne $P$ (ou aussi appelé motif) dans un texte $T$ avec une complexité linéaire $O(|P|+|T|)$ dans le pire cas, où $|P|$ et $|T|$ sont respectivement les longueurs (nombres de caractères) de la chaîne $P$ et du texte $T$ et $O()$ est une notation asymptotique de Landau. De plus la constante dans le $O()$ ne dépend pas de la taille de l'alphabet.

Sa particularité réside en un prétraitement de la chaîne, qui fournit une information suffisante pour déterminer où continuer la recherche en cas de non-correspondance. Ainsi l'algorithme ne ré-examine pas les caractères qui ont été vus précédemment, et donc limite le nombre de comparaisons nécessaires. Plus précisément, la complexité du prétraitement est en $O(|P|)$, et la recherche proprement dite est en $O(|T|)$.

L'algorithme a été conçu en 1970 par Knuth et Pratt (en), et dans un autre contexte, par Morris (en), et publié conjointement en 1977. Indépendamment Matiyasevich avait déjà obtenu dès 1969 un algorithme similaire, codé par une machine de Turing à deux dimensions^[pas clair], en étudiant un problème de reconnaissance d'occurrence de chaîne.

Contexte

L'approche naïve de recherche d'une chaîne $P$ consiste à décaler la chaîne $P$ le long du texte $T$, de gauche à droite d'une lettre à chaque étape. A chaque fois, on compare la chaîne $P$ et la portion $T[s+1..s+|P|]$ du texte $T$. Voici le pseudo-code de l'algorithme naïf (cf. Section 32.1 p. 908 dans ) :

fonction rechercheNaïve(T, P)
      pour s = 0 à |T| - |P|
           si P = T[s+1..s+|P|]
                 afficher "la chaîne P apparaît avec le décalage" s

Dans le pire cas, l'approche naïve a un coût qui est $O(|P|\cdot |T|)$, où $|P|$ est la longueur du motif $P$ et $|T|$ la longueur du texte $T$. En effet, la comparaison $P=T[s+1..s+|P|]$ est en $O(|P|)$, qui dans un corps de boucle qui s'exécute $O(|T|)$ fois.

Principe

L'algorithme de Knuth-Morris-Pratt améliore l'approche naïve en utilisant l'information acquise lors des comparaisons lettre à lettre réalisées dans les comparaisons $P=T[s+1..s+|P|]$. Ainsi, on peut décaler le motif $P$ de plus d'une lettre à chaque étape.

Exemple

Considérons la chaîne $P$ est ABABACA et le texte $T$ est ABABAABCBAB (cf. p. 923 dans ). Au début on compare le motif $P$ avec le début ABABAAB. Les cinq premières lettres ABABA coïncident mais à la 6e position, les caractères différent :

T : ABABAABCBAB
P : ABABACA
         ^

Sachant que le début ABABA du motif correspond, la question est : quel est le plus petit décalage qui fait coïncider les caractères avant le curseur ^ ? On sait que décaler de 1 lettre n'aboutira pas, cela reviendrait à aligner le début ABAB avec BABA qui sont différents. Par contre, décaler de 2 lettres est prometteur car on retrouve le début ABA(que l'on appelle préfixe) du motif à la fin (suffixe) du texte déjà lu :

T : ABABAABCBAB
P :   ABABACA          

Fonction préfixe

La fin du texte déjà lu correspond à la fin de la portion du motif qui coïncide. On se ramène donc à l'étude du motif. En particulier, pour tout préfixe du motif $P[1..k]$, on cherche la longueur $\pi [k]$ du plus long préfixe de $P[1..k]$ qui est aussi suffixe de $P[1..k]$. Plus ce plus long préfixe/suffixe est court, plus on décale. Dans l'exemple ci-dessus, $\pi [5]$ vaut 3 car le mot ABA est le plus long qui est préfixe propre et suffixe propre de $P[1..k]$. La fonction $\pi$ s'appelle fonction préfixe (cf. p. 922 dans ). Voici la table qui donne les valeurs de $\pi [i]$ pour le motif ABABACA :

$i$	1	2	3	4	5	6	7
$P[i]$	A	B	A	B	A	C	A
$\pi [i]$	0	0	1	2	3	0	1

Structure de l'algorithme

L'algorithme de Knuth-Morris-Pratt est composée de deux phases.

1. Calcul de la fonction préfixe. L'algorithme construit la fonction préfixe $\pi$ ;
2. Phase de recherche. A l'instar de l'algorithme naïf, on recherche le motif $P$ dans le texte $T$ mais en utilisant la fonction préfixe $\pi$ pour connaître le décalage.

Phase de recherche

Illustration de la recherche du motif P dans le texte T. La variable i est la position actuelle dans le texte. La variable est le nombre de lettres qui coïncident jusqu'à présent. Le début du motif P glissant sur T est à la position i - q dans T.

Pseudo-code

Voici un pseudo-code de la phase de recherche (cf. p. 924 dans ), où l'on suppose que les indices des chaînes de caractères (autant le motif $P$ que le texte $T$) commencent à 1 :

entrée : π fonction préfixe correspondante à P
         P chaîne à chercher (motif, ou aiguille)
         T texte
sortie : toutes les positions où on trouve P dans T

fonction phaseRecherche(π, P, T)
      q := 0
      pour i = 1 à |T|
           tant que q > 0 et P[q+1] ≠ T[i]
                 q = π[q]
           si P[q+1] = T[i]
                 q = q + 1
           si q = |P|
                 afficher "le motif apparaît en position" i - |P|
                 q = π[q]

On suppose que la fonction préfixe π est déjà calculée. Dans l'algorithme ci-dessus, i désigne la position courante dans le texte T. La variable q, elle, désigne le nombre de caractères qui coïncident. La notation q est la même que pour désigner un état d'un automate fini, puisque l'algorithme de Knuth-Morris-Pratt s'introduit parfois avec l'exécution d'un automate fini. La différence i - q représente la position dans T du début du motif P glissant sur T.

Explication

Avec la boucle pour i = 1 à |T|, on parcourt toutes les lettres de T. Avec la boucle tant que q > 0 et P[q+1] ≠ T[i], on glisse le motif vers la droite jusqu'à avoir atteint la position i (q = 0) ou jusqu'à avoir un égalité des lettres courantes dans le motif et texte (P[q+1] = T[i]). En cas d'égalité, on augmente la partie qui coïncide (en vert dans l'image) en incrémentant q. Si q = |P|, cela signifie que tout le motif coïncide. L'affectation q = π[q] dans ce cas est présente pour glisser le motif afin de poursuivre la recherche.

Complexité temporelle

Dans la boucle tant que, i - q augmente strictement. A chaque tour de la boucle pour, i augmente strictement alors que i - q augmente ou stagne. Donc 2i - q augmente strictement à chaque tour de boucle (pour ou tant que). Donc l'algorithme est en $O(|T|)$.

Calcul de la fonction préfixe

Décrivons maintenant comment calculer la fonction préfixe π.

Pseudo-code

On a $\pi [1]=0$. Pour $q\in \{2,3,...,|P|\}$, le calcul de $\pi [q]$ s'obtient grâce aux valeurs de $\pi [i]$ avec $i<q$ grâce à la relation de récurrence suivante (cf. corollaire 32.7, p. 926 dans ) :

• $\pi [q]=0$ si $E_{q-1}=\emptyset$
• $\pi [q]=1+\max E_{q-1}$ si $E_{q-1}\neq \emptyset$

où $E_{q-1}=\{k\mid \exists i,k=\pi ^{i}[q-1]~et~P[k+1]=P[q]\}$.

Cette relation permet d'obtenir un algorithme de programmation dynamique pour calculer la fonction préfixe comme le montre le pseudo-code suivant (adapté de celui de Cormen et al., p. 924 dans ) :

entrée : P chaîne à chercher (motif, ou aiguille)
sortie : la fonction de préfixe π associée à P

fonction calculFonctionPrefixe(P)
     soit π[1..|P|] un tableau
     π[1] := 0
     pour q = 2 à |P|
          k := π[q-1]  
          tant que k > 0 et P[k+1] ≠ P[q]
                 k := π[k]
          si P[k+1] = P[q]
               π[q] := k + 1
          sinon
               π[q] := 0
    renvoyer π

Cormen et al. (p. 924 dans ) présente l'algorithme suivant, qui est équivalent au pseudo-code précédent, mais qui montre que le calcul de la fonction préfixe est similaire à une "phase de recherche" du motif P sur lui-même, en utilisant les valeurs de π[k] déjà calculées :

entrée : P chaîne à chercher (motif, ou aiguille)
sortie : la fonction de préfixe π associée à P

fonction calculFonctionPrefixe(P)
     soit π[1..|P|] un tableau
     π[1] := 0
     k := 0
     pour q = 2 à |P|
          // ici k = π[q-1]  
          tant que k > 0 et P[k+1] ≠ P[q]
                 k := π[k]
          si P[k+1] = P[q]
               k := k + 1
          π[q] := k
    renvoyer π

Complexité temporelle

Comme l'algorithme de calcul de la fonction préfixe est similaire à une phase de recherche du motif dans lui-même. De ce fait, l'analyse de complexité est similaire et sa complexité temporelle est en O(|P|).

Voir aussi

Articles connexes

• Algorithme de recherche de sous-chaîne
• Algorithme de Boyer-Moore.

Bibliographie

• (ru) Юрий Матиясевич, « О распознавании в реальное время отношения вхождения », Записки научных семинаров Ленинградского отделения Математического института им. В.А.Стеклова, vol. 20,‎ 1971, p. 104--114 (lire en ligne)
  Version en russe
• (en) Yuri Maiyasevich, « Real-time recognition of the inclusion relation », Journal of Soviet Mathematics, vol. 1,‎ 1973, p. 64--70 (lire en ligne)

Version traduite en anglais.

• (en) Donald Knuth, James H. Morris Jr. et Vaughan Pratt, « Fast pattern matching in strings », SIAM Journal on Computing, vol. 6, n^o 2,‎ 1977, p. 323–350
  Citations. Publication originale.
• (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill, 2001, 2^e éd. [détail de l’édition]. Section 32.4: The Knuth-Morris-Pratt algorithm, p. 923–931.

Liens externes

• Olivier Carton, « Algorithmes de Knuth, Morris et Pratt », sur LIAFA (Université Paris Diderot)
• (en) David Eppstein, « Knuth-Morris-Pratt string matching », sur ICS (University of California), une explication de l'algorithme.
• (en) J Strother Moore (co-inventeur de l'algorithme de Boyer-Moore), « KPM example », sur CS (Univesity of Texas), un exemple de l'algorithme Knuth-Morris-Pratt.