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

L'algorithme a été conçu en 1970^[2] par Knuth et Pratt, et dans un autre contexte, par Morris, et publié conjointement en 1977^[3]. Indépendamment Matiyasevich^[4]Modèle:,^[5] avait déjà obtenu dès 1969 un algorithme similaire, codé par une machine de Turing à deux dimensionsModèle: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 ^[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 (| P | \cdot | T |)$ , où $| P |$ est la longueur du motif $P$ et $| T |$ la longueur du texte $T$ ^[7]. 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 ^[6]). 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 $π [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, $π [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 $π$ s'appelle fonction préfixe (cf. p. 922 dans ^[6]). Voici la table qui donne les valeurs de $π [i]$ pour le motif ABABACA :


$i$	1	2	3	4	5	6	7
$P [i]$	A	B	A	B	A	C	A
$π [i]$	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 $π$ ;
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 $π$ 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 $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.

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

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

où $E_{q - 1} = {k ∣ \exists i, k = π^{i} [q - 1] e t 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

Modèle:Références

Voir aussi

Articles connexes

Bibliographie

Modèle:Commentaire biblio

Modèle:Article Modèle:Commentaire biblio
Modèle:Cormen2en. Section 32.4: The Knuth-Morris-Pratt algorithm, Modèle:P..

Liens externes

Modèle:Lien web
Modèle:Lien web, une explication de l'algorithme.
Modèle:Lien web, un exemple de l'algorithme Knuth-Morris-Pratt.

Modèle:Palette Modèle:Portail

↑ Modèle:Ouvrage
↑ Modèle:Article
↑ Modèle:Article
↑ Modèle:Article, dans sa version russe, traduite en anglais comme Modèle:Article
↑ Knuth le mentionne dans les errata de son livre Selected Papers on Design of Algorithms : Modèle:Citation
↑ ^6,0 ^6,1 ^6,2 ^6,3 ^6,4 ^6,5 ^6,6 et ^6,7 Modèle:Ouvrage
↑ Modèle:Ouvrage
↑ Modèle:Lien web
↑ Modèle:Lien web

[1] Modèle:Ouvrage

[2] Modèle:Article

[3] Modèle:Article

[4] Modèle:Article, dans sa version russe, traduite en anglais comme Modèle:Article

[5] Knuth le mentionne dans les errata de son livre Selected Papers on Design of Algorithms : Modèle:Citation

[:0-6] 6,0 ^6,1 ^6,2 ^6,3 ^6,4 ^6,5 ^6,6 et ^6,7 Modèle:Ouvrage

[7] Modèle:Ouvrage

[8] Modèle:Lien web

[9] Modèle:Lien web

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Algorithme de Knuth-Morris-Pratt

Sommaire

Contexte

Principe

Exemple

Fonction préfixe

Structure de l'algorithme

Phase de recherche

Pseudo-code

Explication

Complexité temporelle

Calcul de la fonction préfixe

Pseudo-code

Complexité temporelle

Généralisation à plusieurs motifs

Notes et références

Voir aussi

Articles connexes

Bibliographie

Liens externes

Menu de navigation

Algorithme de Knuth-Morris-Pratt

Contexte

Principe

Exemple

Fonction préfixe

Structure de l'algorithme

Phase de recherche

Pseudo-code

Explication

Complexité temporelle

Calcul de la fonction préfixe

Pseudo-code

Complexité temporelle

Généralisation à plusieurs motifs

Notes et références

Voir aussi

Articles connexes

Bibliographie

Liens externes

Menu de navigation

Rechercher