[Dynamic Programming] Edit Distance

โจทย์จาก : Edit Distance เป็นปัญหาที่ถามเราว่าถ้ามี String 2 ตัว A,B จะมี operation ทำให้เหมือนกันโดยน้อยที่สุด โดยมี 3 operation

1. insert แทรกตัวอักษรเข้าไป 
2. delete ลบตัวอักษรออกจาก String
3.  replace เปลี่ยน A[i] เป็น B[j] 

 เช่น ถ้า A = ABC B = DEF
   operation ที่น้อยที่สุดคือ เปลี่ยน A -> D และเปลี่ยน B -> E และสุดท้าย C -> F ถ้า A = ABC B = ADE
   จะใช้เพียงแค่ 2 operation เพราะ A[0] กับ B[0] เท่ากันแล้ว  

วิธีตรงไปตรงมา(recursion)
เนื่องจากเราไม่รู้ว่าทำแบบไหนจะได้น้อยสุด เราจะทำทั้งหมดแล้วดูว่าวิธีไหนน้อยสุด
A = "X" B = "PQ" วิธีที่เราจะทำได้คือ

insert    : A -> "PX" B = "PQ" insert P เข้าไปใน A ทำให้ A กับ B มี P เหมือนกันแล้ว
delete   : A ->   _     B = "PQ" ลบ X ออก 
replace : A -> "P"    B = "PQ" เปลี่ยน X เป็น P

ตัวสีแดงคือตัวอักษรที่เราไม่สนใจแล้ว (ถูกดำเนินการแล้ว) ตัวอักษรที่ขีดเส้นใต้คือตัวอักษรที่เราต้องเปลี่ยน เช่น insert X กับ Q ถูกขีดเส้นตาย เพราะเราสามารถ
1.ลบ X ออก แล้วเพิ่ม Q 
2.ลบ Q ออกแล้วเพิ่ม X 
3.เปลี่ยน X ->Q หรือ Q -> X ก็จะทำให้เท่ากัน 
ส่วน P เราไม่ยุ่งเพราะเราทำให้เหมือนกันแล้ว


จากตัวอย่างข้างบนถ้าเราดำเนินการต่อแต่ละเคส ด้วย 3 เคสนี้ไปเรื่อยๆ เราก็จะรู้ว่าแต่ละแบบใช้กี่ครั้งจะเหมือนกัน

คำถามคือเราจะหยุดเมื่อไหร่ เพราะเราสามารถเพิ่มเข้าไปได้เรื่อยๆ หรือเปลี่ยนไปเรื่อยๆ ถ้าตัวขีดเส้นใต้ของเราคือตัวที่เราจะเปลี่ยนแล้วตัวขีดเส้นใต้ของเราไม่มีใน A หรือใน B แล้ว แปลว่าเราไม่ต้องทำต่อแล้ว แต่อาจจะเกิดกรณี A = "PQX" B = "PQ" ตัวขวาเราไม่มีตัวไหนที่ต้องดูแล้ว แต่ตัว X ยังมีในกรณีนี้ ถ้าตัวขวาเป็น 0 เราจะตอบว่าต้องลบตัวใน A เป็นจำนวนตัวที่ต้องเปลี่ยนขีดเส้นใต้ของ X และในทางกลับกันถ้าตัวซ้ายตัวที่เราต้องเปลี่ยนหมดแล้ว เราก็จะตอบจำนวนตัวที่ต้องเปลี่ยนใน X แทน

เพระฉะนั้น base case ของเราเป็น if(i == 0) return j;
                                               if(j == 0) return i;
ถ้ามอง recursion tree ด้านล่างเราจะจบทุกครั้งที่เป็น 0

recursion tree ที่เราจะเขียนจะทำทุกวิธีที่เป็นไปได้จนกว่าตัวที่เราสนใจจะเปลี่ยนเป็น 0
เราจะสร้าง f(i,j) ฟังค์ชั่นตัวนึงขึ้นมา f(i,j) จะให้ค่าน้อยที่สุดของ f(i,j)

f(i,j-1) คือ การ insert
f(i-1,j) คือ การ delete
f(i-1,j-1) คือการ replace
และเราก็ทำการเลือก min ของ 3 ฟังชั่นข้างบน ส่วน 1 คือไม่ว่าเราจะเลือกอะไรจาก 3 operation ก็ถือว่า 1 ครั้ง Tree ของเรายิ่งสูงขึ้นจำนวน + 1 ที่นี้จะบอกว่าเราสูงเท่าไหร่

ถ้าอธิบาย f(i,j) ให้เป็นภาษาทั่วไปคือ มี 3 วิธีไปเลือกวิธีที่น้อยที่สุดมาจาก 3 วิธีนี้ ส่วน + 1 ก็คือเราเลือกตัวน้อยสุด 1 ตัว และแต่ละครั้งก็จะถามแบบนี้จนกว่าจะไปเจอ i == 0 หรือ j == 0

จาก code จะเห็นเคส else if(a[i-1] == b[j-1]) คือกรณีที่เหมือนกัน ถ้าตัวอักษรเหมือนกัน ก็เหมือนเรา replace เช่น "AC" "PX" ถ้า replace ก็เป็น "PC" "PX" ถือว่านับ 1 แต่ถ้า
"AC" "AX" เราก็ไม่ต้องเช็คตัวแรกของแต่ละตัวแล้วเพราะว่ามันเหมือนกันแล้ว จะกลายเป็น
"AC" "PX" แต่เราจะไม่ + 1 เพราะว่าเราไม่จำเป็นต้องทำอะไร เพราะเท่ากันแล้ว

วิเคราะห์ Algorithm นี้  ถ้าเราลองนับดูว่า A = "ABC" B = "DEF" ซึ่งแค่ 3 ตัวอักษรแต่จะพบว่า recursion นี้ทำหลายรอบมากๆ
จะทำให้ดีขึ้นได้อย่างไร ถ้ามองรูป tree ด้านบน เราจะเห็นว่ามีบาง f(i,j) ที่เราได้หาเจอแล้ว ถูกเรียกใหม่อีกรอบ ในรูป f(1,1) ได้ถูกหาไปแล้วจากซ้ายสุด และถูกหาอีกครั้งตรงกลาง
เราจะใช้ dynamic programming เข้ามาช่วย
เขียน f(i,j) เต็มๆจะได้ 

ถ้าเราจะทำแบบ top down เราก็ต้องจำค่าแต่ละ f(i,j) และเมื่อ f(i,j) ถูกคำนวณไปแล้วเราจะตอบทันทีไม่ไปเสียเวลาเพิ่ม
ถ้าเราจะเขียนแบบ bottom up ก็ใช้ตรรกะเดียวกับข้างบนแต่เราจะทำตั้งแต่
 i = 0 -> len(A) j = 0 -> len(B)