Algorithme de Knuth-Morris-Pratt

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 ${\displaystyle P}$ (ou aussi appelé motif) dans un texte ${\displaystyle T}$ avec une complexité linéaire ${\displaystyle O(|P|+|T|)}$ dans le pire cas, où ${\displaystyle |P|}$ et ${\displaystyle |T|}$ sont respectivement les longueurs (nombres de caractères) de la chaîne ${\displaystyle P}$ et du texte ${\displaystyle T}$ et ${\displaystyle O()}$ est une notation asymptotique de Landau. De plus la constante dans le ${\displaystyle O()}$ ne dépend pas de la taille de l'alphabet^[1].

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 ${\displaystyle O(|P|)}$, et la recherche proprement dite est en ${\displaystyle O(|T|)}$.

L'algorithme a été conçu en 1970^[2] par Knuth et Pratt (en), et dans un autre contexte, par Morris (en), et publié conjointement en 1977^[3]. Indépendamment Matiyasevich^[4],[5] 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.

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

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 ${\displaystyle O(|P|\cdot |T|)}$, où ${\displaystyle |P|}$ est la longueur du motif ${\displaystyle P}$ et ${\displaystyle |T|}$ la longueur du texte ${\displaystyle T}$^[7]. En effet, la comparaison ${\displaystyle P=T[s+1..s+|P|]}$ est en ${\displaystyle O(|P|)}$, qui dans un corps de boucle qui s'exécute ${\displaystyle O(|T|)}$ fois. L'approche naïve décale le motif d'une lettre à chaque fois.

L'algorithme de Knuth-Morris-Pratt propose d'utiliser l'information acquise lors des comparaisons lettre à lettre réalisées dans les comparaisons ${\displaystyle P=T[s+1..s+|P|]}$. Ainsi, on peut décaler le motif ${\displaystyle P}$ de plus d'une case.

Considérons la chaîne ${\displaystyle P}$ vaut ABABACA et le texte ${\displaystyle T}$ est ABABAABCBAB (cf. p. 923 dans ^[6]). Au début on compare le motif 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 du motif ABABA 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. 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          

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 ${\displaystyle P[1..k]}$, on cherche la longueur ${\displaystyle \pi [k]}$ du plus long préfixe de ${\displaystyle P[1..k]}$ qui est aussi suffixe de ${\displaystyle P[1..k]}$. Plus ce plus long préfixe/suffixe est court, plus on décale. Dans l'exemple, ${\displaystyle \pi [5]}$ vaut 3 car le mot ABA est le plus long qui est préfixe propre et suffixe propre de ${\displaystyle P[1..k]}$. On appelle fonction préfixe la fonction ${\displaystyle \pi }$ (cf. p. 922 dans ^[6]). Voici la table pour le motif ABABACA :

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

L'algorithme de Knuth-Morris-Pratt est en deux phases.

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

Voici un pseudo-code de la phase de recherche (cf. p. 924 dans ^[6]), 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^[6]. La différence i - q représente la position dans T du début du motif P glissant sur T.

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.

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 ${\displaystyle O(|T|)}$.

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

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

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

où ${\displaystyle 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^[8] pour calculer la fonction préfixe comme le montre le pseudo-code suivant (adapté de celui de Cormen et al., p. 924 dans ^[6]) :

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 ^[6]) 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 π

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|).

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

• (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)

• (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.

• 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.

• Portail de l'informatique théorique