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 
ขั้นตอนวิธี
ทฤษฎีสารสนเทศ
การวัดความคล้ายกันของสายอักขระ