ระยะทางเลเวนชเตย์น
 | ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
Levenshtein edit distance เป็นขั้นตอนวิธีการวัดหาค่าความต่างกันของสายอักขระสองชุด ระหว่างชุดแรกที่เป็นต้นแบบ และ ชุดที่สองที่เป็นชุดเปรียบเทียบ โดยค่าความต่างกันจะวัดจากจำนวนของการที่จะต้องทำการตัดออก แทรก และแทนที่ อักขระในชุดที่นำมาเปรียบเทียบจนกระทั่งมีลักษณะเหมือนชุดอักขระที่เป็นต้นแบบทุกประการ ขั้นตอนวิธีการวัดใช้กำหนดการพลวัตในการแก้ปัญหา
ประวัติ
[แก้]Levenshtein Edit Distance ถูกตั้งชื่อตามนักวิทยาศาสตร์ชาวรัสเซีย Vladimir Levenshtein ซึ่งเป็นผู้ปรับปรุงชุด Algorithms นี้ในปี ค.ศ. 1965 และเป็นส่วนหนึ่งในรางวัล IEEE Rechard W. Hamming Medal ที่เขาได้รับในปี ค.ศ. 2006
คำอธิบาย
[แก้]ขั้นตอนวิธีการนี้จะเป็นการนำชุดอักขระ 2 ชุด มาเปรียบเทียบจำนวนความแตกต่างกัน โดยจะพิจารณาดังนี้
- การแทรก เป็นการนำเอาอักขระตัวใดๆมา เพื่อให้ชุดอักขระชุดนั้นเหมือนกับอีกชุดอักขระหนึ่งในภายหลัง เช่น run → ruin จะแทรกตัว i ให้กับ run เพื่อให้ run กลายเป็น ruin เป็นต้น
- การตัดออก เป็นการตัดอักขระออกครั้งละ 1 ตัว จากชุดอักขระตัวหนึ่ง เพื่อให้ชุดอักขระชุดนั้นเหมือนกับอีกชุดอักขระหนึ่งในภายหลัง เช่น dog → do จะตัดตัว g ออก เพื่อให้ dog กลายเป็น do เป็นต้น
- การแทนที่ เป็นการนำอักขระของชุดอักขระหนึ่งไปแทนอักขระของอีกชุดอักขระหนึ่ง เพื่อให้ชุดอักขระชุดนั้นเหมือนกับอีกชุดอักขระหนึ่งในภายหลัง เช่น cat → rat จะแทนที่ r ด้วย c เพื่อให้ cat กลายเป็น rat หรือ อาจมองในทางกลับกันก็ได้ เป็นต้น
รหัสเทียม
[แก้]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 // การแทนที่
)
}
}
return d[m,n]
}
ตัวอย่าง
[แก้]| m | e | t | h | o | d | ||
|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| a | 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| l | 2 | 2 | 2 | 3 | 4 | 5 | 6 |
| g | 3 | 3 | 3 | 3 | 4 | 5 | 6 |
| o | 4 | 4 | 4 | 4 | 4 | 4 | 5 |
| r | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
| i | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
| t | 7 | 7 | 7 | 6 | 7 | 7 | 7 |
| h | 8 | 8 | 8 | 7 | 6 | 7 | 8 |
| m | 9 | 8 | 9 | 8 | 7 | 7 | 8 |
จากตัวอย่างจะเห็นว่า คำว่า algorithm และ คำว่า method มีค่าความต่างกันอยู่คือ 8 โดยได้มาจาก
- การแทรก a, l, g และ o ดำเนินการ 4 ครั้ง
- การตัด o ของ method ออก ดำเนินการ 1 ครั้ง
- การแทนที่ m ด้วย r, e ด้วย i และ d ด้วย m ดำเนินการ 3 ครั้ง
ดั้งนั้น จะต้องดำเนินการทั้งหมด 8 ครั้ง จึงมีค่าความต่างกันอยู่ 8
การพิสูจน์ความถูกต้อง
[แก้]เราสามารถแปลงชุดอักขระเริ่มต้น s[1..i] เป็นชุดอักขระเปรียบเทียบ t[1..j] โดยใช้จำนวนครั้งในการกระทำคือ d[i,j] ซึ่งเป็นจำนวนครั้งของการกระทำที่น้อยที่สุด สามารถแสดงการพิสูจน์ความถูกต้องได้ดังนี้
- เราจะต้องเริ่มจากแถว และ สดมภ์ ที่ 0 เพราะว่าชุดอักขระ s[1..i] สามารถแปลงเป็นชุดอักขระว่างเปล่า t[1..0] ได้ โดยการตัดอักขระของชุดอักขระ s[1..i] ออกทั้งหมด i ตัว และในทำนองเดียวกัน เราก็สามารถแปลงจากชุดอักขระว่างเปล่า s[1..0] เป็นชุดอักขระ t[1..j] ได้ โดยเพิ่มอักขระจำนวน j ตัว
- ถ้า s[i] = t[j] และเราสามารถแปลงชุดอักขระ s[1..i-1] เป็นชุดอักขระ t[1..j-1] ใน k ครั้งแล้ว เราก็สามารถทำในทำนองเดียวกันกับ s[1..i] ได้ใน k ครั้ง โดยสามารถละเลยอักขระตัวสุดท้ายไปได้
- มิฉะนั้นแล้ว การแปลงชุดอักขระโดยมีค่าการกระทำน้อยที่สุดสามารถดำเนินการได้ด้วยสามวิธีดังนี้
- ถ้าเราสามารถแปลงชุดอักขระ s[1..i] เป็นชุดอักขระ t[1..j-1] ใน k ครั้งแล้ว เราก็สามารถเพิ่มอักขระ t[j] ได้ เพื่อที่จะให้ได้ข้อความ t[1..j] โดยใช้การกระทำ k+1 ครั้ง (การแทรก)
- ถ้าเราสามารถแปลงชุดอักขระ s[1..i-1] เป็นชุดอักขระt[1..j] ใน k ครั้งแล้ว เราก็สามารถลด s[i] ออก แล้วกระทำการแปลงข้อความตามเดิม จำนวนครั้งจะเท่ากับ k+1 ครั้ง (การตัดออก)
- ถ้าเราสามารถแปลงชุดอักขระ s[1..i-1] เป็นชุดอักขระ t[1..j-1] ใน k ครั้ง เราก็สามารถทำในทำนองเดียวกันกับชุดอักขระ s[1..i] และเปลี่ยนอักขระต้นแบบ s[i] ไปเป็นอักขระ t[j] ได้ จำนวนครั้งจะเท่ากับ k+1 ครั้ง (การแทนที่)
- จำนวนการกระทำที่ต้องการแปลงจากชุดอักขระ s[1..n] เป็นชุดอักขระ t[1..m] คือจำนวนครั้งที่ใช้ในการแปลงอักขระทั้งหมดใน s ไปเป็นอักขระทั้งหมดใน t ซึ่งจะปรากฏในตำแหน่ง d[n, m]
การนำไปประยุกต์ใช้
[แก้]Levenshtein Edit Distance ถูกใช้ในการตรวจคำสะกด พิสูจน์ประโยคข้อความ วิเคราะห์รหัสพันธุกรรม ตรวจสอบการคัดลอกข้อความ และ อื่นๆอีกมากมาย เช่น
- การกรองรายชื่ออีเมลล์ filter blocks of email lists เก็บถาวร 2011-10-08 ที่ เวย์แบ็กแมชชีน
- การสำรวจรายชื่อทารก the ultimate baby name explorer เก็บถาวร 2011-10-07 ที่ เวย์แบ็กแมชชีน
- การตั้งชื่อสินค้า และ บริการ
- ใช้เป็นส่วนหนึ่งของการตรวจสอบการสะกดคำ spell checker
- ใช้พิสูจน์เนื้อหาที่เลียนแบบมา และ การลอกเลียนแบบ
- ใช้เพื่อแก้คำผิด สำหรับการค้นหาของเครื่องมือค้นหา
ขั้นตอนวิธีอื่นๆที่เกี่ยวข้อง
[แก้]- agrep
- Approximate string matching
- Bitap algorithm
- Damerau–Levenshtein distance
- diff
- Dynamic time warping
- Euclidean distance
- Fuzzy string searching
- Hamming weight
- Hirschberg's algorithm
- Homology of sequences in genetics
- Hunt–McIlroy algorithm
- Jaccard index
- Jaro–Winkler distance
- Levenshtein automaton
- Longest common subsequence problem
- Lucene
- Manhattan distance
- Metric space
- Needleman–Wunsch algorithm
- Sequence alignment
- Similarity (mathematics)
- Similarity space on Numerical taxonomy
- Smith–Waterman algorithm
- Sørensen similarity index
- Typosquatting
ดูเพิ่ม
[แก้]อ้างอิง
[แก้]- Lloyd Allison, Dynamic Programming Algorithm (DPA) for Edit-Distance
- Alex Bogomolny, Distance Between Strings
- Thierry Lecroq, Levenshtein Distance