Kmp

หน้านี้สำหรับอธิบายการทำงานของอัลกอริทึม Knuth–Morris–Pratt string matching

อัลกอริทึมรับ string P (pattern) และสตริง S จากนั้นหา P ใน S

อัลกอริทึมจะทยอย match P ใน S ไปเรื่อย ๆ เช่นถ้าเราต้องการหา ABABACA ใน ABABABACA อัลกอริทึมจะเริ่ม match ตั้งแต่ตำแหน่งแรก ดังด้านล่าง

S:ABABABACA
P:A

S:ABABABACA
P:AB

S:ABABABACA
P:ABA

S:ABABABACA
P:ABAB

S:ABABABACA
P:ABABA

จนกระทั่ง match ไม่ได้

S:ABABA*B*ACA
P:ABABA*C*

สิ่งที่อัลกอริทึมทราบคือ ณ ตำแหน่งปัจจุบัน match มาได้ถึง ABABA แล้ว คำถามคือจะเอาข้อมูลนี้ไปใช้อย่างไรได้บ้าง?

สังเกตว่าถ้าเอา P มาเทียบกับตัวเอง โดยพิจารณาเฉพาะ prefix ABABA ที่ถูก match ไปแล้ว เราจะพบว่า:

P:ABABA|
  ..ABA|
  ....A|

ดังนั้นการที่จะขยับจุดเริ่มต้นของจุดที่จะตรวจสอบ pattern P ใน S ให้น้อยที่สุด คือ ขยับไปสองตำแหน่ง นั่งคือ ดูจากความยาวของ ABABA ลบด้วยความยาวของ ABA แล้วสองสตริงนี้คืออะไร?

สังเกตว่า ถ้าเรา match มาได้ถึง ABABA แล้ว เราจะกระโดดไปน้อยสุด เราต้องหา suffix ที่ยาวที่สุดของ ABABA ที่เป็น prefix ของ ABAB ด้วยนั่งเอง ซึ่งในกรณีนี้คือ ABA ค่าของความยาวนี้จะเรียกว่า prefix function ถ้าเรามีค่านี้แล้วการจะ implement algorithm KMP ก็จะสามารถเขียนได้โดยง่าย

prefix function

ส่วนที่ยุ่งยากที่สุดคือการคำนวน prefix function ($\pi$, เพื่อความง่ายต่อไปจะเรียกว่า T), ซึ่งมีนิยามดังนี้

• T(j) เป็นความยาวของ prefix ของ P[1...(j-1)] ที่เป็น suffix ของ P[1...j] ฟังก์ชันนี้จะใช้ในการกระโดดเมื่อเกิดการจับคู่ไม่ได้

ด้านล่างแสดงตัวอย่างของค่า T(j) ต่าง ๆ ของสตริง ABABACA

  P : ABABACA
T(2): AB
      --         T(2) = 0

T(3): ABA
      --A        T(3) = 1

T(4): ABAB 
      --AB       T(4) = 2

T(5): ABABA 
      --ABA      T(5) = 3

T(6): ABABAC
      ------     T(6) = 0

ในการคำนวณนั้นเราจะเก็บไล่พิจารณา prefix ต่าง ๆ ของ P ไปตามลำดับ

ตอนที่พิจารณา P[1..j] เราจะคำนวณ T[j] ไปด้วย โดยเรา assume ว่าเราคำนวณ T[2], T[3], . . . , T[j-1] มาแล้ว

เมื่อเราพิจารณา P[1..j] เราทราบว่าที่ P[1...(j-1)] มี suffix ที่ยาวสุดที่เป็น prefix ของ P[1...(j-2)] ยาวเท่ากับ T[j-1] พิจารณาดังรูปด้านล่าง

พิจารณา P[1..j] โดยให้ P[j] แทนด้วย ? ไปก่อน

 P[1...j]     :  dabcdxdabcd?

เราทราบว่า P[1..(j-1)] มี suffix ที่ยาวที่สุดที่เป็น prefix ของ P[1..(j-2)] ยาวเท่ากับ T[j-1] เพื่อความสะดวกเราจะให้ k = T[j-1]

 P[1...(j-1)] :  dabcdxdabcd
                 ------dabcd  (ยาว T[j-1])

พิจารณา P[j] มีได้สองกรณีคือ

Case 1: กรณีที่ prefix กับ suffix ที่ match กันอยู่ ยังต่อกันได้ กล่าวคือ P[j] == P[k+1], แสดงดังด้านล่าง

 P[1...j]     :  dabcdxdabcdx
                 ------dabcdx (ยาว T[j-1]+1)

ในกรณีนี้เราจะได้ว่า T[j] = k + 1 (และในรอบถัดไป k = k + 1)

Case 2: ถ้าไม่เช่นนั้น เราก็ต้องหา prefix อื่นที่สั้นลงที่จะ match กับ P[1..j] ได้ ดังแสดงดังรูปด้านล่าง:

 P[1...j]     :  dabcdxdabcda
                 ------dabcdx ไม่ตรง
match up to      ------dabcd    (P[1..k])
next prefix      ----------d     (P[1..T[k]])

นั่นคือ ในกรณีนี้ เราจะพิจารณา prefix ที่ยาวที่สุดที่ match ได้ถึงตำแหน่งเดิมที่ match ได้ (นั่นคือ match ได้ถึง P[1..k]) ดังนั้นเราจะให้ k = T[k], แล้วกลับไปพิจารณาใหม่

จากสองกรณีข้างต้น เราเขียนโค้ดได้ดังนี้

1. m = len(P)
2. T[1] = 0
3. k = 0
4. for q = 2 to m do

5.    while ( k > 0 ) and ( P[k+1] != P[q] ) do // Case 2
6.       k = T[k]
7.    endwhile

8.    if ( P[k+1] == P[q] ) then // Case 1
9.        k = k + 1
10.   endif

11.   T[q] = k

12. endfor

เวลาการทำงาน: ใช้เวลา O(m) เนื่องจาก for loop ทำงาน m รอบ, while loop ทำงานรวมไม่เกิน O(m) เพราะว่าทุกรอบค่า k ลดลง แต่ k เพิ่มขึ้นครั้งละ 1 (บรรทัด 9) ต่อหนึ่งรอบ for loop, ดังนั้น k จะลดค่าไม่เกิน m ครั้ง

จาก prefix function

เมื่อเรามี prefix function T แล้ว KMP ก็ใช้หลักการเดิม (สังเกตว่าอัลกอริทึมแทบเหมือนกันเลย) ดังนี้:

ALGORITHM KMP(P, S)   // try to match P in S
1. m = len(P), n = len(S)
2. T = compute_prefix_function()
3. k = 0 // match length
4. q = 1 // index
5. while q <= n do

6.    while ( k > 0 ) and ( P[k+1] != S[q] ) do 
7.       k = T[k]
8.    endwhile

9.    if ( P[k+1] == S[q] ) then // Case 1
10.       k = k + 1
11.   endif

12.   if ( k == m ) then
13.      output "Match at ", q - m
14.      k = T[k]
15.   endif

16.   q = q + 1

17. endwhile

เอกสารเพิ่มเติม

• wikipedia
• lecture note จาก Hong Kong University of Science and Technology