Algorithme de Knuth-Morris-Pratt

Exemple d'une recherche de la chaîne ${\displaystyle P}$ "longs des" dans le texte ${\displaystyle 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 ${\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.

Contexte

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.

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 ${\displaystyle P=T[s+1..s+|P|]}$. Ainsi, on peut décaler le motif ${\displaystyle P}$ de plus d'une lettre à chaque étape.

Exemple

Considérons la chaîne ${\displaystyle P}$ est ABABACA et le texte ${\displaystyle T}$ est ABABAABCBAB (cf. p. 923 dans ^[6]). Au début on compare le motif ${\displaystyle 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 ${\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 ci-dessus, ${\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]}$. La fonction ${\displaystyle \pi }$ s'appelle fonction préfixe (cf. p. 922 dans ^[6]). Voici la table qui donne les valeurs de ${\displaystyle \pi [i]}$ 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

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 ${\displaystyle \pi }$ ;
2. Phase de recherche. A l'instar de l'algorithme naïf, on recherche le motif ${\displaystyle P}$ dans le texte ${\displaystyle T}$ mais en utilisant la fonction préfixe ${\displaystyle \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 ^[6]), où l'on suppose que les indices des chaînes de caractères (autant le motif ${\displaystyle P}$ que le texte ${\displaystyle 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.

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

Calcul de la fonction préfixe

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

Pseudo-code

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 π

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

Généralisation à plusieurs motifs

L'algorithme d'Aho-Corasick généralise l'algorithme de Knuth-Morris-Pratt à la recherche simultanée de plusieurs motifs (voir p. 367, Section 10.3 dans ^[9]). Pour l'algorithme d'Aho-Corasick la fonction préfixe devient arborescente et est défini sur un trie.

Notes et références

1. (en) Maxime Crochemore et Wojciech Ryller, Text algorithms, Oxford University Press (ISBN 0-19-508609-0), Section 3.1, p. 34-42
2. (en) « A linear pattern-matching algorithm, », Tech. Rep. University of California Berkeley, n^o 40,‎ 1970
3. (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
4. (ru) Юрий Матиясевич, « О распознавании в реальное время отношения вхождения », Записки научных семинаров Ленинградского отделения Математического института им. В.А.Стеклова, vol. 20,‎ 1971, p. 104--114 (lire en ligne), dans sa version russe, traduite en anglais comme (en) Yuri Matiyasevich, « Real-time recognition of the inclusion relation », Journal of Soviet Mathematics, vol. 1,‎ 1973, p. 64--70 (lire en ligne)
5. Knuth le mentionne dans les errata de son livre Selected Papers on Design of Algorithms  : « I learned in 2012 that Yuri Matiyasevich had anticipated the linear-time pattern matching and pattern preprocessing algorithms of this paper, in the special case of a binary alphabet, already in 1969. He presented them as constructions for a Turing machine with a two-dimensional working memory. »
6. Cormen, Leiserson, Rivest, Stein, Algorithmique, Dunod (ISBN 978-2-10-054526-1)
7. (en) Graham A Stephen, String Searching Algorithms, World Scientific, 1994, 256 p. (ISBN 978-9810237035), p. 6
8. Jeff Erickson, « Algorithms by Jeff Erickson, 7. String matching (director's cut) », sur jeffe.cs.illinois.edu (consulté le 17 septembre 2024)
9. « Eléments d'algorithmique (Beauquier et.al.) — Sciencinfolycee », sur wiki.inria.fr (consulté le 11 octobre 2024)

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.