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

เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
Awksauce (คุย | ส่วนร่วม)
เก็บกวาด
ย้อนการแก้ไขของ Awksauce (พูดคุย) ไปยังรุ่นก่อนหน้าโดย Nullzerobot
บรรทัด 4:
 
== คำนำ ==
[[ขั้นตอนวิธีของเฮิร์ชเบิร์ก]]เป็นขั้นตอนวิธีสำหรับการเปรียบเทียบของสายอักขระ มีชื่อมาจากผู้คิดค้น [[แดน เฮิร์ชเบิร์ก]] (Dan Hirschberg) ซึ่งขั้นตอนวิธีนี้เป็น[[ขั้นตอนวิธีการเขียนโปรแกรมแบบพลวัต]] (Dynamic programming algorithm) ที่ถูกออกแบบมาเพื่อแก้ปัญหา[[ลำดับย่อยร่วมยาวสุด]] (Longest common subsequence) โดยขั้นตอนวิธีนี้จะแก้ปัญหาการเปรียบเทียบสายอักขระโดยใช้[[ปริภูมิเชิงเส้น]] (Linear space) เพื่อหา[[ระยะทางที่ถูกแก้ไขของราเวนสตีน]] (Levenshtein edit distance) ของสายอักขระ 2 สายที่เปรียบเทียบกันรวมทั้งหาการเรียงตัวของสายอักขระทั้งสองด้วย
 
== คำอธิบาย ==
สำหรับ[[สายอักขระ]] 2 สายคือ ''s1'', ''s2'' ซึ่งเป็นสายอักขระย่อยของสายอักขระที่ประกอบด้วยตัวอักษรเท่านั้น โดยสายอักขระย่อยไม่จำเป็นต้องติดกัน เช่น ee ese และ es เป็นสายอักขระย่อยของ “predecessor” และ “descendant” (ee สามารถเป็นสายอักขระย่อยได้ “predecessor”)
 
การเชื่อมต่อระหว่าง[[ลำดับย่อยร่วมยาวสุด]] (Longest common subsequence (lcs) ) และ[[ระยะทางที่ถูกแก้ไข]] (edit distance) สามารถแสดงในรูปสมการได้ดังนี้ d (''s1'', ''s2'') =|''s1''|+|''s2''|-2lcs (''s1'', ''s2'') ซึ่ง d (''s1'', ''s2'') คือ[[ระยะทางที่ถูกแก้ไขของราเวนสตีน]] (Levenshtein edit distance) ที่จะหาต้นทุนที่น้อยที่สุดในการแปลงสายอักขระหนึ่งไปเป็นอีกสายอักขระหนึ่ง โดยมีทั้งการแทรก การแทนที่ การลบ หรือ การกระทำที่ไม่มีผล เป็นต้น
 
ขั้นตอนวิธีของเฮิร์ชเบิร์กสามารถอธิบายการทำงานได้หลายวิธี เช่น ใช้[[ขั้นตอนวิธีแวงเกอร์ – ฟิชเชอร์]] (Wanger – Fisher algorithm) <ref>http://www.csci.agh.edu.pl/42/</ref> ในการมาใช้สร้างขั้นตอนวิธีของเฮิร์ชเบิร์กแต่ในที่นี้เราจะอธิบาย[[ขั้นตอนวิธีของเฮิร์ชเบิร์ก]] โดยใช้[[การแบ่งแยกและเอาชนะ]] (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 และ โปรตีน
 
== ข้อมูลขั้นตอนวิธี ==
ขั้นตอนวิธีของเฮิร์ชเบิร์กเป็นขั้นตอนวิธีที่ใช้ในการหาการจัดเรียงของลำดับสายอักขระที่ดีที่สุด สมมติว่าให้ ''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>
 
== การคำนวณระยะทางที่ถูกแก้ไขของราเวนสตีนด้วยปริภูมิเชิงเส้น ==
[[ระยะทางที่ถูกแก้ไข]] (Edit distance Edit (''x'', ''y'') ) คือ ต้นทุนที่น้อยที่สุดของการเปลี่ยนแปลงรูปจากสายอักขระหนึ่งเปลี่ยนเป็นอีกสายอักขระหนึ่ง ซึ่งโดยทั่วไปการเปลี่ยนแปลงสายอักขระจะมีดังนี้ การแทรก การแทนที่ การลบ และ การสลับตำแหน่ง เป็นต้น
 
โดยนิยามสัญลักษณ์ต่าง ๆ ต่างๆดังนี้ 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''
 
== การจัดการขั้นตอนวิธี ==
เพื่อที่จะเข้าใจขั้นตอนวิธีของเฮิร์ชเบิร์กมันสำคัญมากที่จะต้องเข้าใจระยะทางที่ถูกแก้ไขสามารถคำนวณโดยใช้วิธีการ[[ปริภูมิเชิงเส้น]] (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) แต่น่าเสียดายที่บางครั้งค่าที่ถูกลบไปอาจจะต้องนำมาใช้ในการคำนวณทีหลัง ขั้นตอนวิธีของเฮิร์ชเบิร์กจะใช้เวลาในการทำงานเป็น 2 เท่าของ[[ขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์]] (Needleman-Wunsch algorithm) แต่ก็ยังถือว่าอยู่ในเวลา [[สัญกรณ์โอใหญ่| O]] (''nm'')
 
== รหัสเทียม ==
คำอธิบายระดับสูงของโปรแกรมย่ิอยไปข้างหน้า
<source lang="text" line>
Forwards[x, y] is
 
1. n = length (x); m = length (y)
2. Edit[Prefix[0, 0]] = 0;
3. For all i from 1 to n:
Edit[Prefix[x, i], Prefix[y, 0]] = Edit[Prefix[x, i-1], Prefix[y, 0]] + Del (x_i)
4. For all j from 1 to m:
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:
i. Edit[Prefix[x, i], Prefix[y, j]] =
min{Edit[Prefix[x, i-1], Prefix[y, j]] + Del (x_i),
Edit[Prefix[x, i-1], Prefix[y, j-1]] + Sub (x_i, y_j),
Edit[Prefix[x, i], Prefix[y, j-1]] + Ins (y_j)}
ii. Erase Edit[Prefix[x, i-1], Prefix[y, j-1]]
C. Erase Edit[Prefix[x, i-1], Prefix[y, j]]
5. RETURN Edit[x] %% an array of length m+1
</source>
บรรทัด 54:
 
<source lang="text" line>
Backwards[x, y] is
 
1. n = length (x); m = length (y)
2. For all i from 1 to n:
Edit[Suffix[x, i], Suffix[y, 0]] = 0
3. For all j from 1 to m:
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:
i. Edit[Suffix[x, i], Suffix[y, j]] =
min{Edit[Suffix[x, i-1], Suffix[y, j]] + Del (x_{n-i-1}),
Edit[Suffix[x, i-1], Suffix[y, j-1]] + Sub (x_{n-i-1}, y_{m-j+1}),
Edit[Suffix[x, i], Suffix[y, j-1]] + Ins (y_{m-j+1})}
ii. Erase Edit[Suffix[x, i-1], Suffix[y, j-1]]
C. Erase Edit[Suffix[x, i-1], Suffix[y, j]]
4. RETURN Edit[x] %% an array of length m+1
</source>
บรรทัด 74:
 
<source lang="text" line>
Hirschberg (x, y) is
 
1. n = length (x); m = length (y)
2. If n <= 1 or m <= 1:
OUTPUT Alignment (x, y) using Needleman-Wunsch.
Else:
A. mid = floor (n/2)
B. x_left = Prefix[x, mid]
C. x_right = Suffix[x, n-mid]
D. Edit[x_left] = Forwards (x_left, y) %% an array of length m+1
E. Edit[x_right] = Backwards (x_right, y) %% an array of length m+1
F. cut = ArgMin{Edit[x_left, Prefix[y, j]] + Edit[x_right, Suffix[y, m-j]]} %% j ranges from 1 to m-1
G. Hirschberg Hirschberg(x_left, Prefix[y, cut])
H. Hirschberg Hirschberg(x_right, Suffix[y, m-cut])
</source>
 
บรรทัด 101:
== ความเห็นส่วนตัวของคนเขียน ==
 
ผู้ศึกษาขั้นตอนวิธีการของเฮิร์ชเบิร์ก เป็นขั้นตอนวิธีที่มีประโยชน์มากในการที่จะนำไปประยุกต์ใช้งาน เนื่องจากในโลกปัจจุบันเรามีข้อมูลจำนวนมากที่เป็นสายอักขระ ดังนั้นการที่เรามีขั้นตอนวิธีการที่ใช้เปรียบเทียบสายอักขระได้อย่างมีประสิทธิภาพ จะทำให้เราสามารถแก้ไขปัญหาหลาย ๆ หลายๆปัญหาที่เกี่ยวข้องกับสายอักขระได้อย่างมีประสิทธิภาพด้วยเช่นกัน
 
== แหล่งเอกสารอ้างอิง ==
บรรทัด 108:
== การเชื่อมโยงภายนอก ==
{{รายการอ้างอิง}}
 
 
[[หมวดหมู่:ขั้นตอนวิธีการจัดลำดับ]]