SchemeのKnuth-Morris-Prattアルゴリズム

Aug 18 2020

これは、Knuth-Morris-Prattアルゴリズムを使用する場合に、Schemeで失敗関数(戻る必要のあるステップ数)を計算するためのコードです。

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

しかし、私はその部分を理解していませんk > 0。誰かがそれを説明できますか?

回答

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

名前let付きの構文と混同しているようです。この投稿はそれがどのように機能するかを説明するのに良い仕事をしますが、おそらくより馴染みのある構文の例は物事をより明確にするでしょう。このコードをPythonで取得すると、1から10までのすべての整数が追加されます。

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

print(sum)
=> 55

それでは、再帰的に記述してみましょうloop。関数を呼び出します。これは完全に同等です:

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

loop(1, 0)
=> 55

上記の例では、loop関数は反復を実装し、パラメーターnは現在の位置を追跡するために使用され、パラメーターはsum回答を累積します。それでは、まったく同じコードをSchemeで記述しましょう。

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

これで、というローカルプロシージャが定義されました。loopこのプロシージャは、初期値10そのパラメータnおよびで自動的に呼び出されますsum。再帰の基本ケースに達すると、を返しsumます。それ以外の場合は、このプロシージャを呼び出し続け、パラメータの更新された値を渡します。Pythonコードとまったく同じです!構文に惑わされないでください。

アルゴリズムでは、i-pkは反復変数であり20それぞれとに初期化されます。条件が真であるかに応じて、我々が呼ぶとき、反復は継続loopのために更新された値で再びi-p及びk、またはケースがときに終了し(>= i-p n-p)、この時点で、ループが終了に達していると計算された値が変数ですsigma-table。この手順は、「失敗関数」と呼ばれる新しい関数を返すことで終了します。