Algorithme de Knuth-Morris-Pratt dans Scheme

Aug 18 2020

C'est le code pour calculer la fonction d'échec (combien d'étapes nous devons reculer) dans Scheme, lorsque nous utilisons l'algorithme de Knuth-Morris-Pratt:

(define (compute-failure-function p)
    (define n-p (string-length p))
    (define sigma-table (make-vector n-p 0))
    (let loop
        ((i-p 2)
         (k 0))
      (cond
          ((>= i-p n-p)
           (vector-set! sigma-table (- n-p 1) k))
          ((eq? (string-ref p k)
                (string-ref p (- i-p 1)))
           (vector-set! sigma-table i-p (+ k 1))
           (loop (+ i-p 1) (+ k 1)))
          ((> k 0)
           (loop i-p (vector-ref sigma-table k)))
          (else ; k=0
           (vector-set! sigma-table i-p 0)
           (loop (+ i-p 1) k))))
    (vector-set! sigma-table 0 -1)
    (lambda (q)
        (vector-ref sigma-table q)))

Mais je ne comprends pas la partie quand k > 0. Quelqu'un peut-il l'expliquer s'il vous plaît?

Réponses

2 ÓscarLópez Aug 18 2020 at 22:54

Je vois que vous êtes confus avec la syntaxe d'un namedlet . Cet article explique bien son fonctionnement, mais peut-être qu'un exemple avec une syntaxe plus familière rendra les choses plus claires. Prenez ce code en Python, il ajoute tous les entiers de 1 à 10:

sum = 0
n = 1
while n <= 10:
  sum += n
  n += 1

print(sum)
=> 55

Essayons maintenant de l'écrire de manière récursive, j'appellerai ma fonction loop. C'est tout à fait équivalent:

def loop(n, sum):
    if n > 10:
        return sum
    else:
        return loop(n + 1, n + sum)

loop(1, 0)
=> 55

Dans l'exemple ci-dessus, la loopfonction implémente une itération, le paramètre nest utilisé pour garder une trace de la position actuelle et le paramètre sumaccumule la réponse. Maintenant, écrivons exactement le même code, mais dans Scheme:

(let loop ((n 1) (sum 0))
  (cond ((> n 10) sum)
        (else (loop (+ n 1) (+ n sum)))))
=> 55

Nous avons maintenant défini une procédure locale appelée loopqui est ensuite automatiquement appelée avec les valeurs initiales 1et 0pour ses paramètres net sum. Lorsque le cas de base de la récursion est atteint, nous retournons sum, sinon nous continuons d'appeler cette procédure, en passant des valeurs mises à jour pour les paramètres. C'est exactement la même chose que dans le code Python! Ne soyez pas confus par la syntaxe.

Dans votre algorithme, i-pet ksont les variables d'itération, qui sont respectivement initialisées à 2et 0. Selon la condition vraie, l'itération continue lorsque nous appelons à loopnouveau avec des valeurs mises à jour pour i-pet k, ou elle se termine lorsque le cas (>= i-p n-p)est atteint, à ce stade, la boucle se termine et la valeur calculée est dans la variable sigma-table. La procédure se termine par le retour d'une nouvelle fonction, appelée «fonction d'échec».