อัลกอริทึม Knuth-Morris-Pratt ใน Scheme

Aug 18 2020

นี่คือรหัสสำหรับคำนวณฟังก์ชันความล้มเหลว (จำนวนขั้นตอนที่เราต้องย้อนกลับ) ใน Scheme เมื่อเราใช้อัลกอริทึม 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)))

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

ตอนนี้ขอพยายามที่จะเขียนมันในแฟชั่น recursive 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ขั้นตอนจะสิ้นสุดลงโดยส่งคืนฟังก์ชันใหม่เรียกว่า "ฟังก์ชันความล้มเหลว"