SchemeのKnuth-Morris-Prattアルゴリズム
これは、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
。誰かがそれを説明できますか?
回答
名前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
このプロシージャは、初期値1
と0
そのパラメータn
およびで自動的に呼び出されますsum
。再帰の基本ケースに達すると、を返しsum
ます。それ以外の場合は、このプロシージャを呼び出し続け、パラメータの更新された値を渡します。Pythonコードとまったく同じです!構文に惑わされないでください。
アルゴリズムでは、i-p
とk
は反復変数であり2
、0
それぞれとに初期化されます。条件が真であるかに応じて、我々が呼ぶとき、反復は継続loop
のために更新された値で再びi-p
及びk
、またはケースがときに終了し(>= i-p n-p)
、この時点で、ループが終了に達していると計算された値が変数ですsigma-table
。この手順は、「失敗関数」と呼ばれる新しい関数を返すことで終了します。