ระยะทางเลเวนชเตย์น

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]
}
== ตัวอย่าง ==
{|class="wikitable"
! scope="col" |
! scope="col" |
! scope="col" | m
! scope="col" | e
! scope="col" | t
! scope="col" | h
! scope="col" | o
! scope="col" | d
|-
! scope="row" |
| 0 || 1 || 2 || 3 || 4 || 5 || 6
|-
! scope="row" | a
| 1 || 1 || 2 || 3 || 4 || 5 || 6
|-
! scope="row" | l
| 2 || 2 || 2 || 3 || 4 || 5 || 6
|-
! scope="row" | g
| 3 || 3 || 3 || 3 || 4 || 5 || 6
|-
! scope="row" | o
| 4 || 4 || 4 || 4 || 4 || 4 || 5
|-
! scope="row" | r
| 5 || 5 || 5 || 5 || 5 || 5 || 5
|-
! scope="row" | i
| 6 || 6 || 6 || 6 || 6 || 6 || 6
|-
! scope="row" | t
| 7 || 7 || 7 || 6 || 7 || 7 || 7
|-
! scope="row" | h
| 8 || 8 || 8 || 7 || 6 || 7 || 8
|-
! scope="row" | 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 
การสำรวจรายชื่อทารก the ultimate baby name explorer 
การตั้งชื่อสินค้า และ บริการ
ใช้เป็นส่วนหนึ่งของการตรวจสอบการสะกดคำ 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
== ดูเพิ่ม ==
C# implementation
== อ้างอิง ==
Lloyd Allison, Dynamic Programming Algorithm (DPA) for Edit-Distance
Alex Bogomolny, Distance Between Strings
Thierry Lecroq, Levenshtein Distance
กำหนดการพลวัต
การวัดความคล้ายกันของสายอักขระ