ขั้นตอนวิธีของเฮิร์ชเบิร์ก

**[[ขั้นตอนวิธีของเฮิร์ชเบิร์ก]]** เป็นขั้นตอนวิธีสำหรับการเปรียบเทียบของสายอักขระ มีชื่อมาจากผู้คิดค้น แดน เฮิร์ชเบิร์ก (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) ในการมาใช้สร้างขั้นตอนวิธีของเฮิร์ชเบิร์กแต่ในที่นี้เราจะอธิบายขั้นตอนวิธีของเฮิร์ชเบิร์ก โดยใช้การแบ่งแยกและเอาชนะ (divide and conquer) ของขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์ (Needleman – Wunsch algorithm) โดยปกติแล้วขั้นตอนวิธีของเฮิร์ชเบิร์กนิยมใช้ในทางการคำนวณชีววิทยาเพื่อเปรียบเทียบของเหมือนของการเรียงตัวของ DNA และ โปรตีน

## ข้อมูลขั้นตอนวิธี
ขั้นตอนวิธีของเฮิร์ชเบิร์กเป็นขั้นตอนวิธีที่ใช้ในการหาการจัดเรียงของลำดับสายอักขระที่ดีที่สุด สมมติว่าให้ *x* และ *y* เป็นสายอักขระซึ่ง *n* เป็นความยาวของสายอักขระ *x* และ *m* เป็นความยาวของสายอักขระ *y* เราสามารถใช้ขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์ (Needleman – Wunsch algorithm) หาการจัดเรียงที่ดีที่สุดได้โดยใช้เวลา O(*nm*) และใช้เนื้อที่ O(*nm*) แต่หากเราใช้ขั้นตอนวิธีของเฮิร์ชเบิร์กซึ่งดีกว่าขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์เราจะหาการจัดเรียงที่ดีที่สุดภายในเวลา O(*nm*) และใช้เนื้อที่เพียง O(min{*n*,*m*})

## การคำนวณระยะทางที่ถูกแก้ไขของราเวนสตีนด้วยปริภูมิเชิงเส้น
ระยะทางที่ถูกแก้ไข (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*])}0 ≤ *j* ≤ *m* อีกส่วนหนึ่งที่เราจะนิยามคือโปรแกรมย่อยถอยหลัง(Backward subprogram) ซึ่งคล้ายกับโปรแกรมย่อยไปข้างหน้าแต่จะทำโปรแกรมแบบพลวัติ (dynamic program) จะสลับทิศทางกัน โดยจะเริ่มจากซ้ายไปขวาและล่างขึ้นบนแทน ซึ่งโปรแกรมนี้จะคืนค่า array {Edit(*x*,Suffix[*y*,*j*])}0 ≤ *j* ≤ *m* โดย Suffix[*y*,*j*] คือ คำเสริมท้าย(suffix) ของสายอักขระ *y* ของความยาว *j*

โปรแกรมย่อยไปข้างหน้า (Forward subprogram) และโปรแกรมย่อยถอยหลัง (Backward subprogram) จะคำนวณค่าในเมทริกซ์ (matrix) โดยใช้ค่าที่ถูกคำนวณไว้ก่อนหน้านี้ แต่จะบันทึกช่องว่างโดยการลบค่าที่ไม่จำเป็นต้องใช้อีกต่อไประหว่างการทำงานของโปรแกรมย่อย (subprogram) แต่น่าเสียดายที่บางครั้งค่าที่ถูกลบไปอาจจะต้องนำมาใช้ในการคำนวณทีหลัง ขั้นตอนวิธีของเฮิร์ชเบิร์กจะใช้เวลาในการทำงานเป็น 2 เท่าของขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์ (Needleman-Wunsch algorithm) แต่ก็ยังถือว่าอยู่ในเวลา O(*nm*)

## รหัสเทียม
คำอธิบายระดับสูงของโปรแกรมย่อยไปข้างหน้า

```text
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
```


คำอธิบายระดับสูงของโปรแกรมย่อยถอยหลัง


```text
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
```


คำอธิบายระดับสูงของขั้นตอนวิธีเฮิร์ชเบิร์ก :


```text
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(x_left,Prefix[y,cut])
      H.  Hirschberg(x_right,Suffix[y,m-cut])
```


## ตัวอย่างประยุกต์ใช้งาน
ประโยชน์สำคัญอันหนึ่งของขั้นตอนวิธีนี้ คือ การหาการลำดับเรียงตัวของสาย DNA และสายโปรตีน ซึ่งมันเป็นวิธีที่มีประสิทธิภาพในการคำนวณลำดับย่อยร่วมยาวสุด (Longest cummon subsequence) ระหว่างกลุ่มข้อมูล 2 กลุ่มที่แตกต่างกัน

## ดูเพิ่ม
* :en:Needleman-Wunsch algorithm
* :en:Smith Waterman algorithm
* :en:Levenshtein distance
* Longest Common Subsequence

## ความเห็นส่วนตัวของคนเขียน

ผู้ศึกษาขั้นตอนวิธีการของเฮิร์ชเบิร์ก เป็นขั้นตอนวิธีที่มีประโยชน์มากในการที่จะนำไปประยุกต์ใช้งาน เนื่องจากในโลกปัจจุบันเรามีข้อมูลจำนวนมากที่เป็นสายอักขระ ดังนั้นการที่เรามีขั้นตอนวิธีการที่ใช้เปรียบเทียบสายอักขระได้อย่างมีประสิทธิภาพ จะทำให้เราสามารถแก้ไขปัญหาหลายๆปัญหาที่เกี่ยวข้องกับสายอักขระได้อย่างมีประสิทธิภาพด้วยเช่นกัน

## แหล่งเอกสารอ้างอิง
เอกสารการเรียนเรื่องการจัดเรียง

## การเชื่อมโยงภายนอก

หมวดหมู่:ขั้นตอนวิธีการจัดลำดับ
หมวดหมู่:ขั้นตอนวิธีชีวสารสนเทศศาสตร์
หมวดหมู่:กำหนดการพลวัต