Instrumentation de programme : KMP - [Site WWW de Laurent Bloch]

Introduction aux macros de Scheme

Instrumentation de programme : KMP

Article mis en ligne le 7 juin 2006

dernière modification le 3 janvier 2007

par Laurent Bloch

Sommaire

Analyse de programme par instrumentation

"http://www.w3.org/TR/REC-html40/loose.dtd">

Analyse de programme par instrumentation

Laurent Bloch

Le 7 juin 2006

Cet article est la suite de celui consacré, entre autres, à
l’algorithme de Knuth-Morris-Pratt. Signalons aussi
l’excellent article de Wikipedia, en
français.

1. KMP, le traitement 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 les « bons » en fait ce sont les caractères de la sous-chaîne que nous avons vus : nous pouvons savoir ce qui nous arrivera d'avance uniquement en examinant d'abord les caractères de la sous chaine.

Figure 1:

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-pretraite Donnée : Motif ; une chaîne Résultat : Table-prefixes ; un tableau des adresses des ; plus longs préfixes propres identiques ; à un suffixe de chacun des préfixes. Soit L-motif <- longueur de Motif pour k allant de 0 à L-motif - 1 faire i <- k-1 tant que i != -1 et Motif[Table-prefixes[i] + 1] != Motif[k] faire i <- Table-prefixes[i] fait si i = -1 alors Table-prefixes[k] <- -1 sinon Table-prefixes[k] <- i fait

2. Étendre la syntaxe pour observer un programme

Nous allons reprendre le programme de pré-traitement de l'algorithme, mais pour en observer le comportement nous allons l'instrumenter, c'est-à-dire y insérer des expressions dont l'évaluation va écrire sur la sortie standard (par exemple) les résultats d'observations.

Pour ce faire nous allons introduire un nouveau moyen d'étendre notre langage, les macro-instructions.

Macro-instructions

Pour mesurer le fonctionnement de notre programme nous pourrions en modifier le texte pour y introduire des manipulations de compteurs ou des commandes d'impression, mais cette technique est inélégante, source d'erreurs et de difficultés de gestion du code source. Il est plus approprié de faire modifier le texte du programme... par un programme, évidemment, en l'occurrence le compilateur, qui est justement un logiciel adapté à ce genre de travail.

Le moyen qui permet de réaliser des modifications du texte d'un programme est la macro. Le principe en est de générer un texte Scheme qui sera ensuite évalué.

La forme spéciale define-macro permet de décrire le texte à générer¹. La syntaxe en est analogue à celle de define :

(define-macro (<nom de la macro> p1 p2 ... pk)
         <corps de la macro>)

L'usage de notre nouvelle macro se fait ainsi :

(<nom de la macro> a1 a2 ... ak)

ce qui s'évalue en deux étapes selon la règle suivante :

Macro-expansion : les paramètres formels p1 p2 ... pk sont liés aux arguments a1 a2 ... ak sans évaluation de ceux-ci, puis le <corps de la macro> est évalué dans cet environnement. L'expression qui résulte de cette évaluation est appelée expansion de la macro.
L'expansion obtenue à l'étape précédente est évaluée dans l'environnement courant de l'appel.

L'étape 1 (expansion) construit un texte Scheme, qui est évalué à l'étape 2.

La difficulté est de rédiger le corps de la macro de sorte que son expansion donne le résultat voulu. Les formes spéciales quasiquote (qui s'abrège en

</CODE>, cf. <A HREF="#sec:arobas">??</A>),
<CODE>unquote</CODE> (qui s'abrège en <CODE>,</CODE>) et
<CODE>unquote-splicing</CODE> (qui s'abrège en <CODE>,@</CODE>)
sont généralement mises à contribution à cet effet.<BR>
<BR>
Ils faut considérer les actions effectuées par les macros comme
s'il s'agissait d'opérations réalisées avec un éditeur de texte :
elles doivent précéder physiquement la compilation du programme et
<EM>a fortiori</EM> son exécution. En particulier, le texte de
définition d'une macro doit précéder son invocation ; une macro
n'est pas exportable d'un module à l'autre.<BR>
<BR>
Il est possible avec des macros de modifier une procédure (même
du standard) pour lui incorporer un compteur, ainsi pour Fibonnaci
d'un cours précédent :<BR>
<BR>

<DIV CLASS="lstlisting"><TT>(<B>define</B> (compte-fonction compteur fonction)</TT><TT>
</TT><TT>   (<B>lambda</B> L-param</TT><TT>
</TT><TT>      (compteur 'inc)</TT><TT>
</TT><TT>      (<B>apply</B> fonction L-param)))</TT></DIV><BR>
<BR>
Nous proposons pour ce faire :<BR>
<BR>

<DIV CLASS="lstlisting"><TT>(<B>define-macro</B> (compte compteur fonction)</TT><TT>
</TT><TT>(set! ,fonction (compte-fonction ,compteur ,fonction)))





utilisé ainsi :




(compte compteur-fib fib)






3. Instrumentation de KMP




En Scheme :





(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
         (cond ((= i L-motif) Tpref)
               ((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))))




On rappelle le texte Scheme de KMP, qu'ici on a également instrumenté
pour compter le nombre d'itérations :





(module kmp-instru
   (main appel)
   (import kmp-tableau))

(define-macro (cree-compteur compteur)
   <code class='spip_code spip_code_inline' dir='ltr'>(define ,compteur (make-compteur 0)))

(define-macro (inc-compteur compteur)</code>(,compteur 'inc))

(define-macro (val-compteur compteur)
   `(print "Longueur du texte : " L-texte
           " Compteur de boucle KMP : "
           (,compteur 'val)))

(define (make-compteur val)
   (lambda message
      (case (car message)
         ((val) val)
         ((reset) (set! val 0))
         ((inc) (set! val (+ 1 val))))))

(define (appel args)
   (print (kmp:KMP (cadr args) (caddr args))))

(define (kmp:KMP Motif Texte)
   (cree-compteur compte-kmp)
   (let ((Tpref (kmp:tableau Motif))
         (L-texte (string-length Texte))
         (L-motif (string-length Motif))
         (m 0)
         (i 0))
      (print "Motif : " Motif " Texte : " Texte)
      (print "Tableau : " Tpref)
      (let boucle ()
         (inc-compteur compte-kmp)
         (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)))
      (val-compteur compte-kmp)
      (if (= i L-motif)
          m
          (+ m i))))



Voici le résultat de l'exécution de ce programme :




Motif : atatag Texte : atatattagggatttagtatatttatatatattataatatag
Tableau : #(-1 0 0 1 2 3 0)
Longueur du texte : 42 Compteur de boucle KMP : 56
36




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




1
La forme define-macro
n'est pas dans la norme et il existe d'autre syntaxes pour
créer des macros. Celle-ci nous a semblé la plus simple et
la plus élégante.





This document was translated from L^AT_EX by
H^EV^EA.

Dans la même rubrique

Votre inscription a été enregistrée avec succès !