วิกิพีเดีย

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

เรียกดูประวัติแบบโต้ตอบ
← การแก้ไขก่อนหน้าการแก้ไขถัดไป →
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
เห็นภาพข้อความวิกิ
Octahedron80 (คุย | ส่วนร่วม)
ผู้ตรวจตรา
การแก้ไข 131,464 ครั้ง
ไม่มีความย่อการแก้ไข
Octahedron80 (คุย | ส่วนร่วม)
ผู้ตรวจตรา
การแก้ไข 131,464 ครั้ง
ลิงก์ซ้ำซาก
บรรทัด 1:
{{ต้องการหมวดหมู่}}
{{issues|ปรับภาษา=yes|จัดรูปแบบ=yes|ต้องการอ้างอิง=yes}}
 
 
'''ขั้นตอนวิธีของเฮิร์ชเบิร์ก''' ({{lang-en|Hirschberg’s algorithm}})เป็นขั้นตอนวิธีสำหรับการเปรียบเทียบของสายอักขระ มีชื่อมาจากผู้คิดค้น [[แดน เฮิร์ชเบิร์ก]] (Dan Hirschberg) ซึ่งขั้นตอนวิธีนี้เป็น[[ขั้นตอนวิธีการเขียนโปรแกรมแบบพลวัต]] (Dynamic programming algorithm) ที่ถูกออกแบบมาเพื่อแก้ปัญหา[[ลำดับย่อยร่วมยาวสุด]] (Longest summon subsequence) โดยขั้นตอนวิธีนี้จะแก้ปัญหาการเปรียบเทียบสายอักขระโดยใช้[[ปริภูมิเชิงเส้น]] (Linear space) เพื่อหา[[ระยะทางที่ถูกแก้ไขของราเวนสตีน]] (Levenshtein edit distance) ของสายอักขระ 2 สายที่เปรียบเทียบกันรวมทั้งหาการเรียงตัวของสายอักขระทั้งสองด้วย
เส้น 10 ⟶ 9:
การเชื่อมต่อระหว่าง[[ลำดับย่อยร่วมยาวสุด]] (Longest common subsequence (lcs)) และ[[ระยะทางที่ถูกแก้ไข]] (edit distance) สามารถแสดงในรูปสมการได้ดังนี้ d(''s1'',''s2'')=|''s1''|+|''s2''|-2lcs(''s1'',''s2'') ซึ่ง d(''s1'',''s2'') คือ[[ระยะทางที่ถูกแก้ไขของราเวนสตีน]] (Levenshtein edit distance) ที่จะหาต้นทุนที่น้อยที่สุดในการแปลงสายอักขระหนึ่งไปเป็นอีกสายอักขระหนึ่ง โดยมีทั้งการแทรก การแทนที่ การลบ หรือ การกระทำที่ไม่มีผล เป็นต้น
 
[[ขั้นตอนวิธีของเฮิร์ชเบิร์ก]] (Hirschberg’s algorithm) สามารถอธิบายการทำงานได้หลายวิธี เช่น ใช้[[ขั้นตอนวิธีแวงเกอร์ – ฟิชเชอร์]] (Wanger – Fisher algorithm)<ref>http://www.csci.agh.edu.pl/42/</ref> ในการมาใช้สร้าง[[ขั้นตอนวิธีของเฮิร์ชเบิร์ก]] (Hirschberg’s algorithm) แต่ในที่นี้เราจะอธิบาย[[ขั้นตอนวิธีของเฮิร์ชเบิร์ก]] โดยใช้[[การแบ่งแยกและเอาชนะ]] (divide and conquer) ของ[[ขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์]] (Needleman – Wunsch algorithm)<ref>[http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Hirsch/ Hirschberg's algorithm<!-- Bot generated title -->]</ref> โดยปกติแล้ว[[ขั้นตอนวิธีของเฮิร์ชเบิร์ก]]นิยมใช้ในทางการคำนวณ[[ชีววิทยา]]เพื่อเปรียบเทียบของเหมือนของการเรียงตัวของ DNA และ โปรตีน
 
==ข้อมูลขั้นตอนวิธี==
[[ขั้นตอนวิธีของเฮิร์ชเบิร์ก]] (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 กลุ่มที่แตกต่างกัน
เส้น 25 ⟶ 24:
 
==การจัดการขั้นตอนวิธี==
เพื่อที่จะเข้าใจ[[ขั้นตอนวิธีของเฮิร์ชเบิร์ก]] (Hirschberg's algorithm) มันสำคัญมากที่จะต้องเข้าใจระยะทางที่ถูกแก้ไขสามารถคำนวณโดยใช้วิธีการ[[ปริภูมิเชิงเส้น]] (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> โดย Suffix[''y'',''j''] คือ คำเสริมท้าย(suffix) ของสายอักขระ ''y'' ของความยาว ''j''
 
[[โปรแกรมย่อยไปข้างหน้า]] (Forward subprogram) และ[[โปรแกรมย่อยถอยหลัง]] (Backward subprogram) จะคำนวณค่าใน[[เมทริกซ์]](matrix) โดยใช้ค่าที่ถูกคำนวณไว้ก่อนหน้านี้ แต่จะบันทึกช่องว่างโดยการลบค่าที่ไม่จำเป็นต้องใช้อีกต่อไประหว่างการทำงานของ[[โปรแกรมย่อย]] (subprogram) แต่น่าเสียดายที่บางครั้งค่าที่ถูกลบไปอาจจะต้องนำมาใช้ในการคำนวณทีหลัง [[ขั้นตอนวิธีของเฮิร์ชเบิร์ก]] (Hirschberg's algorithm) จะใช้เวลาในการทำงานเป็น 2 เท่าของ[[ขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์]] (Needleman-Wunsch algorithm) แต่ก็ยังถือว่าอยู่ในเวลา [[สัญกรณ์โอใหญ่| O]](''nm'')
 
==รหัสเทียม==
เข้าถึงจาก "https://th.wikipedia.org/wiki/ขั้นตอนวิธีของเฮิร์ชเบิร์ก"