ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของเฮิร์ชเบิร์ก"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
Nullzerobot (คุย | ส่วนร่วม) ล เก็บกวาด |
Nullzerobot (คุย | ส่วนร่วม) ล เก็บกวาด |
||
บรรทัด 26:
เพื่อที่จะเข้าใจขั้นตอนวิธีของเฮิร์ชเบิร์กมันสำคัญมากที่จะต้องเข้าใจระยะทางที่ถูกแก้ไขสามารถคำนวณโดยใช้วิธีการ[[ปริภูมิเชิงเส้น]] (Linear space)
เราจะนิยาม[[โปรแกรมย่อยไปข้างหน้า]](Forward subprogram) ซึ่งคำนวณค่าของ Edit(Prefix[''x'',''i''],Prefix[''y'',''j'']) สำหรับทุกๆ ''i'' และ ''j'' คล้าย[[ขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์]] และคืนค่า array{Edit(''x'',Prefix[''y'',''j''])}<sub>0 ≤ ''j'' ≤ ''m''</sub> อีกส่วนหนึ่งที่เราจะนิยามคือ[[โปรแกรมย่อยถอยหลัง]](Backward subprogram) ซึ่งคล้ายกับโปรแกรมย่อยไปข้างหน้าแต่จะทำ[[โปรแกรมแบบพลวัติ]] (dynamic program) จะสลับทิศทางกัน โดยจะเริ่มจากซ้ายไปขวาและล่างขึ้นบนแทน ซึ่งโปรแกรมนี้จะคืนค่า array {Edit(''x'',Suffix[''y'',''j''])}<sub>0 ≤ ''j'' ≤ ''m''</sub>
[[โปรแกรมย่อยไปข้างหน้า]] (Forward subprogram) และ[[โปรแกรมย่อยถอยหลัง]] (Backward subprogram) จะคำนวณค่าใน[[เมทริกซ์]](matrix) โดยใช้ค่าที่ถูกคำนวณไว้ก่อนหน้านี้ แต่จะบันทึกช่องว่างโดยการลบค่าที่ไม่จำเป็นต้องใช้อีกต่อไประหว่างการทำงานของ[[โปรแกรมย่อย]] (subprogram) แต่น่าเสียดายที่บางครั้งค่าที่ถูกลบไปอาจจะต้องนำมาใช้ในการคำนวณทีหลัง ขั้นตอนวิธีของเฮิร์ชเบิร์กจะใช้เวลาในการทำงานเป็น 2 เท่าของ[[ขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์]] (Needleman-Wunsch algorithm) แต่ก็ยังถือว่าอยู่ในเวลา [[สัญกรณ์โอใหญ่| O]](''nm'')
บรรทัด 35:
Forwards[x,y] is
1.
2.
3.
Edit[Prefix[x,i],Prefix[y,0]] = Edit[Prefix[x,i-1],Prefix[y,0]] + Del(x_i)
4.
A. Edit[Prefix[x,0],Prefix[y,j]] = Edit[Prefix[x,0],Prefix[y,j-1]] + Ins(y_j)
B. For all i from 1 to n, execute the following steps:
บรรทัด 48:
ii. Erase Edit[Prefix[x,i-1],Prefix[y,j-1]]
C. Erase Edit[Prefix[x,i-1],Prefix[y,j]]
5.
</source>
บรรทัด 56:
Backwards[x,y] is
1.
2.
Edit[Suffix[x,i],Suffix[y,0]] = 0
3.
A. Edit[Suffix[x,0],Suffix[y,j]] = Edit[Suffix[x,n],Suffix[y,j-1]] + Ins(y_{m-j+1})
B. For all i from 1 to n:
บรรทัด 68:
ii. Erase Edit[Suffix[x,i-1],Suffix[y,j-1]]
C. Erase Edit[Suffix[x,i-1],Suffix[y,j]]
4.
</source>
บรรทัด 76:
Hirschberg(x,y) is
1.
2.
OUTPUT Alignment(x,y) using Needleman-Wunsch.
Else:
บรรทัด 94:
== ดูเพิ่มเติม ==
* [[:en:Needleman-Wunsch algorithm]]
* [[:en:Smith Waterman algorithm]]
* [[:en:Levenshtein distance]]
* [[:en:
== ความเห็นส่วนตัวของคนเขียน ==
|