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

**Levenshtein edit distance** เป็นขั้นตอนวิธีการวัดหาค่าความต่างกันของสายอักขระสองชุด ระหว่างชุดแรกที่เป็นต้นแบบ และ ชุดที่สองที่เป็นชุดเปรียบเทียบ โดยค่าความต่างกันจะวัดจากจำนวนของการที่จะต้องทำการตัดออก แทรก และแทนที่ อักขระในชุดที่นำมาเปรียบเทียบจนกระทั่งมีลักษณะเหมือนชุดอักขระที่เป็นต้นแบบทุกประการ ขั้นตอนวิธีการวัดใช้กำหนดการพลวัตในการแก้ปัญหา

## ประวัติ
Levenshtein Edit Distance ถูกตั้งชื่อตามนักวิทยาศาสตร์ชาวรัสเซีย Vladimir Levenshtein ซึ่งเป็นผู้ปรับปรุงชุด Algorithms นี้ในปี ค.ศ. 1965 และเป็นส่วนหนึ่งในรางวัล IEEE Rechard W. Hamming Medal ที่เขาได้รับในปี ค.ศ. 2006

## คำอธิบาย
ขั้นตอนวิธีการนี้จะเป็นการนำชุดอักขระ 2 ชุด มาเปรียบเทียบจำนวนความแตกต่างกัน โดยจะพิจารณาดังนี้
# การแทรก เป็นการนำเอาอักขระตัวใดๆมา เพื่อให้ชุดอักขระชุดนั้นเหมือนกับอีกชุดอักขระหนึ่งในภายหลัง เช่น run → ru**i**n จะแทรกตัว i ให้กับ run เพื่อให้ run กลายเป็น ruin เป็นต้น
# การตัดออก เป็นการตัดอักขระออกครั้งละ 1 ตัว จากชุดอักขระตัวหนึ่ง เพื่อให้ชุดอักขระชุดนั้นเหมือนกับอีกชุดอักขระหนึ่งในภายหลัง เช่น do**g** → do จะตัดตัว g ออก เพื่อให้ dog กลายเป็น do เป็นต้น
# การแทนที่ เป็นการนำอักขระของชุดอักขระหนึ่งไปแทนอักขระของอีกชุดอักขระหนึ่ง เพื่อให้ชุดอักขระชุดนั้นเหมือนกับอีกชุดอักขระหนึ่งในภายหลัง เช่น **c**at → **r**at จะแทนที่ 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]
 }

## ตัวอย่าง



จากตัวอย่างจะเห็นว่า คำว่า 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

หมวดหมู่:กำหนดการพลวัต
หมวดหมู่:การวัดความคล้ายกันของสายอักขระ