Voir la source de Algorithme de Knuth-Morris-Pratt

[[Fichier:Problème de recherche d'une sous-chaîne.svg|vignette|Exemple d'une recherche de la chaîne <math>P</math> "longs des" dans le texte <math>T</math> "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|algorithme de recherche de sous-chaîne de caractères]]. Il permet de trouver les occurrences d'une chaîne <math>P</math> (ou aussi appelé motif) dans un texte <math>T</math> avec une [[complexité en temps|complexité]] linéaire <math>O(|P| + |T|)</math> dans le pire cas, où <math>|P|</math> et <math>|T|</math> sont respectivement les longueurs (nombres de caractères) de la chaîne <math>P</math> et du texte <math>T</math> et ''<math>O()</math>'' est une [[Notation de Landau|notation asymptotique de Landau]]. De plus la [[constante]] dans le ''<math>O()</math>'' ne dépend pas de la taille de l'[[alphabet]]<ref>{{Ouvrage|langue=Anglais|auteur1=Maxime Crochemore et Wojciech Ryller|titre=Text algorithms|éditeur=Oxford University Press|passage=Section 3.1, p. 34-42|isbn=0-19-508609-0}}</ref>.

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 <math>O(|P|)</math>, et la recherche proprement dite est en <math>O(|T|)</math>.

L'algorithme a été conçu en [[1970]]<ref>{{article
| langue =en 
 | prénom2 = James H. | nom2 = Morris Jr. | lien auteur2 = James H. Morris, Jr.
 | prénom3 = Vaughan | nom3 = Pratt | lien auteur3 = Vaughan Pratt
| titre = A linear pattern-matching algorithm,
| périodique = Tech. Rep. University of California Berkeley
| numéro = 40
| année = 1970
}}</ref> par [[Donald Knuth|Knuth]] et [[Vaughan Pratt|Pratt]], et dans un autre contexte, par [[James H. Morris|Morris]], et publié conjointement en [[1977]]<ref>{{article
 | langue = en
 | prénom1 = Donald | nom1 = Knuth | lien auteur1 = Donald Knuth
 | prénom2 = James H. | nom2 = Morris Jr. | lien auteur2 = James H. Morris, Jr.
 | prénom3 = Vaughan | nom3 = Pratt | lien auteur3 = Vaughan Pratt
 | titre = Fast pattern matching in strings
 | périodique = SIAM Journal on Computing
 | volume = 6 | numéro = 2
 | pages = 323–350
 | année = 1977
}}</ref>. Indépendamment [[Matiyasevich]]<ref>{{article
| langue = ru
| prénom= Юрий
| nom = Матиясевич
| titre = О распознавании в реальное время отношения вхождения
| périodique = Записки научных семинаров Ленинградского отделения Математического института им. В.А.Стеклова 
| volume = 20 
| année = 1971
| page = 104--114
| url = http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=znsl&paperid=2401&option_lang=rus
}}, dans sa version russe, traduite en anglais comme {{article
| langue = en
| prénom = Yuri 
| nom = Matiyasevich
| titre = Real-time recognition of the inclusion relation
| périodique =  Journal of Soviet Mathematics
| volume =  1 
| année = 1973
| page = 64--70
| url = https://link.springer.com/article/10.1007%2FBF01117471
}}</ref>{{,}}<ref>Knuth le mentionne dans les errata de son livre ''Selected Papers on Design of Algorithms '' : {{citation|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.}}</ref> avait déjà obtenu dès 1969 un algorithme similaire, codé par une [[machine de Turing]] à deux dimensions{{Pas clair|date=décembre 2023}}, en étudiant un problème de reconnaissance d'occurrence de chaîne.

== Contexte ==
L'[[algorithme de recherche de sous-chaîne|approche naïve]] de recherche d'une chaîne <math>P</math> consiste à décaler la chaîne <math>P</math> le long du texte <math>T</math>, de gauche à droite d'une lettre à chaque étape. A chaque fois, on compare la chaîne <math>P</math> et la portion <math>T[s+1..s+|P|]</math> du texte <math>T</math>. Voici le [[pseudo-code]] de l'algorithme naïf (cf. Section 32.1 p. 908 dans <ref name=":0">{{Ouvrage|langue=Français|auteur1=Cormen, Leiserson, Rivest, Stein|titre=Algorithmique|éditeur=Dunod|isbn=978-2-10-054526-1}}</ref>) :
 '''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 <math>O(|P| \cdot |T|)</math>, où <math>|P|</math> est la longueur du motif <math>P</math> et <math>|T|</math> la longueur du texte <math>T</math><ref>{{Ouvrage|langue=en|auteur1=Graham A Stephen|titre=String Searching Algorithms|éditeur=World Scientific|année=1994|pages totales=256|passage=6|isbn=978-9810237035}}</ref>. En effet, la comparaison <math>P = T[s+1..s+|P|]</math> est en <math>O(|P|)</math>, qui dans un corps de boucle qui s'exécute <math>O(|T|)</math> 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 <math>P = T[s+1..s+|P|]</math>. Ainsi, on peut décaler le motif <math>P</math> de plus d'une lettre à chaque étape. 

=== Exemple ===
Considérons la chaîne <math>P</math> est <code>ABABACA</code> et le texte <math>T</math> est <code>ABABAABCBAB</code> (cf. p. 923 dans <ref name=":0" />). Au début on compare le motif <math>P</math> avec le début <code>ABABAAB</code>. Les cinq premières lettres <code>ABABA</code> coïncident mais à la 6e position, les caractères différent :
 T : '''ABABA'''ABCBAB
 P : '''ABABA'''CA
          '''^'''
Sachant que le début <code>ABABA</code> 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 <code>ABAB</code> avec <code>BABA</code> qui sont différents. Par contre, décaler de 2 lettres est prometteur car on retrouve le début <code>ABA</code>(que l'on appelle préfixe) du motif à la fin (suffixe) du texte déjà lu :
 T : '''AB<u>ABA</u>'''ABCBAB
 P :   '''<u>ABA</u>BA'''CA          

=== 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 <math>P[1..k]</math>, on cherche la longueur <math>\pi[k]</math> du plus long préfixe de <math>P[1..k]</math> qui est aussi suffixe de <math>P[1..k]</math>. Plus ce plus long préfixe/suffixe est court, plus on décale. Dans l'exemple ci-dessus, <math>\pi[5]</math> vaut 3 car le mot ABA est le plus long qui est préfixe propre et suffixe propre de <math>P[1..k]</math>. La fonction <math>\pi</math> s'appelle ''fonction préfixe'' (cf. p. 922 dans <ref name=":0" />). Voici la table qui donne les valeurs de <math>\pi[i]</math> pour le motif <code>ABABACA</code> :
{| class="wikitable"
|+
!<math>i</math>
!1
!2
!3
!4
!5
!6
!7
|-
|<math>P[i]</math>
|A
|B
|A
|B
|A
|C
|A
|-
|<math>\pi[i]</math>
|0
|0
|1
|2
|3
|0
|1
|}

=== Structure de l'algorithme ===
L'algorithme de Knuth-Morris-Pratt est composée de deux phases.
# ''Calcul de la fonction préfixe''. L'algorithme construit la fonction préfixe <math>\pi</math> ;
# ''Phase de recherche''. A l'instar de l'algorithme naïf, on recherche le motif <math>P</math> dans le texte <math>T</math> mais en utilisant la fonction préfixe <math>\pi</math> pour connaître le ''décalage''.

== Phase de recherche ==
[[Fichier:Knuth-morris-pratt-illustration.svg|vignette|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 <ref name=":0" />), où l'on suppose que les indices des [[Chaîne de caractères|chaînes de caractères]] (autant le motif <math>P</math> que le texte <math>T</math>) 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<ref name=":0" />. 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 <math>O(|T|)</math>.

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

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

* <math>\pi[q] = 0</math> si <math>E_{q-1} = \emptyset</math>
* <math>\pi[q] = 
1 + \max E_{q-1}</math> si <math>E_{q-1} \neq \emptyset</math>

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

Cette relation permet d'obtenir un algorithme de [[programmation dynamique]]<ref>{{Lien web |auteur=Jeff Erickson |titre=Algorithms by Jeff Erickson, 7. String matching (director's cut) |url=https://jeffe.cs.illinois.edu/teaching/algorithms/ |site=jeffe.cs.illinois.edu |consulté le=2024-09-17}}</ref> pour calculer la fonction préfixe comme le montre le pseudo-code suivant (adapté de celui de Cormen et al., p. 924 dans <ref name=":0" />) :
 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 <ref name=":0" />) 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 <ref>{{Lien web |titre=Eléments d'algorithmique (Beauquier et.al.) — Sciencinfolycee |url=https://wiki.inria.fr/sciencinfolycee/El%C3%A9ments_d'algorithmique_(Beauquier_et.al.) |site=wiki.inria.fr |consulté le=2024-10-11}}</ref>). Pour l'algorithme d'Aho-Corasick la fonction préfixe devient arborescente et est défini sur un [[Trie (informatique)|trie]].

== Notes et références ==
{{Références}}

== Voir aussi ==
=== Articles connexes ===
* [[Algorithme de recherche de sous-chaîne]]
* [[Algorithme de Boyer-Moore]].

=== Bibliographie ===
* {{article
| langue = ru
| prénom= Юрий
| nom = Матиясевич
| titre = О распознавании в реальное время отношения вхождения
| périodique = Записки научных семинаров Ленинградского отделения Математического института им. В.А.Стеклова 
| volume = 20 
| année = 1971
| page = 104--114
| url= http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=znsl&paperid=2401&option_lang=rus
| lire en ligne = http://gdz.sub.uni-goettingen.de/pdfcache/PPN502141972/PPN502141972___LOG_0019.pdf
}}{{commentaire biblio | Version en russe}}
* {{article
| langue = en
| prénom = Yuri 
| nom = Maiyasevich
| titre = Real-time recognition of the inclusion relation
| périodique =  Journal of Soviet Mathematics
| volume =  1 
| année = 1973
| page = 64--70
| lire en ligne = http://logic.pdmi.ras.ru/~yumat/Journal/inclusion/inclusion.pdf.gz
}}
{{commentaire biblio | Version traduite en anglais.}}
* {{article
 | langue = en
 | prénom1 = Donald | nom1 = Knuth | lien auteur1 = Donald Knuth
 | prénom2 = James H. | nom2 = Morris Jr. | lien auteur2 = James H. Morris, Jr.
 | prénom3 = Vaughan | nom3 = Pratt | lien auteur3 = Vaughan Pratt
 | titre = Fast pattern matching in strings
 | périodique = SIAM Journal on Computing
 | volume = 6 | numéro = 2
 | pages = 323–350
 | année = 1977
}} {{commentaire biblio|[http://citeseer.ist.psu.edu/context/23820/0 Citations]. Publication originale.}}
* {{Cormen2en}}. Section 32.4: The Knuth-Morris-Pratt algorithm, {{p.|923–931}}.

=== Liens externes ===

* {{lien web
 | langue = fr
 | url = http://www.liafa.jussieu.fr/~carton/Enseignement/Algorithmique/Programmation/Pattern/MorrisPratt/
 | titre = Algorithmes de Knuth, Morris et Pratt
 | auteur = Olivier Carton
 | site = LIAFA (Université Paris Diderot)
}}
* {{lien web
 | langue = en
 | url = http://www.ics.uci.edu/~eppstein/161/960227.html
 | titre = Knuth-Morris-Pratt string matching
 | auteur = David Eppstein
 | site = ICS (University of California)
}}, une explication de l'algorithme.
* {{lien web
 | langue = en
 | url = http://cs.utexas.edu/users/moore/best-ideas/string-searching/kpm-example.html
 | titre = KPM example
 | auteur = [[J Strother Moore]] (co-inventeur de l'[[algorithme de Boyer-Moore]])
 | site = CS (Univesity of Texas)
}}, un exemple de l'algorithme Knuth-Morris-Pratt.

{{Palette|Algorithmes de manipulation de texte}}
{{Portail|informatique théorique}}

[[Catégorie:Algorithme sur les chaînes de caractères]]