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

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 
 การสำรวจรายชื่อทารก 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

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