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

จากวิกิพีเดีย สารานุกรมเสรี

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

ประวัติ[แก้]

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

คำอธิบาย[แก้]

ขั้นตอนวิธีการนี้จะเป็นการนำชุดอักขระ 2 ชุด มาเปรียบเทียบจำนวนความแตกต่างกัน โดยจะพิจารณาดังนี้

  1. การแทรก เป็นการนำเอาอักขระตัวใดๆมา เพื่อให้ชุดอักขระชุดนั้นเหมือนกับอีกชุดอักขระหนึ่งในภายหลัง เช่น run → ruin จะแทรกตัว i ให้กับ run เพื่อให้ run กลายเป็น ruin เป็นต้น
  2. การตัดออก เป็นการตัดอักขระออกครั้งละ 1 ตัว จากชุดอักขระตัวหนึ่ง เพื่อให้ชุดอักขระชุดนั้นเหมือนกับอีกชุดอักขระหนึ่งในภายหลัง เช่น dog → do จะตัดตัว g ออก เพื่อให้ dog กลายเป็น do เป็นต้น
  3. การแทนที่ เป็นการนำอักขระของชุดอักขระหนึ่งไปแทนอักขระของอีกชุดอักขระหนึ่ง เพื่อให้ชุดอักขระชุดนั้นเหมือนกับอีกชุดอักขระหนึ่งในภายหลัง เช่น 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 ถูกใช้ในการตรวจคำสะกด พิสูจน์ประโยคข้อความ วิเคราะห์รหัสพันธุกรรม ตรวจสอบการคัดลอกข้อความ และ อื่นๆอีกมากมาย เช่น

ขั้นตอนวิธีอื่นๆที่เกี่ยวข้อง[แก้]

  • 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