Algoritmo di Knuth-Morris-Pratt in Scheme

Aug 18 2020

Questo è il codice per calcolare la funzione di guasto (quanti passaggi dobbiamo tornare indietro) in Scheme, quando usiamo l'algoritmo di 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)))

Ma non capisco la parte in cui k > 0. Qualcuno può spiegarlo per favore?

Risposte

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

Vedo che sei confuso con la sintassi di un namedlet . Questo post spiega come funziona, ma forse un esempio con una sintassi più familiare renderà le cose più chiare. Prendi questo codice in Python, aggiunge tutti i numeri interi da 1 a 10:

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

print(sum)
=> 55

Ora proviamo a scriverlo in modo ricorsivo, chiamerò la mia funzione loop. Questo è completamente equivalente:

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

loop(1, 0)
=> 55

Nell'esempio precedente, la loopfunzione implementa un'iterazione, il parametro nviene utilizzato per tenere traccia della posizione corrente e il parametro sumaccumula la risposta. Ora scriviamo lo stesso identico codice, ma in Scheme:

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

Ora abbiamo definito una procedura locale chiamata loopche viene poi chiamata automaticamente con i valori iniziali 1e 0per i suoi parametri ne sum. Quando viene raggiunto il caso base della ricorsione, torniamo sum, altrimenti continuiamo a chiamare questa procedura, passando i valori aggiornati per i parametri. È esattamente lo stesso del codice Python! Non lasciarti confondere dalla sintassi.

Nel tuo algoritmo, i-pe ksono le variabili di iterazione, che sono inizializzate rispettivamente a 2e 0. A seconda di quale condizione è vera, l'iterazione continua quando chiamiamo di loopnuovo con valori aggiornati per i-pe k, oppure termina quando (>= i-p n-p)viene raggiunto il caso , a questo punto il ciclo termina e il valore calcolato è nella variabile sigma-table. La procedura termina restituendo una nuova funzione, denominata "funzione di errore".