วิกิพีเดีย

ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของเฮิร์ชเบิร์ก"

เรียกดูประวัติแบบโต้ตอบ
← การแก้ไขก่อนหน้าการแก้ไขถัดไป →
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
เห็นภาพข้อความวิกิ
AAAERTCM (คุย | ส่วนร่วม)
ผู้ดูแลระบบ
การแก้ไข 15,783 ครั้ง
ล HIRSCHBERG’S ALGORITHM ถูกเปลี่ยนชื่อเป็น ขั้นตอนวิธีของเฮิร์ชเบิร์ก: ชื่อไทย
Octahedron80 (คุย | ส่วนร่วม)
ผู้ตรวจตรา
การแก้ไข 131,459 ครั้ง
ไม่มีความย่อการแก้ไข
บรรทัด 3:
 
 
'''ขั้นตอนวิธีของเฮิร์ชเบิร์ก''' ({{lang-en|Hirschberg’s algorithm}})เป็นขั้นตอนวิธีสำหรับการเปรียบเทียบของสายอักขระ มีชื่อมาจากผู้คิดค้นอัลกอริทึมนี้ชื่อ [[แดน เฮิร์ชเบิร์ก]] (Dan Hirschberg) ซึ่งอัลกอริทึมขั้นตอนวิธีนี้เป็น[[ขั้นตอนวิธีการเขียนโปรแกรมแบบพลวัต]] (Dynamic programming algorithm) ที่ถูกออกแบบมาเพื่อแก้ปัญหา[[ลำดับย่อยร่วมยาวสุด]] (Longest summon subsequence) โดยอัลกอริทึมขั้นตอนวิธีนี้จะแก้ปัญหาการเปรียบเทียบสายอักขระโดยใช้[[ปริภูมิเชิงเส้น]] (Linear space) เพื่อหา[[ระยะทางที่ถูกแก้ไขของราเวนสตีน]] (Levenshtein edit distance) ของสายอักขระ 2 สายที่เปรียบเทียบกันรวมทั้งหาการเรียงตัวของสายอักขระทั้งสองด้วย▼
'''ขั้นตอนวิธีของเฮิร์ชเบิร์ก ({{lang-en|Hirschberg’s algorithm}})''' เป็นขั้นตอนวิธีสำหรับการเปรียบเทียบของสายอักขระ
 
▲ขั้นตอนวิธีของเฮิร์ชเบิร์ก (Hirschberg’s algorithm) มีชื่อมาจากผู้คิดค้นอัลกอริทึมนี้ชื่อ [[แดน เฮิร์ชเบิร์ก]] (Dan Hirschberg) ซึ่งอัลกอริทึมนี้เป็น[[ขั้นตอนวิธีการเขียนโปรแกรมแบบพลวัต]] (Dynamic programming algorithm) ที่ถูกออกแบบมาเพื่อแก้ปัญหา[[ลำดับย่อยร่วมยาวสุด]] (Longest summon subsequence) โดยอัลกอริทึมนี้จะแก้ปัญหาการเปรียบเทียบสายอักขระโดยใช้[[ปริภูมิเชิงเส้น]] (Linear space) เพื่อหา[[ระยะทางที่ถูกแก้ไขของราเวนสตีน]] (Levenshtein edit distance) ของสายอักขระ 2 สายที่เปรียบเทียบกันรวมทั้งหาการเรียงตัวของสายอักขระทั้งสองด้วย
 
==คำแนะนำ==
เส้น 15 ⟶ 13:
 
==ข้อมูลขั้นตอนวิธี==
[[ขั้นตอนวิธีของเฮิร์ชเบิร์ก]] (Hirschberg's algorithm) เป็นอัลกอริทึมขั้นตอนวิธีที่ใช้ในการหาการจัดเรียงของลำดับสายอักขระที่ดีที่สุด สมมติว่าให้ ''x'' และ ''y'' เป็นสายอักขระซึ่ง ''n'' เป็นความยาวของสายอักขระ ''x'' และ ''m'' เป็นความยาวของสายอักขระ ''y'' เราสามารถใช้[[ขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์]] (Needleman – Wunsch algorithm) หาการจัดเรียงที่ดีที่สุดได้โดยใช้เวลา [[สัญกรณ์โอใหญ่| O]](''nm'') และใช้เนื้อที่ [[สัญกรณ์โอใหญ่| O]](''nm'') แต่หากเราใช้ขั้นตอนวิธีของเฮิร์ชเบิร์กซึ่งดีกว่า[[ขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์]]เราจะหาการจัดเรียงที่ดีที่สุดภายในเวลา [[สัญกรณ์โอใหญ่| O]](''nm'') และใช้เนื้อที่เพียง [[สัญกรณ์โอใหญ่| O]](min{''n'',''m''})<ref>http://www.cs.tau.ac.il/~rshamir/algmb/98/scribe/html/lec02/node10.html</ref>
 
ประโยชน์สำคัญอันหนึ่งของอัลกอริทึมขั้นตอนวิธีนี้ คือ การหาการลำดับเรียงตัวของสาย DNA และสายโปรตีน ซึ่งมันเป็นวิธีที่มีประสิทธิภาพในการคำนวณ[[ลำดับย่อยร่วมยาวสุด]] (Longest summon subsequence) ระหว่างกลุ่มข้อมูล 2 กลุ่มที่แตกต่างกัน
 
==การคำนวนระยะทางที่ถูกแก้ไขของราเวนสตีนด้วยปริภูมิเชิงเส้น==
เส้น 24 ⟶ 22:
โดยนิยามสัญลักษณ์ต่างๆดังนี้ Ins(''a'') คือ ต้นทุนในการแทรกสัญลักษณ์ ''a'' ลงสายอักขระ Sub(''a'',''b'') ต้นทุนครั้งของการแทนที่สัญลักษณ์ ''a'' ด้วยสัญลักษณ์ ''b'' ในสายอักขระ และ Del(''a'') ต้นทุนของการลบสัญลักษณ์ ''a'' ในสายอักขระซึ่งโดยทั่วไปแล้วต้นทุนของการเปลี่ยนแปลงต่างๆจะเป็นดังนี้ Ins(''a'') และ Del(''a'') ต้นทุนเท่ากับ 1 สำหรับทุกๆสัญลักษณ์ ''a'' ใดๆ รวมทั้ง Sub(''a'',''a'') เท่ากับ 0 และ Sub(''a'',''b'') เท่ากับ 1 ในกรณีที่สัญลักษณ์ ''a'' ไม่เท่ากับ ''b''
 
[[ขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์]] (Needleman – Wunsch algorithm) จะคำนวณ Edit(Prefix[''x'',''i''],Prefix[''y'',''j'']) สำหรับทุกๆ ''i'' และ ''j'' ที่ซึ่ง Prefix[''x'',''i''] หมายถึง คำนำหน้า(prefix) ของสายอักขระ ''x'' ที่ความยาว ''i'' อัลกอริทึมขั้นตอนวิธีนี้ต้องใช้เวลา [[สัญกรณ์โอใหญ่| O]](''nm'') และใช้เนื้อที่ [[สัญกรณ์โอใหญ่| O]](''nm'') โดย ''n'' เท่ากับความยาวของสายอักขระ ''x'' และ ''m'' เท่ากับความยาวของสายอักขระ ''y''
 
==การจัดการขั้นตอนวิธี==
เส้น 93 ⟶ 91:
</source>
 
== ดูเพิ่ม ==
==เพิ่มเติม==
*[[:en:Needleman-Wunsch algorithm]]
*[[:en:Smith Waterman algorithm]]
เข้าถึงจาก "https://th.wikipedia.org/wiki/ขั้นตอนวิธีของเฮิร์ชเบิร์ก"