Damerau–Levenshtein distance

ในทฤษฎีสารสนเทศและวิทยาการคอมพิวเตอร์ Damerau–Levenshtein distance (ตั้งตามชื่อผู้คิดค้น Frederick J. Damerau และ Vladimir I. Levenshtein) คือระยะทางระหว่างสองสายอักขระ ซึ่งสามารถหาได้จากจำนวนการกระทำที่น้อยที่ในการแปลงสายอักขระหนึ่งมาเป็นอีกสายอักขนะหนึ่ง โดยการกระทำที่สามารถทำกับสายอักขระได้มีสี่แบบ ดังนี้

การเพิ่มอักขระ
การลบอักขระ
การเปลี่ยนแปลงอักขระ
การสลับอักขระ (อาจกำหนดให้สามารถสลับได้เฉพาะอักขระที่อยู่ติดกันหรือไม่จำเป็นต้องอยู่ติดกันก็ได้ ขึ้นอยู่กับการใช้งาน)

Damerau คิดเฉพาะการสะกดผิดที่สามารถแก้ไขด้วยการกระทำเพียงครั้งเดียว ส่วนการหาระยะทางที่เกิดจากการกระทำหลายการกระทำเป็นของ Levenshtein^[1] ในชื่อ Levenshtein edit distance แต่ Levenshtein ไม่มีการกระทำสลับอักขระ เมื่อนำมารวมกันจึงได้เป็น Damerau–Levenshtein distance

ถึงแม้ตอนแรกจะใช้ในการแก้คำที่ผู้ใช้พิมพ์ผิด แต่ในปัจจุบัน Damerau–Levenshtein distance ถูกใช้ในชีววิทยาในการหาความแตกต่างระหว่างสายอักขระ DNA อีกด้วย

คำอธิบาย[แก้]

Damerau–Levenshtein distance เป็นการแก้ไข Levenshtein edit distance ให้มีการกระทำสลับอักขระเพิ่มขึ้น โดยสามารถนำ Levenshtein edit distance ซึ่งใช้การแก้ปัญหาโดยกำหนดการพลวัต มาแก้ไขเพิ่มเติมการกระทำได้เลย

รหัสเทียม[แก้]

เพิ่มการกระทำจาก Levenshtein edit distance เข้าไปอีกหนึ่งการกระทำ ดังนี้

if(i > 1 and j > 1 and str1[i] = str2[j-1] and str1[i-1] = str2[j]) then
 d[i, j] := minimum(
 d[i, j],
 d[i-2, j-2] + cost   // transposition
 )

จะได้รหัสเทียมที่สมบูรณ์เป็น

int LevenshteinDistance(char s[1..m], char t[1..n])
{
 // สำหรับทุกๆค่า i และ j, d[i,j] จะแสดงค่าความแตกต่างระหว่างอักขระ i ตัวแรกของ s และ อักขระ j ตัวแรกของ t สังเกตว่า แถวลำดับ d จะมีขนาด (m+1)x(n+1)
 declare int d[0..m, 0..n]
 for i from 0 to m
   d[i, 0] := i // ค่าความแตกต่างระหว่างข้อความแรกใดๆ กับ ข้อความที่สองที่ว่างเปล่า
  for j from 0 to n
   d[0, j] := j // ค่าความแตกต่างระหว่างข้อความที่สองใดๆ กับ ข้อความแรกที่ว่างเปล่า
  for j from 1 to n
 {
   for i from 1 to m
   {
     if s[i] = t[j] then
       d[i, j] := d[i-1, j-1]       // พิจารณาตัวถัดมา
     else
       d[i, j] := minimum
                  (
                    d[i-1, j] + 1,  // การตัดออก
                    d[i, j-1] + 1,  // การแทรก
                    d[i-1, j-1] + 1 // การแทนที่
                  )
      if(i > 1 and j > 1 and s[i] = t[j-1] and s[i-1] = t[j]) then
       d[i, j] := minimum(
       d[i, j],
       d[i-2, j-2] + cost   // การสลับอักขระ
       )
   }
 }
 return d[m,n]
}

ประสิทธิภาพในการทำงาน[แก้]

เนื่องจากมีการวนสำหรับทุกอักขระในอักขระ s และ t จะได้ว่า ประสิทธิภาพในการทำงานเป็น $O\left(m\cdot n\right)$ เมื่อ m, n คือความยาวของสายอักขระ

ดูเพิ่ม[แก้]

อ้างอิง[แก้]

↑ Vladimir I. Levenshtein, Binary codes capable of correcting deletions, insertions and reversals. Soviet Physice – Doklady 10, pp. 707-710, 1966.

แหล่งข้อมูลอื่น[แก้]

[1] Vladimir I. Levenshtein, Binary codes capable of correcting deletions, insertions and reversals. Soviet Physice – Doklady 10, pp. 707-710, 1966.

[1]