Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Knuth-Morris-Pratt & C°
Recherche de mots dans un texte, KMP
Article mis en ligne le 8 mai 2009
dernière modification le 25 février 2015

par Laurent Bloch, William Saurin

L'algorithme de Knuth-Morris-Pratt

L’algorithme de Knuth-Morris-Pratt

William Saurin, Laurent Bloch

Le 8 mai 2009

Nous nous intéressons à déterminer si un mot (ici un mot est une simple chaîne de caractères) figure dans un texte. Nous noterons Mot le mot et nous considérerons que les éléments successifs du mot recherché sont stockés en Mot[0], Mot[1], ... Mot[m-1] Le texte sera noté Texte et ses éléments successifs seront stockés en Texte[0], Texte[1], ... Texte[t-1].

L’indice j correspond à une progression dans le mot et l’indice i à une progression dans le texte. À un moment donné on compare le caractère d’indice i+j du texte avec le caractère d’indice j du
mot.


Algorithme force brute.

On peut imaginer positionner successivement la sous-chaîne sous le texte de manière à ce que sa première position (celle indexée par 0) soit successivement sous les chacune des positions du texte. On vérifie alors la coincidence des différents caractères superposés.

Algorithme : brute-force Données : Texte, Mot  ; le texte, et le mot recherché Résultat : la première position le mot a été trouvé, ou bien -1. Soient Ltexte la longueur du Texte Lmot la longueur du Mot pour i allant de 0 à (Ltexte - Lmot) faire j <- 0 tant que j < Lmot et Texte[i+j] = Mot[j] faire j <- j+1 fait si j = Lmot alors retourner i finsi fait si j = Lmot alors retourner i sinon retourner -1

Complexité de l’algorithme : l × m

En Scheme :

  1. (module force-brute
  2.       (main get-args))
  3.  
  4. (define (get-args args)
  5.    (print (force-brute (cadr args)
  6.                        (caddr args))))
  7.  
  8. ;; les instruments
  9.  
  10. (define (force-brute Texte Motif)
  11.    (let* ((L-Texte (string-length Texte))
  12.           (L-Motif (string-length Motif))
  13.           (DerPos-Texte (- L-Texte 1)))
  14.       (let boucle1 ((i 0)
  15.                     (j 0))
  16.          (let boucle2 ()
  17.             (if (and (< j L-Motif)
  18.                      (char=? (string-ref Texte (+ i j))
  19.                              (string-ref Motif j)))
  20.                 (begin
  21.                    (set! j (+ j 1))
  22.                    (boucle2))))
  23.          (cond ((= j L-Motif) i)
  24.                ((< i DerPos-Texte)
  25.                 (boucle1 (+ i 1) 0))
  26.                (else -1)))))

Télécharger


Exposé de l’algorithme KMP

L’idée de l’algorithme est simple : lorsque nous ne réussissons plus à faire progresser l’indice j vers la droite, en fait nous faisons progresser l’indice i mais dans ce cas nous réexaminons à nouveau des caractères du texte. Puisque nous les avons déjà vus ne pourrions nous pas nous en passer ?

La deuxième idée est que puisque les k+1 caractères du texte, de rang i à i+k, que nous venons d’examiner sont « bons » alors ce sont aussi les k+1 premiers caractères du mot : nous pouvons savoir ce qui nous arrivera d’avance uniquement en examinant d’abord les caractères du mot. Par exemple, si les n derniers caractères parmi ces k+1, soit les caractères du mot de rangs kn+1 à k, se trouvent constituer un préfixe du mot, nous pouvons recommencer la comparaison dans le texte à la position i+kn+1, et comme nous savons que les caractères i+kn+1 à i+k sont bien égaux aux n premiers caractères du mot, en fait nous allons recommencer la comparaison avec le caractère de rang i+k+1 dans le texte, et kn+1 dans le mot.

La troisième idée est celle-ci : la seconde idée consiste à exploiter le fait que si nous examinons les différents préfixes du mot, de longueurs croissantes, certains de ces préfixes vont avoir des suffixes identiques à un certain préfixe du mot lui-même, ce qui est la circonstance qui autorise le recours à la seconde idée exposée ci-dessus.

Reprenons : si les k+1 caractères de rangs i à i+k étaient « bons », c’est-à-dire égaux aux k+1 premiers caractères du mot, on peut en tirer des conséquences. Par exemple, si aucun des caractères de i+1 à i+k du texte n’est égal au premier caractère du mot, on en déduit qu’il est inutile de commencer une comparaison à ces emplacements, on peut sauter tout de suite à la position i+k+1 du texte. Par contre, si un suffixe de la chaîne Texte[i..i+k], disons Texte[i+k-m..i+k]
est un préfixe du mot, alors il faut reprendre la comparaison à la position Texte[i+k+1] du texte et à partir de la position Mot[k-m], puisque l’on sait déjà que la comparaison sera positive pour les m+1 premiers caractères.

Si la comparaison était positive pour les k+1 premiers caractères du mot, soit Texte[i..i+k] = Mot[0..k], et si en outre Texte[i+k-m..i+k] = Mot[k-m..k], alors c’est que Mot[0..m]= Mot[k-m..k]. Or ce résultat concerne uniquement Mot, est peut être pré-calculé.

Dans le cas de notre exemple : i=2, k=4, m=2.

Imaginons donc que pour tous les mots allant de 0 à k dans la chaîne nous connaissions la positions la plus grande j telle que le mot allant de 0 à j soit identique à celle allant de kj à k. Considérons que prec soit une fonction telle que prec(k) soit la valeur de j en question. Imaginons que nous ayons examiné tous les caractères du texte allant de i à i+k avec succès, c’est à dire tous ceux de la chaine de 0 à k. Nous cherchons donc à trouver quel caractère de la chaîne peut-être mis en correspondance avec le caractère i+k+1 du texte. Le caractère k+1 de la chaîne est un bon candidat mais s’il n’est pas identique à celui du texte alors le caractère prec(k)+1 de la chaîne en est autre bon candidat, si ce caractère n’est pas identique alors prec(prec (k))+1 est à nouveau un bon candidat, et ainsi de suite jusqu’à ce qu’on ait trouvé une identité ou jusqu’à ce que prec(...(prec(k))...)+1 vaille 0 et ait échoué. Dans le premier cas on examinera le caractère suivant du texte. Dans tous les cas on examine le caractère suivant du texte.


Figure 1 :


La fonction qui construit la table des préfixes est écrite selon la méthode exposée à la section  ?? plus bas.

L’algorithme KMP proprement dit

Nous supposerons donc l’existence d’un tableau Tpref qui, pour chaque position k du mot recherché à laquelle une comparaison échoue (et qui correspond donc, si nous avons commencé dans le texte à la position i, à la position i+k du texte), nous donne la position où recommencer la comparaison en évitant les positions qu’il est inutile de vérifier parce que c’est déjà fait. Ou, en d’autres termes, de combien de positions dans le texte il faut revenir en arrière à partir de i+k. Soit :

  • si nous avons comparé fructueusement de Texte[i] à Texte[i+k-1], mais échoué en comparant Texte[i+k] à Mot[k], alors la comparaison doit pour avoir des chances de réussite reprendre en Texte[i+k-Tpref[k-1]].Notons que Tpref[-1] existe et vaut −1, parce que la comparaison peut échouer au premier caractère du texte, Texte[0], et donc du mot, Mot[0], et alors il faut recommencer en Texte[1].

Nous verrons plus bas la construction de Tpref, pour l’instant supposons ce tableau construit et donné par la procédure kmp:tableau. Voici le principe de l’algorithme :

Algorithme : kmp :KMP Données : Mot, Texte Résultat : la position à laquelle est Mot dans Texte Soient Tpref <- kmp :tableau(Mot) Lmot <- longueur(Mot) Ltexte <- longueur(Texte) i <- 0 j <- 0 tant que j < Lmot et j+i < Ltexte faire si Texte[j+i] = Mot[j] alors j <- j+1 sinon i <- j+i - Tpref[j] si j > 0 alors j <- Tpref[j] finsi finsi fait si j = Lmot alors retourner i sinon retourner -1 fin

En moyenne cet algorithme s’exécute en un temps moyen qui croît
comme O(n).

Signalons l’excellent article de Wikipédia, en
français
.

En Scheme :

  1. (module kmp
  2.    (main appel)
  3.    (import kmp-tableau))
  4.  
  5. (define (appel args)
  6.    (print (kmp:KMP (cadr args) (caddr args))))
  7.  
  8. (define (kmp:KMP Mot Texte)
  9.    (let ((Tpref (kmp:tableau Mot))
  10.          (L-texte (string-length Texte))
  11.          (L-mot (string-length Mot))
  12.          (i 0)
  13.          (j 0))
  14.       (let boucle ()
  15.          (if (char=? (string-ref Texte (+ i j))
  16.                      (string-ref Mot j))
  17.              (set! j (+ j 1))
  18.              (begin
  19.                 (set! i (- (+ i j) (vector-ref Tpref j)))
  20.                 (if (> j 0)
  21.                     (set! j (vector-ref Tpref j)))))
  22.          (if (and (< (+ i j) L-texte)
  23.                   (< j L-mot))
  24.              (boucle)))
  25.       (if (= j L-mot)
  26.           i
  27.           (+ i j))))

Télécharger

Construction de la table des préfixes

Le but de la construction de la table des préfixes est de déterminer, en fonction du résultat d’une comparaison partielle entre une zone du texte et le début du mot cherché, début que nous appelons motif, quelle est la position suivante, dans le mot, à partir de laquelle il est utile de reprendre la comparaison.

Si la comparaison a été positive entre les k caractères de la zone Texte[i..i+k-1] et les k caractères du mot, soit Mot[0..k-1], c’est que ces caratères sont identiques, dirait Monsieur de la Palice. Nous allons « pré-chercher » dans le mot les sous-chaînes, que nous appellerons motifs, telles que Mot[0..j] = Mot[k-j..k]. Munis de la liste de ces motifs, nous saurons combien de caractères sauter lorsqu’une comparaison échouera au caractère de rang k du mot.

Pour chaque position dans le mot nous déterminerons la longueur du plus long motif qui se termine à la position courante.

Tpref vérifiera la propriété suivante : si Texte[i..i+k-1] = Mot[0..k-1] mais que Texte[i+k] != Mot[k], alors la première position à laquelle une occurrence du mot peut apparaître est Texte[i+k-Tpref[k-1]].

En particulier, Tpref[-1] existe et vaut −1, parce que la comparaison peut échouer au premier caractère du texte, et donc du mot.

Tpref[j] aura pour valeur la longueur du motif initial le plus long qui se termine en Mot[j]. Notamment,
Tpref[-1] = -1, comme signalé ci-dessus.

Voici l’exposé de l’algorithme. Afin d’éviter un cas particulier, nous adopterons la convention suivante : Mot[-1] existe et sa valeur est différente de toute autre valeur possible pour les caractères de Mot. Nous choisirons ici le caractère nul ASCII, qui s’écrit en Scheme

. Pour des raisons de syntaxe de Scheme, les indices de notre tableau seront augmentés de 1 : Tpref[i] dans le pseudo-code est équivalent à Tpref[i+1] dans les développements ci-dessus.

Algorithme : kmp :tableau Donnée : Mot Soient Lmot <- longueur de Mot Tpref un tableau de longueur Lmot+1 i <- 0 j <- -1 Tpref[0] <- -1 c <- #a000  ; ; le caractère nul tant que i < Lmot faire si c = Mot[i] alors Tpref[i+1] <- j+1 j <- j+1 i <- i+1 sinon si j > 0 alors j <- Tpref[j] sinon Tpref[i+1] <- 0 i <- i+1 j <- 0 finsi finsi c <- Mot[j] fait retourner Tpref fin

En Scheme (algorithme adapté de l’article de Wikipedia, en
français
) :

  1. (module kmp-tableau
  2.    (export (kmp:tableau Motif)))
  3.  
  4. (define (kmp:tableau Motif)
  5.    (let* ((L-motif (string-length Motif))
  6.           (Tpref (make-vector (+ L-motif 1) 0))
  7.           (i 0)
  8.           (j -1))
  9.       (vector-set! Tpref 0 j)
  10.       (let boucle ((c #a000))    ;; le caractère nul
  11.          (print Tpref)
  12.          (cond ((= i L-motif) 'fini)
  13.                ((char=? c (string-ref Motif i))
  14.                 (vector-set! Tpref (+ i 1) (+ j 1))
  15.                 (set! j (+ j 1))
  16.                 (set! i (+ i 1)))
  17.                ((> j 0)
  18.                 (set! j (vector-ref Tpref j)))
  19.                (else
  20.                 (vector-set! Tpref (+ i 1) 0)
  21.                 (set! i (+ i 1))
  22.                 (set! j 0)))
  23.          (if (< i L-motif)
  24.              (boucle (string-ref Motif j))
  25.              Tpref))))

Télécharger

Trace d’exécution

Voici un exemple de déroulement de l’algorithme de construction
du tableau des préfixes :

Init. : Motif <- "ATATAGA" Tpref <- 00000000 i <- 0 j <- -1 c <- #a000 Tpref[0] <- -1 ---- c = #a000  != Motif[0] = A, donc : j = -1, donc : Tpref[1] <- 0 i <- 1 j <- 0 c <- A ---- c = A  != Motif[1] = T, donc : j = 0, donc : Tpref[2] <- 0 i <- 2 j <- 0 c <- A ---- c = A = Motif[2], donc : Tpref[3] <- 1  ; (j + 1) j <- 1 i <- 3 c <- T ---- c = T = Motif[3], donc : Tpref[4] <- 2  ; (j + 1) j <- 2 i <- 4 c <- A ---- c = A = Motif[4], donc : Tpref[5] <- 3  ; (j + 1) j <- 3 i <- 5 c <- T ---- c = T  != Motif[5] = G , donc : j <- Tpref[j = 3] = 1 c <- T ---- c = T  != Motif[5] = G, donc : j <- Tpref[j = 1] = O c <- A ---- c = A  != Motif[5] = G, donc : j = 0, donc : Tpref[i+1 = 6] <- 0 i <- 6 j <- 0 c <- A ---- c = A = Motif[6] Tpref[7] <- 1 j <- 1 i <- 7 c <- T ---- i = longueur(Motif) => fait Tpref = #(-1 0 0 1 2 3 0 1)

En moyenne cet algorithme s’exécute en un temps moyen qui croît
comme O(n).


KMP en style récursif

Aux fins d’une meilleure conformité aux canons de l’élégance lispienne, voici les mêmes programmes réécrits dans un style récursif dépourvu d’affectations :

  1. (module kmp
  2.    (main main)
  3.    (import kmp-table))
  4.  
  5. (define (main args)
  6.    (print (kmp:KMP (cadr args) (caddr args))))
  7.  
  8. (define (kmp:KMP Word Text)
  9.    (let ((Tpref (kmp:table Word))
  10.          (Ltext (string-length Text))
  11.          (LastCharPos (- (string-length Word) 1)))
  12.       (let loop ((i 0)
  13.                  (j 0))
  14.          (cond ((>= (+ i j) Ltext)
  15.                 -1)
  16.                ((char=? (string-ref Text (+ i j))
  17.                         (string-ref Word j))
  18.                 (if (= j LastCharPos)
  19.                     i
  20.                     (loop i (+ j 1))))
  21.                (else
  22.                 (loop
  23.                  (- (+ i j) (vector-ref Tpref j))
  24.                  (if (> j 0)
  25.                      (vector-ref Tpref j)
  26.                      j))) ) ) ))

Télécharger

  1. (module kmp-table
  2.    (export (kmp:table Word)))
  3.  
  4. (define (kmp:table Word)
  5.    (let* ((WordLength (string-length Word))
  6.           (Tpref (make-vector (+ WordLength 1) 0)) )
  7.       (vector-set! Tpref 0 -1)
  8.       (let loop ((i 0)
  9.                  (j -1)
  10.                  (c #a000))    ;; null character
  11.          (if (>= i WordLength)
  12.              Tpref
  13.              (cond ((char=? c (string-ref Word i))
  14.                     (vector-set! Tpref (+ i 1) (+ j 1))
  15.                     (loop (+ i 1)
  16.                           (+ j 1)
  17.                           (string-ref Word (+ j 1))))
  18.                    ((> j 0)
  19.                     (let ((j2 (vector-ref Tpref j)))
  20.                        (loop i
  21.                              j2
  22.                              (string-ref Word j2))))
  23.                    (else
  24.                     (vector-set! Tpref (+ i 1) 0)
  25.                     (loop (+ i 1)
  26.                           0
  27.                           (string-ref Word 0)))) ) )))

Télécharger





This document was translated from LATEX by HEVEA.