Recherche de mots dans un texte, KMP

William Saurin, Laurent Bloch

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

<!—TOC section Algorithme force brute.—>

<!—SEC ANCHOR —>1 Algorithme force brute.

<!—SEC END —>

On peut imaginer positionner successivement la sous chaine 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.

Complexité de l'algorithme : l × m

Nom de l'algo: brute-force Données : Texte, Mot ; le texte, et le mot recherché Résultat : la première position où 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

En Scheme, le programme :

(define (force-brute1 Texte Motif) (let ((Ltexte (string-length Texte)) (Lmotif (string-length Motif)) (p -1)) (do ((i 0 (+ i 1))) ((or (> i (- Ltexte Lmotif)) (> p -1)) p) (do ((j 0 (+ j 1))) ((or (>= j Lmotif) (not (char=? (string-ref Texte (+ i j)) (string-ref Motif j)))) (if (= j Lmotif) (set! p i)))))))

L'entête du module Bigloo pour la compilation :

(module force-brute (main get-args)) (define (get-args args) (print (force-brute (cadr args) (caddr args))))

Là c'est peut-être plus facile à lire :

(define (force-brute2 Texte Motif) (let* ((Ltexte (string-length Texte)) (Lmotif (string-length Motif)) (DerPosTexte (- Ltexte Lmotif))) (let loop1 ((i 0)(j 0)) (let loop2 () (if (and (< j Lmotif) (char=? (string-ref Texte (+ i j)) (string-ref Motif j))) (begin (set! j (+ j 1)) (loop2)))) (cond ((= j Lmotif) i) (( <= i DerPosTexte)(loop1 (+ i 1) 0)) (else -1)))))

Et une quatrième variante :

(define (force-brute3 Texte Motif) (let* ((Ltexte (string-length Texte)) (Lmotif (string-length Motif)) (DerPosTexte (- Ltexte Lmotif))) (let loop1 ((i 0)) (let loop2 ((j 0)) (if (and (< j Lmotif) (char=? (string-ref Texte (+ i j)) (string-ref Motif j))) (loop2 (+ j 1)) (cond ((= j Lmotif) i) ((<= i DerPosTexte)(loop1 (+ i 1))) (else -1)))))))

Et pour finir, sans doute la plus élégante :

(define (force-brute4 Texte Motif) (let ((Ltexte (string-length Texte)) (Lmotif (string-length Motif))) (do ((i 0 (+ i 1)) (p -1 (do ((j 0 (+ j 1))) ((or (>= j Lmotif) (not (char=? (string-ref Texte (+ i j)) (string-ref Motif j)))) (if (= j Lmotif) i -1))))) ((or (> i (- Ltexte Lmotif)) (> p -1)) p))))

<!—TOC section Algorithme de Knuth-Morris-Pratt (KMP)—>

<!—SEC ANCHOR —>2 Algorithme de Knuth-Morris-Pratt (KMP)

<!—SEC END —>

On rappelle que l'indice j correspond à une progression dans le motif et l'indice i à une progression dans le texte. À un moment donné on compare le caratère d'indice i+j du texte avec le caractère d'indice j du motif. 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 caractères du texte que nous avons examinés sont « bons » alors ce sont les premiers caractères du motif : nous pouvons savoir ce qui nous arrivera d'avance uniquement en examinant d'abord les caractères du motif.

Si les k+1 caractères de rangs i à i+k étaient « bons », c'est-à-dire égaux aux k+1 premiers caractères du motif, 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 motif, 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 motif, alors il faut reprendre la comparaison à la position Texte[i+k+1] du texte et à partir de la position Motif[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 motif, soit Texte[i..i+k] = Motif[0..k], et si en outre Texte[i+k-m..i+k] = Motif[k-m..k], alors c'est que Motif[0..m]= Motif[k-m..k]. Or ce résultat concerne uniquement Motif, est peut être pré-calculé.

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

Imaginons donc que pour tous les motifs allant de 0 à k dans la chaine nous connaissions la positions la plus grande j telle que le motif allant de 0 à j soit identique à celle allant de k-j à k. Considérons que prec soit une fonction telle que prec(k) soit la valeur de j en question. Imaginons que nous ayons examinés 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 si 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.

La fonction qui construit la table des préfixes est écrite selon la méthode suivante. La chaîne Motif = atataga est comparée à un texte Texte tel que les q = 5 premiers caractères concordent. En ne nous servant que de notre connaissance des 5 caractères concordants, on peut déduire qu'un décalage de s0+1 est invalide, mais qu'un décalage de s1=s0+2 est cohérent avec ce que nous savons jusque là du texte, et donc potentiellement valide.

Les informations utiles pour ces déductions peuvent être pré-calculées en comparant le motif avec lui-même. ici, on voit que le plus long préfixe de Motif qui est aussi un suffixe de Motif-5 est Motif-3. Cette information est pré-calculée et représentée dans le tableau Table-prefixes, de sorte que Table-prefixes[5]=3. Sachant que q caractères ont été appariés avec succès au décalage s0, le prochain décalage potentiellement valide est :

s1=s0 + (q -Table-prefixes[q])

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) :

(module kmp-tableau (export (kmp:tableau Motif))) (define (kmp:tableau Motif) (let* ((L-motif (string-length Motif)) (Tpref (make-vector (+ L-motif 1) 0)) (i 0) (j -1)) (vector-set! Tpref 0 j) (let boucle ((c #a000)) ;; le caractère nul (print Tpref) (cond ((= i L-motif) 'fini) ((char=? c (string-ref Motif i)) (vector-set! Tpref (+ i 1) (+ j 1)) (set! j (+ j 1)) (set! i (+ i 1))) ((> j 0) (set! j (vector-ref Tpref j))) (else (vector-set! Tpref (+ i 1) 0) (set! i (+ i 1)) (set! j 0))) (if (< i L-motif) (boucle (string-ref Motif j)) Tpref))))

L'algorithme de KMP s'écrit alors :

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 Scheme :

(module kmp (main appel) (import kmp-tableau)) (define (appel args) (print (kmp:KMP (cadr args) (caddr args)))) (define (kmp:KMP Motif Texte) (let ((Tpref (kmp:tableau Motif)) (L-texte (string-length Texte)) (L-motif (string-length Motif)) (m 0) (i 0)) (let boucle () (if (char=? (string-ref Texte (+ m i)) (string-ref Motif i)) (set! i (+ i 1)) (begin (set! m (- (+ m i) (vector-ref Tpref i))) (if (> i 0) (set! i (vector-ref Tpref i))))) (if (and (< (+ m i) L-texte) (< i L-motif)) (boucle))) (if (= i L-motif) m (+ m i))))

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

J'ai ultérieurement écrit une version de ces programmes en style récursif.

La suite de nos aventures avec MM. Knuth, Morris et Pratt est à l'article consacré à l'observation de programmes par instrumentation. Signalons aussi l'excellent article de Wikipedia, en français.

<!—TOC section Karp-Rabin—>

<!—SEC ANCHOR —>3 Karp-Rabin

<!—SEC END —>

Imaginons que nous recherchions le chaine “31416” dans le texte :

“671980190981781314168781981”

Nous pourrions en fait considérer que nous recherchions le nombre 31416 dans la suite de nombre 67198, 71980, 19801,98019... et nous finirions par trouver 31416... comment passe-t-on d'un nombre au suivant ?

10*(v_i−1−p_i−m10^m−1)+p_i . Le problème est que 10^m−1 peut être trop grand à calculer dans ce cas on peut faire des calculs modulo k la formule deviendra :

(10*(v_i−1−p_i−mh)+p_i) mod k. Où h = 10^m−1 mod k.

On peut imaginer appliquer cette idée à n'importe quel alphabet A de taille connu t_a en associant à chaque caractère de l'alphabet une valeur p_i entre 0 et t_a et en remplaçant appliquant la formule :

(t_a*(v_i−1−p_i−mh)+p_i) modk.

Où h = t_a^m−1 modk.

Références

[1]: Thérèse Accart-Hardin Véronique Donzeau-Gouge Viguié. Concepts et outils de programmation. Interéditions, Paris, 1992.
Manuel et méthode d'un enseignement du CNAM, cet ouvrage introduit les concepts fondamentaux de la programmation avec un souci pédagogique qui ne nuit pas à la rigueur.
[2]: A.V. Aho, R. Sethi, J.D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, Massachusetts, 1986. Traduction française : Interéditions, Paris, 1989.
Une référence classique ; les techniques de compilation ont évolué depuis son écriture ; cet ouvrage reste néanmoins une introduction presque obligée.
[3]: Amos Bairoch. << The Swiss-Prot Protein Sequence Data Bank User Manual >>, 1996.
[4]: Laurent Bloch. Initiation à la programmation avec Scheme. Technip, Paris, 2001.
Un livre de programmation consacré à Scheme, un dialecte moderne et élégant de LISP.
[5]: Corrado Böhm Giuseppe Jacopini. << Flow Diagrams, Turing Machines And Languages With Only Two Formation Rules >>. Communications of the ACM (CACM), vol. 9 n° 5, May 1966.
[6]: Jacques Chazarain. Programmer avec Scheme, de la pratique à la théorie. International Thomson Publishing, Paris, 1996.
Ce livre qui nous a servi de modèle en bien des points envisage un champ plus vaste que le nôtre ; il introduit à la logique, au λ-calcul, à la compilation, entre autres.
[7]: Olivier Cogis Claudine Robert. Au-delà des ponts de Königsberg – Théorie des Graphes. Vuibert, Paris, 2003.
[8]: Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction à l'algorithmique. Dunod (pour la traduction française), Paris, 2002.
Une somme d'une complétude impressionnante ; si les exposés mathématiques des algorithmes sont d'une grande clarté, le passage à la programmation (en pseudo-code) est souvent difficile.
[9]: Maxime Crochemore Wojciech Rytter. Text Algorithms. Oxford University Press, Oxford, 1994.
Un exposé de référence pour les algorithmes utilisés aussi bien en biologie informatique que pour la linguistique.
[10]: Albert Ducrocq André Warusfel. Les mathématiques – Plaisir et nécessité. Vuibert, Paris, 2000.
Plaidoyer pour une discipline malmenée, au moyen de nombreux exemples historiques et modernes auxquels l'érudition et le talent de vulgarisateurs des auteurs confèrent un rythme trépidant et passionnant.
[11]: Gottlob Frege. Écrits logiques et philosophiques. Le Seuil, Paris, 1971 [1879–1925].
Qui programme n'échappe pas longtemps à l'interrogation logique. Les réflexions sur la distinction entre le sens et la dénotation des formes du discours d'un fondateur de la logique moderne rejoignent curieusement mais nécessairement des questions d'évaluation posées par la programmation applicative.
[12]: Jeffrey E. F. Friedl. Maîtrise des expressions régulières. O'Reilly, Paris, 1997-2006. http://www.oreilly.fr/catalogue/2841772365.html.
[13]: Herman H. Goldstine. The Computer – from Pascal to von Neumann. Princeton University Press, Princeton, NJ, 1972.
[14]: Oliver Grillmeyer. Exploring computer science with Scheme. Springer-Verlag, New York, 1998.
[15]: Dan Gusfield. Algorithms on Strings, Trees, and Sequences – Computer Science and Computational Biology. Cambridge University Press, Cambridge, 1997.
Ce livre offre une présentation très large de ce que l'on appelle l'algorithmique sur les mots ou les chaînes de caractères telles les séquences biologiques. Y sont ainsi présentés les algorithmes « classiques » sur les chaînes, ainsi que les développements nouveaux inspirés par des problèmes divers en biologie moléculaire (comparaison de séquences, extraction de motifs, recherche de répétitions et de palindromes, phylogénie, cartographie, assemblage entre autres). En ce qui concerne l'algorithmique classique, une grande importance est accordée à l'utilisation d'une structure particulière qui est celle des arbres de suffixes.
[16]: Kurt Gödel Jean-Yves Girard. Le théorème de Gödel. Éditions Le Seuil, Paris, 1989.
[17]: Max Hailperin, Barbara Kaiser, Karl Knight. Concrete Abstractions: An Introduction to Computer Science Using Scheme. Brooks & Cole Publishing, Pacific Grove, Calif., USA, 1999.
Ce livre présente plusieurs chapitres classiques d'un cursus informatique qui n'avaient pas fait l'objet d'une introduction aussi systématique en Scheme, comme la programmation dynamique. La présentation des algorithmes sur les arbres est plus approfondie que de coutume. La clarté des exposés est remarquable et rend faciles des problèmes réputés difficiles. Il est désormais accessible en ligne ici : http://www.gustavus.edu/+max/concrete-abstractions.html.
[18]: C. Antony R. Hoare. << Monitors: An Operating System Structuring Concept >>. Communications of the ACM (CACM), vol. 17 n° 10, octobre 1974. http://www.acm.org/classics/feb96/.
[19]: Andrew Hodges. Alan Turing: the enigma (Alan Turing : l'énigme de l'intelligence). Simon and Schuster (Payot, Paris pour la traduction), New-York, USA, 1983.
[20]: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automata Theory, Languages, and Computation. Addison Wesley, 1979 – 2007.
[21]: Donald E. Knuth. Selected Papers on Computer Science. Cambridge University Press, Cambridge, 1996.
Un recueil d'articles sur des sujets tels que la relation entre les mathématiques et l'informatique ou l'algorithmique babylonienne. Alors que le mathématicien affronte l'infini, on sait que l'informaticien doit se contenter d'objets finis. L'auteur montre que pour être finis certains objets ou certains problèmes n'en sont pas moins très grands.
[22]: Donald E. Knuth, Ronald L. Graham, Oren Patashnik. Concrete Mathematics. Addison-Wesley, Reading, Massachusetts, 1989. Traduction française de Alain Denise : International Thomson Publishing.
Le titre de ce livre est un jeu de mots multiple, « concrete » en anglais veut dire concret mais aussi béton, et peut résulter du télescopage de « continuous » avec « discrete ». Cet ouvrage riche d'abstractions utiles introduit des êtres mathématiques qui œuvrent en secret dans l'ombre d'objets informatiques tels que tables associatives ou procédures récursives. Analyse combinatoire, probabilités discrètes, analyse asymptotique sont introduites sans facilité mais avec passion.
[23]: Donald E. Knuth. The Art of Computer Programming. Addison-Wesley, Reading, Massachusetts, 1997 [1968]. 3 vol.
Encyclopédie inachevée des sciences formelles de l'informatique, une mine encore à exploiter.
[24]: Henri Lilen. La saga du micro-ordinateur. Vuibert, Paris, 2003.
Le titre de ce livre est vraiment mérité : passionnant et passionné, illustré de documents parfois inédits, il rend notamment justice aux précurseurs français de cette industrie et éclaire le processus de décision au sein de grandes entreprises industrielles.
[25]: Jean-Louis Nebut. UNIX pour l'utilisateur. Éditions Technip, Paris, 1990.
Face à l'océan des livres-mode d'emploi inodores et sans saveur, celui-ci introduit des concepts (ceux de la programmation) dans un univers d'où ils sont souvent bannis. Unix y apparaît sous un jour nouveau, doté d'une cohérence non limitée à sa structure interne, et du coup compréhensible même à qui n'en a pas lu le noyau. L'exercice (organiser cet apparent fouillis) était difficile.
[26]: John von Neumann. << First Draft of a Report on the EDVAC >>, 30 juin 1945. Ce texte fondamental, longtemps d'un accès difficile, est maintenant en ligne ici : http://www.virtualtravelog.net/entries/2003-08-TheFirstDraft.pdf.
[27]: John von Neumann. The Computer and the Brain. Yale University Press, New Haven, Connecnicut, 1957. Traduction française : La Découverte, Paris 1992.
Ce texte d'une conférence que la mort de l'auteur a empêché d'être prononcée réfute le réductionnisme qui fleurit souvent sous de tels titres, énumère les différences fondamentales entre l'activité du cerveau et le fonctionnement des machines numériques, ouvre de nouvelles problématiques sur des questions rebattues telle que l'existence des objets de la mathématique et de la logique.
[28]: Christian Queinnec. ABC d'Unix. Eyrolles, Paris, 1985.
Ce livre épuisé mais disponible sur le réseau sous licence FDL (Free Documentation License) à l'URL http://www-spi.lip6.fr/\~queinnec/Books/ABCdUNIX/uunix-toc.html accomplit un exercice délicat : dégager les concepts de la philosophie d'Unix, sans se noyer dans les détails ni omettre rien d'important.
[29]: Christian Queinnec. Principes d'implantation de Scheme et Lisp. Paracamplus, Paris, 2007.
Un examen complet et approfondi de toutes les questions soulevées par les langages Lisp, leur traduction et leur implantation, avec le code en Scheme et de l'humour. Les possibilités de Scheme pour créer des langages sont démontrées avec virtuosité. Une lecture vraiment indispensable à qui veut savoir « comment ça marche ».
[30]: Christian Queinnec, Anne Brygoo, Titou Durand, Maryse Pelletier, Michèle Soria. Programmation récursive (en Scheme). Dunod, Paris, 2004.
[31]: Alfred Rényi. Calcul des probabilités. Jacques Gabay [pour la traduction], Budapest [Paris], 1966.
Ce livre qui a fait date dans son domaine contient un exposé particulièrement incisif et élégant de l'algèbre de Boole.
[32]: Manuel Serrano. << Vers une programmation fonctionnelle praticable >>. Habilitation à diriger des recherches, Université de Nice, 2000.
Une réflexion pratique non dépourvue d'aperçus théoriques sur la construction de logiciels. Disponible ici : http://www-sop.inria.fr/mimosa/personnel/Manuel.Serrano/index-3.html\#Programming-Environment.
[33]: Ravi Sethi. Programming Languages. AddisonWesley, Reading, Massachusetts, 1996.
Parce que les langages sont plusieurs et qu'il importe de les considérer.
[34]: Claude E. Shannon. << A mathematical theory of communication >>. Bell System Technical Journal, 27, p. 379-423 et 623-656, juillet et octobre 1948. Disponible en ligne ici : http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf.
[35]: Alan Turing Jean-Yves Girard. La machine de Turing. Éditions Le Seuil, Paris, 1995.
Une introduction abordable mais sans concessions, puis le texte historique.
[36]: Jacques Vélu. Méthodes mathématiques pour l'informatique. Dunod, Paris, 1987.
Une introduction vraiment accessible. Pour mettre le pied à l'étrier.

Index

algorithme de Knuth-Morris-Pratt, 2
Böhm, Corrado, 3
Cormen, Thomas, 3
Ducrocq, Albert, 3
Girard, Jean-Yves, 3
Goldstine, Herman H., 3
Gödel, Kurt, 3
Hoare, C. Antony R., 3
Hodges, Andrew, 3
Jacopini, Giuseppe, 3

Knuth, Donald E., 3
Leiserson, Charles, 3
Lilen, Henri, 3
Nebut, Jean-Louis, 3
Neumann, John von, 3
Rivest, Ronald, 3
Rényi, Alfred, 3
Serrano, Manuel, 3
Stein, Clifford, 3
Turing, Alan, 3
Warusfel, André, 3

Ce document a été traduit de L^AT_EX par H^EV^EA