Algorithme de Knuth-Morris-Pratt

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), permettant de trouver les occurrences d'une chaîne $P$ dans un texte $S$ avec une complexité linéaire $O(|P|+|S|)$ dans le pire cas. 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.

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

Principe de fonctionnement

Approche naïve

Afin de comprendre l'algorithme de Knuth-Morris-Pratt, il est judicieux de se pencher sur l'approche naïve de la recherche de chaîne. La chaîne P peut être trouvée dans le texte S en utilisant l'algorithme suivant :

1. Soit $i=1$ ;
2. Tant qu'il reste des positions à vérifier
   • Comparer lettre à lettre la chaîne P et le texte S à partir de la position $i$ ;
   • Si la chaîne correspond, terminer le traitement et retourner $i$ comme position du début de l'occurrence ;
   • Sinon fixer $i=i+1$ ;
3. Terminer le traitement, aucune occurrence n'a été trouvée.

Cette procédure peut être améliorée en arrêtant la comparaison de la deuxième étape dès qu'un caractère différent est détecté.

Cette approche a un inconvénient : après une comparaison infructueuse, la comparaison suivante débutera à la position $i+1$, sans tenir aucun compte de celles qui ont déjà eu lieu à l'itération précédente, à la position $i$. Dans le pire cas, l'approche naïve a un coût qui est $O(m\cdot n)$, où $m$ est la longueur du motif P et $n$ la longueur du texte S.

L'algorithme de Knuth-Morris-Pratt, en revanche, examine d'abord la chaîne P et en déduit des informations permettant de ne pas comparer chaque caractère plus d'une fois.

Phases

1. La première phase de l'algorithme construit un tableau, indiquant pour chaque position un « décalage », c'est-à-dire la prochaine position où peut se trouver une occurrence potentielle de la chaîne.
2. La deuxième phase effectue la recherche à proprement parler, en comparant les caractères de la chaîne et ceux du texte. En cas de différence, il utilise le tableau pour connaître le décalage à prendre en compte pour continuer la recherche sans retour en arrière.

Exemple

Pour présenter le principe de fonctionnement de l'algorithme, un exemple particulier est considéré : la chaîne $P$ vaut ABCDABD et le texte $S$ est ABC ABCDAB ABCDABCDABDE.

Notations : Pour représenter les chaînes de caractères, cet article utilise des tableaux dont les indices débutent à zéro. Ainsi, la lettre C de la chaîne $P$ sera notée $P[2]$.

On désigne par $m$ la position dans le texte $S$ à laquelle la chaîne $P$ est en cours de vérification (c'est-à-dire la position de la partie gauche de $P$), et $i$ la position du caractère actuellement vérifié dans $P$.

L'algorithme démarre en testant la correspondance des caractères les uns après les autres. Au début, $m=0$ et $i=0$. A la quatrième étape, $m=0$ et $i=3$. A ce moment là, $S[3]$ est un espace et $P[3]=D$, la correspondance n'est donc pas possible.

              1         2
    01234567890123456789012
m : v
S : ABC ABCDAB ABCDABCDABDE
P : ABCDABD
i :    ^
    0123456

Plutôt que de recommencer avec $m=1$, l'algorithme remarque qu'aucun A n'est présent dans $S$ entre les positions 1 et 3. En conséquence, après avoir testé tous les caractères précédents, l'algorithme sait qu'il n'a aucune chance de trouver le début d'une correspondance s'il vérifie à nouveau. De ce fait, l'algorithme avance jusqu'au caractère suivant, en posant $m=4$ et $i=0$.

              1         2
    01234567890123456789012
m :     v
S : ABC ABCDAB ABCDABCDABDE
P :     ABCDABD
i :     ^
        0123456

Une correspondance presque complète est obtenue. Mais lorsque $i=6$, la vérification échoue.

              1         2
    01234567890123456789012
m :     v
S : ABC ABCDAB ABCDABCDABDE
P :     ABCDABD
i :           ^
        0123456

Toutefois, juste avant la fin de cette correspondance partielle, l'algorithme est passé sur le motif AB, qui pourrait correspondre au début d'une autre correspondance. Cette information doit donc être prise en compte. Comme l'algorithme sait déjà que ces deux premiers caractères correspondent aux deux caractères précédant la position courante, il n'est pas nécessaire de les revérifier. Ainsi, l'algorithme reprend son traitement au caractère courant, avec $m=8$ et $i=2$.

              1         2
    01234567890123456789012
m :         v
S : ABC ABCDAB ABCDABCDABDE
P :         ABCDABD
i :           ^
            0123456

Cette vérification échoue immédiatement (C ne correspond pas à l'espace en $S[10]$). Comme la chaîne ne contient aucune espace (comme dans la première étape), l'algorithme poursuit la recherche avec $m=11$ et en réinitialisant $i=0$.

              1         2
    01234567890123456789012
m :            v
S : ABC ABCDAB ABCDABCDABDE
P :            ABCDABD
i :            ^
               0123456

À nouveau, l'algorithme trouve une correspondance partielle ABCDAB, mais le caractère suivant C ne correspond pas au caractère final D de la chaîne.

              1         2
    01234567890123456789012
m :            v
S : ABC ABCDAB ABCDABCDABDE
P :            ABCDABD
i :                  ^
               0123456

Avec le même raisonnement que précédemment, l'algorithme reprend avec $m=15$, pour démarrer à la chaîne de deux caractères AB menant à la position courante, en fixant $i=2$, nouvelle position courante.

              1         2
    01234567890123456789012
m :                v
S : ABC ABCDAB ABCDABCDABDE
P :                ABCDABD
i :                  ^
                   0123456

Cette fois, la correspondance est complète, l'algorithme retourne la position 15 (c'est-à-dire $m$) : à partir de la position 15, on peut lire le motif ABCDABD.

              1         2
    01234567890123456789012
m :                v
S : ABC ABCDAB ABCDABCDABDE
P :                ABCDABD
i :                      ^
                   0123456

L'algorithme de recherche

L'exemple précédent illustre de façon instructive le principe de l'algorithme. Il suppose l'existence d'un tableau donnant les « correspondances partielles » (décrit plus bas), indiquant où chercher le début potentiel de la prochaine occurrence, dans le cas où la vérification de l'occurrence potentielle actuelle échoue. Pour le moment, ce tableau, désigné par $T$, peut être considéré comme une boîte noire ayant la propriété suivante : si l'on dispose d'une correspondance partielle de $S[m]$ à $S[m+i-1]$, mais qui échoue lors de la comparaison entre $S[m+i]$ et $P[i]$, alors la prochaine occurrence potentielle démarre à la position $m+i-T[i-1]$. En particulier, $T[-1]$ existe et est défini à $-1$. Étant donné ce tableau, l'algorithme est relativement simple :

1. Fixer $i=m=0$. Supposons que $P$ a une longueur de $n$ caractères, et $S$, de $l$ caractères ;
2. Si $m+i=l$, alors terminer le traitement, aucune correspondance n'a été trouvée. Sinon, comparer $P[i]$ et $S[m+i]$ ;
   • S'ils sont égaux, fixer $i=i+1$. Si $i=n$, alors la correspondance est complète. Terminer le traitement et retourner $m$ comme position du début de la correspondance ;
   • S'ils sont différents, fixer $e=T[i-1]$. Fixer $m=m+i-e$, et si $i>0$, fixer $i=e$ ;
3. Reprendre à l'étape n^o 2.

Cette description met en œuvre l'algorithme appliqué dans l'exemple précédent. À chaque échec de la vérification, le tableau est consulté pour trouver le début de la prochaine occurrence potentielle, et les compteurs sont mis à jour en conséquence. De ce fait, la vérification des caractères n'est jamais effectuée vers l'arrière. En particulier, chaque caractère n'est vérifié qu'une seule fois (bien qu'il puisse être possiblement écarté plusieurs fois à la suite de l'échec de correspondances. Voir plus bas pour l'analyse de l'efficacité de l'algorithme).

Exemple de code de l'algorithme de recherche

Le morceau de code C qui suit est une mise en œuvre de cet algorithme, pour des chaines de caractères 8 bits. Afin de pallier les limitations intrinsèques des tableaux en C, les indices sont décalés d'une unité, c'est-à-dire que $T[i]$ dans le code est équivalent à $T[i+1]$ dans la description ci-dessus.

code de l'algorithme de recherche

int kmp_recherche(char *P, char *S)
{
    extern int T[];
    int m = 0;
    int i = 0;

    // Tant que l'on n'a pas atteint la fin de la chaîne S ou de la chaîne P.
    while (S[m + i] != '\0' && P[i] != '\0')
    {
        if (S[m + i] == P[i])
        {
                              // Si on a encore une correspondance
            ++i;              // alors on regarde la lettre suivante
        }
        else
        {
            // sinon
            m += i - T[i];    /* la prochaine correspondance partielle possible est à T[i]
                                 lettre avant celle qu'on vient de regarder. */

            if (i > 0)
                i = T[i];     /* Puisque l'on sait que les T[i]-1 premières lettres à partir
                                 de m sont bonnes, il suffit de regarder P à partir de la T[i]ème
                                 position. Pour S on peut remarquer que on m+i est maintenant
                                 égale à (m+i-T[i])+(T[i]) avec les anciennes valeurs. Ce qui
                                 montre qu'on ne retourne pas en arrière. */
        }
    }

    //Quand on a fini de parcourir une des deux chaines
    if (P[i] == '\0')
    {
        //si la chaine P est finie alors on a trouvé une correspondance à la place m
        return m;
    }
    else
    {                    /* Sinon c'est qu'il n'existe pas de correspondance de
                            P dans S donc on renvoie un nombre impossible */
        return m + i;    /* m est forcément le nombre de caractères de S, donc
                            m+1 est impossible. On pourrait aussi renvoyer -1 */
    }
}

 

Efficacité de l'algorithme de recherche

En supposant l'existence préalable du tableau $T$, la phase « recherche » de l'algorithme de Knuth-Morris-Pratt est de complexité O$(l)$, où $l$ désigne la longueur de $S$. Si l'on exclut les traitements supplémentaires fixes induits par l'entrée et la sortie de la fonction, tous les traitements sont effectués dans la boucle principale. Pour calculer une limite sur le nombre d'itérations, une première observation à propos de la nature de $T$ est nécessaire. Par définition, il est construit de sorte que si une correspondance partielle débutant à $S[m]$ échoue lors de la comparaison entre $S[m+i]$ et $P[i]$, alors la prochaine correspondance potentielle ne débute pas avant $S[m+(i-T[i])]$. En particulier, la prochaine correspondance potentielle doit se trouver à une position supérieure à $m$, de sorte que $T[i]<i$.

Partant de ce fait, on montre que la boucle s'exécute au plus $l$ fois. À chaque itération, elle exécute une des deux branches de l'instruction if.

• La première branche augmente invariablement $i$ et ne modifie pas $m$, ce qui fait que l'index $m+i$ du caractère actuellement vérifié dans la chaîne $S$ est augmenté.
• La seconde branche ajoute $i-T[i]$ à $m$. Comme nous l'avons vu, $i-T[i]$ est toujours positif. Ainsi, la position $m$ du début de la correspondance potentielle actuelle est augmentée.

La boucle prend fin si $S[m+i]='\backslash 0'$, ce qui signifie, en tenant compte de la convention C spécifiant qu'un caractère NUL désigne la fin d'une chaîne, que $m+i=l$. En conséquence, chaque branche de l'instruction if peut être parcourue au plus $l$ fois, puisqu'elles augmentent respectivement $m+i$ ou $m$, et que $m\leq m+i$, ainsi si $m=l$, alors $m+i\geq l$, et comme l'augmentation à chaque itération est au minimum d'une unité, $m+i=l$ a nécessairement été vérifié par le passé.

Ainsi, la boucle est exécutée au plus $2l$ fois, établissant par là-même une complexité algorithmique en $O(l)$.

Le tableau des « correspondances partielles »

L'objectif de ce tableau est de permettre à l'algorithme de ne pas tester chaque caractère du texte plus d'une fois. L'observation-clé, à propos de la nature linéaire de la recherche, qui permet à cet algorithme de fonctionner, est qu'en ayant vérifié une partie du texte avec une « première portion » de la chaîne, il est possible de déterminer à quelles positions peuvent commencer les possibles occurrences qui suivent, et qui continuent de correspondre à la position courante dans le texte. En d'autres termes, les motifs (les sous-parties de la chaîne) sont « pré-recherchés » dans la chaîne, et une liste est établie, indiquant toutes les positions possibles auxquelles continuer pour sauter un maximum de caractères inutiles, sans toutefois sacrifier aucune occurrence potentielle.

Pour chaque position dans la chaîne, il faut déterminer la longueur du motif initial le plus long, qui se termine à la position courante, mais qui ne permet pas une correspondance complète (et qui vient donc très probablement d'échouer). Ainsi, $T[i]$ désigne exactement la longueur du motif initial le plus long se terminant à $P[i]$. Par convention, la chaîne vide est de longueur nulle. Comme un échec au tout début de la chaîne est un cas particulier (la possibilité de backtracking n'existe pas), on pose $T[-1]=-1$, tel que discuté précédemment.

En re-considérant l'exemple ABCDABD présenté précédemment, on peut établir qu'il fonctionne sur ce principe, et qu'il bénéficie de la même efficacité pour cette raison. On fixe $T[-1]=-1$.

       -1  0  1  2  3  4  5  6
i    :  v
P[i] :     A  B  C  D  A  B  D
T[i] : -1

Comme $P[0]$ n'apparaît qu'à la fin du motif initial complet, on fixe également $T[0]=0$.

       -1  0  1  2  3  4  5  6
i    :     v
P[i] :     A  B  C  D  A  B  D
T[i] : -1  0

Pour déterminer $T[1]$, l'algorithme doit trouver un motif terminal dans AB qui soit aussi un motif initial de la chaîne. Mais le seul motif terminal possible de AB est B, qui n'est pas un motif initial de la chaîne. De ce fait, $T[1]=0$.

       -1  0  1  2  3  4  5  6
i    :        v
P[i] :     A  B  C  D  A  B  D
T[i] : -1  0  0

En poursuivant avec C, on remarque qu'il existe un raccourci pour vérifier tous les motifs terminaux. Considérons que l'algorithme ait trouvé un motif terminal de deux caractères de long, prenant fin sur le C ; alors le premier caractère de ce motif est un motif initial d'un motif initial de la chaîne, et par conséquent, un motif initial lui-même. De plus, il prend fin sur le B, pour lequel nous savons que la correspondance n'est pas possible. Ainsi, il n'est pas nécessaire de se soucier des motifs de deux caractères de longueur, et comme dans le cas précédent, l'unique motif de longueur unitaire ne correspond pas. Donc $T[2]=0$.

De même pour D, on obtient $T[3]=0$.

       -1  0  1  2  3  4  5  6
i    :              v
P[i] :     A  B  C  D  A  B  D
T[i] : -1  0  0  0  0

Pour le A suivant, le principe précédent nous montre que le motif le plus long à prendre en compte contient 1 caractère, et dans ce cas, A correspond. Ainsi, $T[4]=1$.

       -1  0  1  2  3  4  5  6
i    :                 v
P[i] :     A  B  C  D  A  B  D
T[i] : -1  0  0  0  0  1
 
P    :     A  B  C  D  A  B  D
P    :                 A  B  C  D  A  B  D

La même logique est appliquée sur B. Si l'algorithme avait trouvé un motif démarrant avant le A précédent, et se poursuivant avec le B actuellement considéré, alors il aurait lui-même un motif initial correct se terminant par A bien que débutant avant A, ce qui contredit le fait que l'algorithme a déjà trouvé que A est la première occurrence d'un motif s'y terminant. En conséquence, il n'est pas nécessaire de regarder avant le A pour y chercher un motif pour B. En fait, en le vérifiant, l'algorithme trouve qu'il continue par B et que B est la deuxième lettre du motif dont A est la première lettre. De ce fait, l'entrée pour B dans $T$ est supérieur d'une unité à celle de A, c'est-à-dire $T[5]=2$.

       -1  0  1  2  3  4  5  6
i    :                    v
P[i] :     A  B  C  D  A  B  D
T[i] : -1  0  0  0  0  1  2
 
P    :     A  B  C  D  A  B  D
P    :                 A  B  C  D  A  B  D

Enfin, le motif ne continue pas de B vers D. Le raisonnement précédent montre que si un motif d'une longueur supérieure à 1 était trouvé sur D, alors il devrait contenir un motif se terminant sur B. Comme le motif courant ne correspond pas, il doit être plus court. Mais le motif courant est un motif initial de la chaîne se terminant à la deuxième position. Donc ce nouveau motif potentiel devrait lui aussi se terminer à la deuxième position, et nous avons déjà vu qu'il n'y en avait aucun. Comme D n'est pas lui-même un motif, $T[6]=0$.

       -1  0  1  2  3  4  5  6
i    :                       v
P[i] :     A  B  C  D  A  B  D
T[i] : -1  0  0  0  0  1  2  0

D'où le tableau suivant :

$i$	-1	0	1	2	3	4	5	6
$P[i]$		A	B	C	D	A	B	D
$T[i]$	-1	0	0	0	0	1	2	0

Algorithme de construction du tableau

L'exemple précédent illustre la technique générale pour produire le tableau avec le moins de soucis possible. Le principe est le même que pour la recherche générale : la majorité du traitement est déjà fait lors de l'arrivée sur une nouvelle position, il ne reste que peu de traitement pour passer à la suivante. Suit la description de l'algorithme. Pour éliminer des cas particuliers, la convention suivante est appliquée : $P[-1]$ existe et sa valeur est différente de tous les caractères possibles de $P$.

1. Fixer $T[-1]=-1$. Supposons que $P$ contienne $n$ caractères ;
2. Fixer $i=0$ et $j=-1$ ;
3. Si $i=n$, terminer le traitement. Sinon, comparer $P[i]$ et $P[j]$.
   • S'ils sont égaux, fixer $T[i]=j+1$, $j=j+1$ et $i=i+1$ ;
   • Sinon, et si $j>0$, fixer $j=T[j-1]$ ;
   • Sinon, fixer $T[i]=0$, $i=i+1$ et $j=0$.
4. Reprendre à l'étape n^o 3.

Exemple de code de l'algorithme de construction du tableau

Le morceau de code C qui suit est une mise en œuvre de cet algorithme. Comme pour l'algorithme de recherche, les indices de $T$ ont été augmentés de 1 afin de rendre le code C plus naturel. La variable supplémentaire c permet de simuler l'existence de $P[-1]$. Il est supposé que cette fonction, ainsi que la fonction de recherche, sont appelées au sein d'une fonction de niveau supérieur, qui gère convenablement l'allocation de la mémoire pour le tableau $T$.

void kmp_tableau(char *P)
{
    extern int T[];
    int i = 0;
    int j = -1;
    char c = '\0';              //Donc c=P[-1]
    
    T[0] = j;                   //c'est-à-dire -1
    while (P[i] != '\0') {      //Tant que l'on n'a pas atteint la fin de la chaine
/* ATTENTION la condition suivante est fausse, contre exemple avec la chaine "ABABABAB", il faut plutot mettre if((P[i] == P[j]) && j < ((i+(i%2))/2)) */
        if (P[i] == c) {        /* Si P[i]==P[j] donc si le caractère qu'on regarde est le même que le caractère suivant la fin
                                 * du dernier motif initial trouvé */
            T[i + 1] = j + 1;   //alors le motif est continué, et on incrémente i et j.
            ++j;
            ++i;
        } else if (j > 0) {     //Sinon si au caractère précédent il existe un motif
            j = T[j];           //on va regarder le motif initial précédent qui peut correspondre a la lettre où l'on était.
        }
        else {                  /* Sinon j=0 ou -1, i.e. si les lettres qui précèdent la ième suivie de la ième ne peuvent
                                 * correspondre a aucun marquage initiale */
            T[i + 1] = 0;       //alors on indique qu'il n'y a aucun motif initial pour cette lettre.
            ++i;
            j = 0;              //Cette affectation ne sert en fait que lorsque j=-1.
        }
        c = P[j];
    }
}

Cependant, remplacer int j=-1; par int j=0;, T[0] = j; par T[0] = -1; permettrait de supprimer l'affectation j = 0; sans rien changer au résultat de l'algorithme. On gagne un petit peu de temps d'exécution mais on perd de la cohérence parmi les variables.

Efficacité de l'algorithme de construction du tableau

La complexité de l'algorithme de construction du tableau est $O(n)$, où $n$ désigne la longueur de $P$. À l'exception des initialisations, tout le traitement est effectué dans l'étape n^o 3. Ainsi, il suffit de montrer que cette étape s'exécute en $O(n)$, ce qui est fait par la suite en examinant simultanément les quantités $i$ et $i-j$.

• Dans la première branche, $i-j$ est préservé, car $i$ et $j$ sont augmentés simultanément. La quantité $i$, elle, est donc augmentée.
• Dans la deuxième branche, $j$ est remplacé par $T[j-1]$, qui est toujours strictement inférieur à $j$ (voir plus haut), ce qui augmente $i-j$.
• Dans la troisième branche, $i$ est augmenté, mais pas $j$, donc $i$ et $i-j$ sont tous deux augmentés.

Comme $i\geq i-j$, cela signifie qu'à chaque étape, soit $i$, soit une quantité inférieure à $i$ augmente. Par conséquent, puisque l'algorithme s'arrête quand $i=n$, il s'arrête après au plus $2n$ itérations de l'étape n^o 3, car $i-j$ commence à $1$. Ainsi, La complexité de cet algorithme est $O(n)$.

Efficacité de l'algorithme de Knuth-Morris-Pratt

Comme les deux parties de l'algorithme ont respectivement des complexités de $O(l)$ et $O(n)$, la complexité de l'algorithme dans sa totalité est $O(n+l)$.

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.