ผลต่างระหว่างรุ่นของ "Kmp"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 38: | แถว 38: | ||
สิ่งที่อัลกอริทึมทราบคือ ณ ตำแหน่งปัจจุบัน match มาได้ถึง ABABA แล้ว คำถามคือจะเอาข้อมูลนี้ไปใช้อย่างไรได้บ้าง? | สิ่งที่อัลกอริทึมทราบคือ ณ ตำแหน่งปัจจุบัน match มาได้ถึง ABABA แล้ว คำถามคือจะเอาข้อมูลนี้ไปใช้อย่างไรได้บ้าง? | ||
| − | สังเกตว่าถ้าเอา P มาเทียบกับตัวเอง เราจะพบว่า: | + | สังเกตว่าถ้าเอา P มาเทียบกับตัวเอง โดยพิจารณาเฉพาะ prefix ABABA ที่ถูก match ไปแล้ว เราจะพบว่า: |
<pre style="font-family: courier"> | <pre style="font-family: courier"> | ||
| − | ABABA | + | P:ABABA| |
| − | ..ABA| | + | ..ABA| |
| − | ....A| | + | ....A| |
</pre> | </pre> | ||
| − | + | ดังนั้นการที่จะขยับจุดเริ่มต้นของจุดที่จะตรวจสอบ pattern '''P''' ใน '''S''' ให้น้อยที่สุด คือ ขยับไปสองตำแหน่ง นั่งคือ ดูจากความยาวของ ABABA ลบด้วยความยาวของ ABA แล้วสองสตริงนี้คืออะไร? | |
| + | |||
| + | สังเกตว่า ถ้าเรา match มาได้ถึง ABABA แล้ว เราจะกระโดดไปน้อยสุด เราต้องหา suffix ที่ยาวที่สุดของ ABABA ที่เป็น prefix ของ ABABA ด้วยนั่งเอง | ||
ส่วนที่ยุ่งยากที่สุดคือการคำนวน prefix function (<math>\pi</math>, เพื่อความง่ายต่อไปจะเรียกว่า '''pi'''), ซึ่งมีนิยามดังนี้ | ส่วนที่ยุ่งยากที่สุดคือการคำนวน prefix function (<math>\pi</math>, เพื่อความง่ายต่อไปจะเรียกว่า '''pi'''), ซึ่งมีนิยามดังนี้ | ||
รุ่นแก้ไขเมื่อ 09:36, 13 กรกฎาคม 2557
หน้านี้สำหรับอธิบายการทำงานของอัลกอริทึม 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 ของ ABABA ด้วยนั่งเอง
ส่วนที่ยุ่งยากที่สุดคือการคำนวน prefix function (, เพื่อความง่ายต่อไปจะเรียกว่า pi), ซึ่งมีนิยามดังนี้
- pi(j) เป็นความยาวของ prefix ของ P[1...(j-1)] ที่เป็น suffix ของ P[1...j] ฟังก์ชันนี้จะใช้ในการกระโดดเมื่อเกิดการจับคู่ไม่ได้
ด้านล่างแสดงตัวอย่างของค่า pi(j) ต่าง ๆ ของสตริง ABABACA
A B A B A C A A B A B A A B A B A B A B A A B A B A C A B A B A C A
