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

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 ถูกใช้ในการตรวจคำสะกด พิสูจน์ประโยคข้อความ วิเคราะห์รหัสพันธุกรรม ตรวจสอบการคัดลอกข้อความ และ อื่นๆอีกมากมาย เช่น

• การกรองรายชื่ออีเมลล์ 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