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 คือความยาวของสายอักขระ
ดูเพิ่ม แก้
อ้างอิง แก้
- ↑ 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.
- 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 ที่ เวย์แบ็กแมชชีน