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 จะได้ว่า ประสิทธิภาพในการทำงานเป็น เมื่อ m, n คือความยาวของสายอักขระ
ดูเพิ่ม
[แก้]- Levenshtein edit distance
- ขั้นตอนวิธีของเฮิร์ชเบิร์ก
- ขั้นตอนวิธีของนีเดอมาน–วานซ์
- Approximate string matching
- Levenshtein automata
- Typosquatting
อ้างอิง
[แก้]- ↑ Vladimir I. Levenshtein, Binary codes capable of correcting deletions, insertions and reversals. Soviet Physice – Doklady 10, pp. 707-710, 1966.
แหล่งข้อมูลอื่น
[แก้]- 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. เก็บถาวร 2011-09-29 ที่ เวย์แบ็กแมชชีน
- 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 เก็บถาวร 2011-09-29 ที่ เวย์แบ็กแมชชีน