Algorithme de Knuth-Morris-Pratt

Afin de comprendre la logique de 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 ${\displaystyle 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 ${\displaystyle i}$ ;
   • Si la chaîne correspond, terminer le traitement et retourner ${\displaystyle i}$ comme position du début de l'occurrence ;
   • Sinon fixer ${\displaystyle 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 ${\displaystyle i+1}$, sans tenir aucun compte de celles qui ont déjà eu lieu à l'itération précédente, à la position ${\displaystyle i}$. L'algorithme de Knuth-Morris-Pratt 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.

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.

Pour présenter le principe de fonctionnement de l'algorithme, un exemple particulier est considéré : la chaîne ${\displaystyle P}$ vaut ABCDABD et le texte ${\displaystyle 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 ${\displaystyle P}$ sera notée ${\displaystyle P[2]}$.

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

L'algorithme démarre en testant la correspondance des caractères les uns après les autres. Au début, ${\displaystyle m=0}$ et ${\displaystyle i=0}$. A la quatrième étape, ${\displaystyle m=0}$ et ${\displaystyle i=3}$. A ce moment là, ${\displaystyle S[3]}$ est un espace et ${\displaystyle 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 ${\displaystyle m=1}$, l'algorithme remarque qu'aucun A n'est présent dans ${\displaystyle 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 ${\displaystyle m=4}$ et ${\displaystyle i=0}$.

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

Une correspondance presque complète est obtenue. Mais lorsque ${\displaystyle 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 ${\displaystyle m=8}$ et ${\displaystyle 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 ${\displaystyle S[10]}$). Comme la chaîne ne contient aucune espace (comme dans la première étape), l'algorithme poursuit la recherche avec ${\displaystyle m=11}$ et en réinitialisant ${\displaystyle 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 ${\displaystyle m=15}$, pour démarrer à la chaîne de deux caractères AB menant à la position courante, en fixant ${\displaystyle 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 ${\displaystyle 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'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 ${\displaystyle T}$, peut être considéré comme une boîte noire ayant la propriété suivante : si l'on dispose d'une correspondance partielle de ${\displaystyle S[m]}$ à ${\displaystyle S[m+i-1]}$, mais qui échoue lors de la comparaison entre ${\displaystyle S[m+i]}$ et ${\displaystyle P[i]}$, alors la prochaine occurrence potentielle démarre à la position ${\displaystyle m+i-T[i-1]}$. En particulier, ${\displaystyle T[-1]}$ existe et est défini à ${\displaystyle -1}$. Étant donné ce tableau, l'algorithme est relativement simple :

1. Fixer ${\displaystyle i=m=0}$. Supposons que ${\displaystyle P}$ a une longueur de ${\displaystyle n}$ caractères, et ${\displaystyle S}$, de ${\displaystyle l}$ caractères ;
2. Si ${\displaystyle m+i=l}$, alors terminer le traitement, aucune correspondance n'a été trouvée. Sinon, comparer ${\displaystyle P[i]}$ et ${\displaystyle S[m+i]}$ ;
   • S'ils sont égaux, fixer ${\displaystyle i=i+1}$. Si ${\displaystyle i=n}$, alors la correspondance est complète. Terminer le traitement et retourner ${\displaystyle m}$ comme position du début de la correspondance ;
   • S'ils sont différents, fixer ${\displaystyle e=T[i-1]}$. Fixer ${\displaystyle m=m+i-e}$, et si ${\displaystyle i>0}$, fixer ${\displaystyle 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).

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 ${\displaystyle T[i]}$ dans le code est équivalent à ${\displaystyle T[i+1]}$ dans la description ci-dessus.

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 */
    }
}

En supposant l'existence préalable du tableau ${\displaystyle T}$, la phase « recherche » de l'algorithme de Knuth-Morris-Pratt est de complexité O${\displaystyle (l)}$, où ${\displaystyle l}$ désigne la longueur de ${\displaystyle 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 ${\displaystyle T}$ est nécessaire. Par définition, il est construit de sorte que si une correspondance partielle débutant à ${\displaystyle S[m]}$ échoue lors de la comparaison entre ${\displaystyle S[m+i]}$ et ${\displaystyle P[i]}$, alors la prochaine correspondance potentielle ne débute pas avant ${\displaystyle S[m+(i-T[i])]}$. En particulier, la prochaine correspondance potentielle doit se trouver à une position supérieure à ${\displaystyle m}$, de sorte que ${\displaystyle T[i]<i}$.

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

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

La boucle prend fin si ${\displaystyle 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 ${\displaystyle m+i=l}$. En conséquence, chaque branche de l'instruction if peut être parcourue au plus ${\displaystyle l}$ fois, puisqu'elles augmentent respectivement ${\displaystyle m+i}$ ou ${\displaystyle m}$, et que ${\displaystyle m\leq m+i}$, ainsi si ${\displaystyle m=l}$, alors ${\displaystyle m+i\geq l}$, et comme l'augmentation à chaque itération est au minimum d'une unité, ${\displaystyle m+i=l}$ a nécessairement été vérifié par le passé.

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

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 : ${\displaystyle P[-1]}$ existe et sa valeur est différente de tous les caractères possibles de ${\displaystyle P}$.

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

Le morceau de code C qui suit est une mise en œuvre de cet algorithme. Comme pour l'algorithme de recherche, les indices de ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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.

La complexité de l'algorithme de construction du tableau est ${\displaystyle O(n)}$, où ${\displaystyle n}$ désigne la longueur de ${\displaystyle 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 ${\displaystyle O(n)}$, ce qui est fait par la suite en examinant simultanément les quantités ${\displaystyle i}$ et ${\displaystyle i-j}$.

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

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

• Algorithme de recherche de sous-chaîne
• Algorithme de Boyer-Moore.

• (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)

• (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.

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