ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของเฮิร์ชเบิร์ก"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มีความย่อการแก้ไข ป้ายระบุ: ผู้ใช้ใหม่เพิ่มลิงก์ไปยังเว็บอื่น |
|||
บรรทัด 1:
{{issues|ปรับภาษา=yes|จัดรูปแบบ=yes|ต้องการอ้างอิง=yes}}
'''ขั้นตอนวิธีของเฮิร์ชเบิร์ก''' ({{lang-en|Hirschberg’s algorithm}})
'''ขั้นตอนวิธีของเฮิร์ชเบิร์ก''' ({{lang-en|Hirschberg’s algorithm}})เป็นขั้นตอนวิธีสำหรับการเปรียบเทียบของสายอักขระ มีชื่อมาจากผู้คิดค้น [[แดน เฮิร์ชเบิร์ก]] (Dan Hirschberg) ซึ่งขั้นตอนวิธีนี้เป็น[[ขั้นตอนวิธีการเขียนโปรแกรมแบบพลวัต]] (Dynamic programming algorithm) ที่ถูกออกแบบมาเพื่อแก้ปัญหา[[ลำดับย่อยร่วมยาวสุด]] (Longest common subsequence) โดยขั้นตอนวิธีนี้จะแก้ปัญหาการเปรียบเทียบสายอักขระโดยใช้[[ปริภูมิเชิงเส้น]] (Linear space) เพื่อหา[[ระยะทางที่ถูกแก้ไขของราเวนสตีน]] (Levenshtein edit distance) ของสายอักขระ 2 สายที่เปรียบเทียบกันรวมทั้งหาการเรียงตัวของสายอักขระทั้งสองด้วย▼
== คำนำ ==
▲
==คำอธิบาย==
สำหรับ[[สายอักขระ]] 2 สายคือ ''s1'', ''s2'' ซึ่งเป็นสายอักขระย่อยของสายอักขระที่ประกอบด้วยตัวอักษรเท่านั้น โดยสายอักขระย่อยไม่จำเป็นต้องติดกัน เช่น ee ese และ es เป็นสายอักขระย่อยของ “predecessor” และ “descendant” (ee สามารถเป็นสายอักขระย่อยได้ “predecessor”)
เส้น 12 ⟶ 15:
==ข้อมูลขั้นตอนวิธี==
ขั้นตอนวิธีของเฮิร์ชเบิร์กเป็นขั้นตอนวิธีที่ใช้ในการหาการจัดเรียงของลำดับสายอักขระที่ดีที่สุด สมมติว่าให้ ''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 กลุ่มที่แตกต่างกัน▼
==การคำนวนระยะทางที่ถูกแก้ไขของราเวนสตีนด้วยปริภูมิเชิงเส้น==
เส้น 89 ⟶ 90:
</source>
==ตัวอย่างประยุกต์ใช้งาน==
▲ประโยชน์สำคัญอันหนึ่งของขั้นตอนวิธีนี้ คือ การหาการลำดับเรียงตัวของสาย DNA และสายโปรตีน ซึ่งมันเป็นวิธีที่มีประสิทธิภาพในการคำนวณ[[ลำดับย่อยร่วมยาวสุด]] (Longest summon subsequence) ระหว่างกลุ่มข้อมูล 2 กลุ่มที่แตกต่างกัน
==ดูเพิ่มเติม==
*[[:en:Needleman-Wunsch algorithm]]
*[[:en:Smith Waterman algorithm]]
เส้น 95 ⟶ 99:
*[[:en:Longest_common_subsequence_problem|Longest Common Subsequence]]
==ความเห็นส่วนตัวของคนเขียน==
== อ้างอิง ==▼
ผู้ศึกษาขั้นตอนวิธีการของเฮิร์ชเบิร์ก เป็นขั้นตอนวิธีที่มีประโยชน์มากในการที่จะนำไปประยุกต์ใช้งาน เนื่องจากในโลกปัจจุบันเรามีข้อมูลจำนวนมากที่เป็นสายอักขระ ดังนั้นการที่เรามีขั้นตอนวิธีการที่ใช้เปรียบเทียบสายอักขระได้อย่างมีประสิทธิภาพ จะทำให้เราสามารถแก้ไขปัญหาหลายๆปัญหาที่เกี่ยวข้องกับสายอักขระได้อย่างมีประสิทธิภาพด้วยเช่นกัน
[http://www.cs.toronto.edu/~brudno/csc2427/Lec7Notes.pdf เอกสารการเรียนเรื่องการจัดเรียง]
==การเชื่อมโยงภายนอก==
{{รายการอ้างอิง}}
| |||