Faire un don
Créer un compte
Se connecter
Algorithme de Knuth-Morris-Pratt
Article Discussion Outils 21 langues
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 (ou aussi appelé
motif) dans un texte avec une complexité linéaire dans le pire cas, où et
sont respectivement les longueurs (nombres de caractères) de la chaîne et du
texte et est une notation asymptotique de Landau. De plus la constante dans le
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 Exemple d'une recherche de la
précisément, la complexité du prétraitement est en , et la recherche chaîne "longs des" dans le texte
proprement dite est en . "les sanglots longs des violons de
L'algorithme a été conçu en 1970 2 par Knuth et Pratt, et dans un autre contexte, l'automne blessent mon cœur d'une
par Morris, et publié conjointement en 1977 3. Indépendamment Matiyasevich4, 5 langueur monotone."
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 [modifier le code]
L'approche naïve de recherche d'une chaîne consiste à décaler la chaîne le long du texte , de gauche à droite d'une
lettre à chaque étape. A chaque fois, on compare la chaîne et la portion du texte . 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 , où est la longueur du motif et la longueur du texte 7. En
effet, la comparaison est en , qui dans un corps de boucle qui s'exécute fois.
Principe [modifier le code]
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 . Ainsi, on peut décaler le motif de plus d'une lettre à chaque étape.
Exemple [modifier le code]
Supposons que la chaîne est ABABACA et que le texte 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 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 [modifier le code]
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 , on cherche la longueur du plus long préfixe de qui est aussi suffixe de .
Plus ce plus long préfixe/suffixe est court, plus on décale. Dans l'exemple ci-dessus, vaut 3 car le mot ABA est le plus
long qui est préfixe propre et suffixe propre de . La fonction s'appelle fonction préfixe (cf. p. 922 dans 6). Voici la table
qui donne les valeurs de pour le motif ABABACA :
1 2 3 4 5 6 7
A B A B A C A
0 0 1 2 3 0 1
Structure de l'algorithme [modifier le code]
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 ;
2. Phase de recherche. A l'instar de l'algorithme naïf, on recherche le motif dans le texte mais en utilisant la fonction
préfixe pour connaître le décalage.
Phase de recherche [modifier le code]
Pseudo-code [modifier le 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 que le texte )
commencent à 1 :
Illustration de la recherche du motif
P dans le texte T. La variable i est la
entrée : π fonction préfixe correspondante à P position actuelle dans le texte. La
P chaîne à chercher (motif, ou aiguille) variable est le nombre de lettres qui
T texte coïncident jusqu'à présent. Le début
sortie : toutes les positions où on trouve P dans T du motif P glissant sur T est à la
position i - q 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 [modifier le code]
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 [modifier le code]
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
.
Calcul de la fonction préfixe [modifier le code]
Décrivons maintenant comment calculer la fonction préfixe π.
Pseudo-code [modifier le code]
On a . Pour , le calcul de s'obtient grâce aux valeurs de avec grâce à la relation de récurrence
suivante (cf. corollaire 32.7, p. 926 dans 6) :
si
si
où .
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 [modifier le code]
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 [modifier le code]
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 [modifier le code]
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, no 40, 1970
3. ↑ (en) Donald Knuth, James H. Morris Jr. et Vaughan Pratt, « Fast pattern matching in strings », SIAM Journal on Computing,
vol. 6, no 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. ↑ a b c d e f g et h 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 [modifier le code]
Articles connexes [modifier le code]
Algorithme de recherche de sous-chaîne
Algorithme de Boyer-Moore.
Bibliographie [modifier le code]
(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, no 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, 2e éd. [détail de l’édition]. Section 32.4: The Knuth-Morris-Pratt algorithm, p. 923–931.
Liens externes [modifier le code]
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.
v·m
Algorithmique du texte
Algorithme de Knuth-Morris-Pratt · Algorithme de Boyer-Moore · Algorithme de Boyer-Moore-
Recherche de sous-
Horspool · Algorithme de Raita · Algorithme de Baeza-Yates-Gonnet · Algorithme Z · Algorithme de
chaîne Rabin-Karp · Algorithme d'Aho-Corasick
Alignement de
Algorithme de Needleman-Wunsch · Algorithme de Smith-Waterman · Transformée de Burrows-Wheeler
chaînes
Mesure de similarité Distance de Jaro-Winkler · Distance de Levenshtein · Distance de Hamming
Algorithmes de Weiner et de McCreight · Algorithme d'Ukkonen · Tableau des suffixes · Tableau de
Arbre des suffixes
Lyndon
Plus longue sous-séquence commune · Plus longue sous-chaîne commune · Plus courte super-
Comparaisons
séquence commune
Portail de l'informatique théorique
Catégorie : Algorithme sur les chaînes de caractères
La dernière modification de cette page a été faite le 9 avril 2025 à 17:38.
Droit d'auteur : les textes sont disponibles sous licence Creative Commons attribution, partage dans les mêmes conditions ; d’autres conditions peuvent
s’appliquer. Voyez les conditions d’utilisation pour plus de détails, ainsi que les crédits graphiques. En cas de réutilisation des textes de cette page, voyez
comment citer les auteurs et mentionner la licence.
Wikipedia® est une marque déposée de la Wikimedia Foundation, Inc., organisation de bienfaisance régie par le paragraphe 501(c)(3) du code fiscal des
États-Unis.
Politique de confidentialité À propos de Wikipédia Avertissements Contact Code de conduite Développeurs Statistiques
Déclaration sur les témoins (cookies) Version mobile
