ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของเฮิร์ชเบิร์ก"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
เก็บกวาด |
|||
บรรทัด 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)
ขั้นตอนวิธีของเฮิร์ชเบิร์กสามารถอธิบายการทำงานได้หลายวิธี เช่น ใช้[[ขั้นตอนวิธีแวงเกอร์ – ฟิชเชอร์]] (Wanger – Fisher algorithm)
== ข้อมูลขั้นตอนวิธี ==
ขั้นตอนวิธีของเฮิร์ชเบิร์กเป็นขั้นตอนวิธีที่ใช้ในการหาการจัดเรียงของลำดับสายอักขระที่ดีที่สุด สมมติว่าให้ ''x'' และ ''y'' เป็นสายอักขระซึ่ง ''n'' เป็นความยาวของสายอักขระ ''x'' และ ''m'' เป็นความยาวของสายอักขระ ''y'' เราสามารถใช้[[ขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์]] (Needleman – Wunsch algorithm) หาการจัดเรียงที่ดีที่สุดได้โดยใช้เวลา [[สัญกรณ์โอใหญ่| O]]
== การคำนวณระยะทางที่ถูกแก้ไขของราเวนสตีนด้วยปริภูมิเชิงเส้น ==
[[ระยะทางที่ถูกแก้ไข]] (Edit distance Edit
โดยนิยามสัญลักษณ์
[[ขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์]] (Needleman – Wunsch algorithm) จะคำนวณ Edit
== การจัดการขั้นตอนวิธี ==
เพื่อที่จะเข้าใจขั้นตอนวิธีของเฮิร์ชเบิร์กมันสำคัญมากที่จะต้องเข้าใจระยะทางที่ถูกแก้ไขสามารถคำนวณโดยใช้วิธีการ[[ปริภูมิเชิงเส้น]] (Linear space)
เราจะนิยาม[[โปรแกรมย่อยไปข้างหน้า]]
[[โปรแกรมย่อยไปข้างหน้า]] (Forward subprogram) และ[[โปรแกรมย่อยถอยหลัง]] (Backward subprogram) จะคำนวณค่าใน[[เมทริกซ์]]
== รหัสเทียม ==
คำอธิบายระดับสูงของโปรแกรมย่ิอยไปข้างหน้า
<source lang="text" line>
Forwards[x,
1. n = length
2. Edit[Prefix[0,
3. For all i from 1 to n:
Edit[Prefix[x,
4. For all j from 1 to m:
A. Edit[Prefix[x,
B. For all i from 1 to n, execute the following steps:
i. Edit[Prefix[x,
min{Edit[Prefix[x,
Edit[Prefix[x,
Edit[Prefix[x,
ii. Erase Edit[Prefix[x,
C. Erase Edit[Prefix[x,
5. RETURN Edit[x] %% an array of length m+1
</source>
บรรทัด 54:
<source lang="text" line>
Backwards[x,
1. n = length
2. For all i from 1 to n:
Edit[Suffix[x,
3. For all j from 1 to m:
A. Edit[Suffix[x,
B. For all i from 1 to n:
i. Edit[Suffix[x,
min{Edit[Suffix[x,
Edit[Suffix[x,
Edit[Suffix[x,
ii. Erase Edit[Suffix[x,
C. Erase Edit[Suffix[x,
4. RETURN Edit[x] %% an array of length m+1
</source>
บรรทัด 74:
<source lang="text" line>
Hirschberg
1. n = length
2. If n <= 1 or m <= 1:
OUTPUT Alignment
Else:
A. mid = floor
B. x_left = Prefix[x,
C. x_right = Suffix[x,
D. Edit[x_left] = Forwards
E. Edit[x_right] = Backwards
F. cut = ArgMin{Edit[x_left,
G.
H.
</source>
บรรทัด 101:
== ความเห็นส่วนตัวของคนเขียน ==
ผู้ศึกษาขั้นตอนวิธีการของเฮิร์ชเบิร์ก เป็นขั้นตอนวิธีที่มีประโยชน์มากในการที่จะนำไปประยุกต์ใช้งาน เนื่องจากในโลกปัจจุบันเรามีข้อมูลจำนวนมากที่เป็นสายอักขระ ดังนั้นการที่เรามีขั้นตอนวิธีการที่ใช้เปรียบเทียบสายอักขระได้อย่างมีประสิทธิภาพ จะทำให้เราสามารถแก้ไขปัญหา
== แหล่งเอกสารอ้างอิง ==
บรรทัด 108:
== การเชื่อมโยงภายนอก ==
{{รายการอ้างอิง}}
[[หมวดหมู่:ขั้นตอนวิธีการจัดลำดับ]]
|