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]