Algorithmique ii - Recherche de motif (Knuth-Morris-Pratt)

Présentation du problème, algorithme naïf

On reprend les mêmes notations que le chapitre Ordre lexicographique. La description du problème est simple et on le rencontre fréquemment, il s'agit de chercher un mot dans un texte (on parle de recherche de motif en théorie des langage et ce terme recouvre des situations bien plus générales que la simple recherche d'un mot). Plus précisément, on se donne deux mots \(u\) et \(v\) sur un alphabet fini \(A\) et on cherche la/les position(s) de \(u\) dans \(v\). Ici nous nous contenterons de chercher la première occurence de \(u\) dans \(v\), c'est-à-dire le plus petit indice \(k\), s'il existe, tel que \begin{equation} \forall i\in[1,|u|],\quad u_i=v_{k+i-1}. \end{equation} Il est implicite dans ce contexte que \(|u|<\!\!<|v|\). Commençons par étudier la méthode naïve.

De manière imagée, on aligne à gauche les symboles du motif \(u\) à chercher avec ceux du texte \(v\). On va décaler le motif \(u\) le long de \(v\) jusqu'à ce que tous leurs symboles coïncident. Pour cela nous utilisons deux indices \(i\) et \(k\) pour indexer respectivement \(u\) et \(v\). L'indice de décalage \(k\) fixe le début de l'alignement entre \(u\) et \(v\) et l'indice \(i\) fixe la position de la lettre du motif à comparer, i.e \(u_i\). Initialement \(k=1\) et \(i=1\). Considérons par exemple le motif \(u\) et le texte \(v\) suivants :

Vous pouvez modifier les valeurs mais les ex­pli­ca­tions s'appuient sur les valeurs initiales (bouton Réinitialiser)

\(\phantom{v}u=\)
\(\phantom{u}v=\)

Nous avons \(|u|=\) et \(|v|=\) . Dans la table ci-dessous, la lettre du motif \(u_i\) qui est comparée avec celles du texte \(v\) est encadrée en poin­til­lés (jaune quand elle est égale à celle du texte, en bleu sinon).

En incrémentant \(k\), l'algorithme naïf décale \(u\) vers la droite jusqu'à ce que la première lettre \(u_1\) du motif coïncide avec la lettre \(v_k\) du texte ou qu'il ne reste plus suffisamment de lettres dans le texte pour aligner le motif. Dans l'exemple proposé on trouve une première coïncidence pour un décalage \(k=3\) (cf. ligne #3 de la table ci-dessus). On compare alors les lettres suivantes en incrémentant \(i\) tant qu'elles coïncident (dans l'exemple, pour ce premier décalage \(k=3\), on atteint la valeur \(i=5\)). Soit on a reconnu l'intégralité du motif \(u\) et \(i = |u|\), soit on décale à nouveau le motif (à la ligne #8 puisque \({\color{#48F}\verb+N+}\not=\verb+C+\) à la ligne #7).

Dans le pire des cas, cet algorithme naïf a une complexité quadratique en \(\Theta(mn)\) comparaisons si \(m\) et \(n\) désignent respectivement les longueurs des mots \(u\) et \(v\). Cette situation défavorable correspond à un motif et à un texte tous deux constitués par la répétition d'un même symbole, sauf le dernier symbole du motif qui doit être différent, soit \(u=x^{m-1}y\) et \(v=x^n\) en notant \(x\) et \(y\) ces deux symboles.

On peut à présent écrire cet algorithme ChercherNaif :

ChercherNaif(u,v):valeur;
données
   u,v: mots
variables
   i,k: entiers
debut
   i ← 1
   k ← 1
   TQ (i ≤ #u) ET (k ≤ #v - #u + 1) FAIRE  
      SI (u[i] = v[k + i - 1]) ALORS
         i ← i + 1
      SINON
         k ← k + 1
         i ← 1
      FSI
   FTQ
   SI (i > #u) ALORS
      retourner k       
   SINON
      retourner 0         
   FSI
fin
Démontrez que dans le premier test SI de l'algorithme ChercherNaif on a toujours \(i\in[1,|u|]\) et \(k + i - 1\in[1,|v|]\). Quelles instances correspondent au cas favorable ? En déduire la fonction de complexité correspondante.
Modifier l'algorithme ChercherNaif pour qu'il renvoie la liste de toutes les positions où se trouve le motif \(u\) dans \(v\).

L'algorithme KMP

Pour gagner du temps, l'algorithme kmp élimine toutes les comparaisons de l'algorithme naïf qui peuvent être évitées grâce aux précédentes comparaisons. La méthode est subtile et s'appuie au préalable sur une observation attentive des comparaisons effectuées dans l'algorithme naïf. Dans l'exemple, après un début de reconnaissance du motif \(u\) dans le texte \(v\) (étapes #3 à #6 avec \(\color{#FF0}\verb+C A H I+\)), l'analyse échoue à la 5ème comparaison (étape #7) quand \(\color{#48F}\verb+N+\) est comparée à \(\verb+C+\). En remarquant que la lettre \(\verb+C+\) ne figure dans aucune des 3 lettres \(\verb+A H I+\) du texte, il est inutile de comparer \(\verb+C+\) avec ces lettres à nouveau comme cela est fait aux étapes #8 à #10. On peut donc décaler le motif de 4 positions et sauter à l'étape #11 directement.

Plutôt que de continuer à débusquer les situations caractéristiques de l'approche naïve, observons plutôt le déroulement de l'algorithme kmp pour les mettre en évidence et comprendre comment décaler le motif plus rapidement en cas d'échec d'une comparaison :

\(\phantom{v}u=\)     \(|u|=\)
\(\phantom{u}v=\)     \(|v|=\)

En cas de réussite d'une comparaison, l'algorithme kmp se comporte strictement de la même façon que l'algorithme naïf. C'est en cas d'échec qu'il optimise le décalage du motif. Nous aurons besoin des définitions suivantes :
Soit \(A\) un alphabet fini et \(u\) un mot de \(A^*\). On appelle facteur de \(u\) tout mot \(v\in A^*\) tel qu'il existe \(p,s\in A^*\) et \(u=p.v.s\) où \(.\) désigne la loi de concaténation. On appelle facteur propre d'un mot \(u\) tout facteur différent du mot vide \(\varepsilon\) et du mot \(u\). Soient \(p,s\in A^*\) tels que \(u=p.s\), on dit que \(p\) est un préfixe et que \(s\) est un suffixe de \(u\). On appelle bord de \(u\) tout facteur qui est à la fois préfixe et suffixe de \(u\).
Le mot \(\color{#FFF}\verb+B O N+\) est un préfixe du mot \({\color{#FFF}\verb+B O N+}\verb+ J O U R+\) alors que \(\color{#FFF}\verb+D E S+\) est un suffixe du mot \(\verb+M O N+{\color{#FFF}\verb+ D E S +}\). Le mot \(\verb+B A B A+\) est un bord du mot \(\verb+ B A B A B A+\).

Le motif \({\color{#FF0}\verb+C A H+}\verb+ I N +{\color{#FF0}\verb+C A H+}\verb+ A+\) contient le mot \({\color{#FF0}\verb+C A H+}\) qui apparaît à la fois en tant que préfixe et en tant que facteur propre. Supposons qu'une partie du motif \(u\) ait été reconnu et que la comparaison échoue à la \(j\)-ème lettre d'un tel facteur, ici la troisième lettre \({\color{#FF0}\verb+C A +}\color{#48F}\verb+H+\) à l'étape #15 de la table 2 ci-dessus. Il est évident qu'aucune des 3 lettres du préfixe \({\color{#FF0}\verb+C A H+}\) ne pourra coincider plus tard, on peut donc décaler le motif après la position \(k+1\) du texte et reprendre l'analyse à la première lettre de \(u\) (cf. étape #16 dans la table).

En revanche, si l'échec a lieu sur la lettre qui suit le facteur \({\color{#FF0}\verb+C A H +}\) (lettre \(\color{#48F}\verb+A+\) à l'étape #24), celle qui suit le préfixe \({\color{#FF0}\verb+C A H+}\) (lettre \({\color{#FF0}\verb+I+}\) à l'étape #25) peut convenir, il faut donc décaler le préfixe à la position du facteur et reprendre l'analyse au même endroit.

Reste à déterminer les décalages à effectuer dans le cadre général. Il faut connaître pour chaque lettre \(u_i\) du motif à comparer si elle termine un bord du mot \(u[1\!:\!i]\) et sa position dans ce bord le cas échéant. Cette information ne dépend que du motif \(u\) et on peut la précalculer dans une table \(B[1\!:\!|u|]\) de \(|u|\) valeurs entières contenant à l'indice \(i\) la longueur du plus grand bord du mot \(u[1\!:\!j]\) :

\begin{equation} \begin{matrix} &1 &2 &3 &4 &5 &6 &7 &8 &9\\ u &\color{#FF0}\verb+C+ &\color{#FF0}\verb+A+ &\color{#FF0}\verb+H+ &\verb+I+ &\verb+N+ &\color{#FF0}\verb+C+ &\color{#FF0}\verb+A+ &\color{#FF0}\verb+H+ &\verb+A+\\ B &0 &0 &0 &0 &0 &1 &2 &3 &0 \end{matrix} \end{equation}
Calculez la table \(B\) des plus grands bords du mot \[\verb+P E T I T A P P E T I T+\] Écrivez un algorithme BordsMax(u) qui renvoie la table des plus grands bords des \(|u|\) préfixes non-vides du mot \(u\). Calculez sa complexité.

On peut à présent résumer le fonctionnement de l'algorithme. On calcule la table \(B\) des plus longs bords des préfixes non-vides de \(u\) au préalable. On initialise les deux indices \(k\) du texte et \(i\) du motif à 1 et on procède de la même manière que pour l'algorithme ChercherNaif sauf si les lettres diffèrent, i.e. sauf si \(u_i\not=v_{k+i-1}\) et qu'il faut gérer les décalages différemment. Deux cas se présentent alors :

  1. \(B[i]>0\) donc \(u_i\) est une lettre d'un facteur, auquel cas il faut décaler le motif de \(i\) positions \(\color{#FF0}k\leftarrow k + i\) et reprendre l'analyse au premier symbole \(u_1\) du motif (\(\color{#FF0}i\leftarrow 1\)) ;
  2. \(B[i]=0\) donc \(u_i\) n'est pas une lettre d'un facteur, auquel cas il faut aligner le motif sur le facteur qui précède immédiatement (éventuellement), i.e. \(\color{#48F}k\leftarrow k + i - B[i-1] - 1\) et reprendre l'analyse au même endroit, soit \(\color{#48F}i\leftarrow B[i-1] + 1\). S'il s'agit de la première lettre du motif, il suffit d'incrémenter \(k\), ce qui peut être intégré dans la situation précédente.

ChercherKmp(u,v):valeur;
données
   u,v: mots
variables
   i,k: entiers
   B: liste d'entiers
debut
   i ← 1
   k ← 1
   B ← BordsMax(u);
   TQ (i ≤ #u) ET (k ≤ #v - #u + 1) FAIRE  
      SI (u[i] = v[k + i - 1]) ALORS
         i ← i + 1
      SINON SI (B[i] > 0) OU (i = 1) ALORS
         k ← k + i
         i ← 1
      SINON
         k ← k + i - B[i - 1] - 1
         i ← B[i - 1] + 1
      FSI
   FTQ
   SI (i > #u) ALORS
      retourner k       
   SINON
      retourner 0         
   FSI
fin
On suppose que la comparaison de la \(i\)-ème lettre du motif \(u\) avec le texte \(v\) échoue, i.e. \(u_i\not= v_{k+i-1}\). Dans le cas où \(B[i]>0\), montrez qu'aucun décalage du motif \(u\) de \(l\) positions avec \(l < i\) ne le fait coïncider avec le texte. Dans le cas où \(B[i]=0\) et \(i>1\), montrez qu'après un décalage du motif de \(s:=i-B[i-1]-1\) positions, toutes les lettres d'indice \(l\leq B[i-1]\) du motif coïncident avec le texte \(v\), puis montrez qu'aucun décalage de longueur \(\leq s\) ne fait coïncider le motif avec le texte.
Modifier l'algorithme ChercherKmp pour qu'il renvoie la liste de toutes les positions où se trouve le motif \(u\) dans \(v\).

Complexité

Notons \(m:=|u|\) et \(n:=|v|\). Dans le meilleur des cas, le motif \(u\) est un préfixe du texte \(v\), il faut donc \(\Theta(m)\) comparaisons plus le coût de la construction de la table \(B\) des longueurs des plus longs bords en \(\Theta(m)\) également. Donc \[\check T(n,m)=\Theta(m)+\Theta(m) = \Theta(m).\] Le pire des cas correspond à la même situation que pour l'algorithme naïf, à savoir \(u=x^{m-1}y\) et \(v=x^n\). La table des longueurs des plus longs bords est \[B=[0,1,2,3,\ldots,m-2,0].\] On se retrouve dans la deuxième situation décrite plus haut. L'échec se produisant sur la dernière lettre \(u_m=y\), on a tout d'abord \(m-1\) coïncidences puis systématiquement un décalage du motif d'une position mais la comparaison suivante (qui réussit) se fait à la même position du texte, on compare donc systématiquement deux fois chaque lettre \(x\) du texte, d'abord avec \(y\) puis avec \(x\). Il reste \(n-m\) lettres à comparer, on a donc \(m+2(n-m)=2n-m\) comparaisons au final. Si l'on rajoute le coût \(\Theta(m)\) de la construction de la table, on obtient finalement \[\hat T(n,m)=\Theta(n+m)+\Theta(m) = \Theta(m+n).\]

Travaux pratiques

Écrivez les fonctions Python correspondant aux deux algorithmes de recherche, naïf et kmp. Vérifiez empiriquement que la complexité dans le pire des cas est bien conforme à la théorie.