Damerau–Levenshtein distance

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

Damerau คิดเฉพาะการสะกดผิดที่สามารถแก้ไขด้วยการกระทำเพียงครั้งเดียว ส่วนการหาระยะทางที่เกิดจากการกระทำหลายการกระทำเป็นของ Levenshtein ในชื่อ 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* คือความยาวของสายอักขระ

## ดูเพิ่ม
* Levenshtein edit distance
* ขั้นตอนวิธีของเฮิร์ชเบิร์ก
* ขั้นตอนวิธีของนีเดอมาน–วานซ์
* Approximate string matching
* Levenshtein automata
* Typosquatting

## อ้างอิง

## แหล่งข้อมูลอื่น
* Python implementation of optimal string alignment distance
* FREJ - an open source java library which implements approximate substring search using Damerau-Levenshtein distance.
* Ruby translation of above Python implementation.
* MySQL stored function implementation of the Levenshtein distance, extended to optimal string alignment distance (source code) <-- This link seems broken, but here's a backup. 
* MySQL implementation as a compiled UDF (User Defined Function)
* MySQL implementation, compiled as a Windows DLL
* C# implementation
*  Site devoted to fuzzy searching and information retrieval 

หมวดหมู่:ขั้นตอนวิธี
หมวดหมู่:ทฤษฎีสารสนเทศ
หมวดหมู่:การวัดความคล้ายกันของสายอักขระ