Levenshtein Distance ใน JavaScript

Levenshtein Distance คืออะไร

Levenshtein Distance (ระยะทางเลเวนชไทน์) เป็นเมตริกวัดความแตกต่างระหว่างสตริงสองตัว คือ จำนวนการแก้ไขขั้นต่ำ (Insert, Delete, Substitute) เพื่อเปลี่ยนสตริงหนึ่งให้กลายเป็นอีกตัว

ตัวอย่าง

const str1 = 'hitting';
const str2 = 'kitten';

ระยะทาง = 3 (3 ขั้นตอน):

1. kitten → hitten (แทนที่ k ด้วย h)
2. hitten → hittin (แทนที่ e ด้วย i)
3. hittin → hitting (แทรก g ท้าย)

โค้ดตัวอย่าง (Dynamic Programming)

const str1 = 'hitting';
const str2 = 'kitten';

const levenshteinDistance = (str1 = '', str2 = '') => {
  // สร้างตาราง DP (str2.length+1) x (str1.length+1)
  const track = Array(str2.length + 1).fill(null).map(() => 
    Array(str1.length + 1).fill(null));
  
  // เริ่มต้นแถวแรกและคอลัมน์แรก
  for (let i = 0; i <= str1.length; i++) track[0][i] = i;
  for (let j = 0; j <= str2.length; j++) track[j][0] = j;
  
  // เติมตาราง
  for (let j = 1; j <= str2.length; j++) {
    for (let i = 1; i <= str1.length; i++) {
      const indicator = str1[i - 1] === str2[j - 1] ? 0 : 1;
      track[j][i] = Math.min(
        track[j][i - 1] + 1,        // deletion
        track[j - 1][i] + 1,        // insertion
        track[j - 1][i - 1] + indicator // substitution
      );
    }
  }
  
  return track[str2.length][str1.length];
};

console.log(levenshteinDistance(str1, str2));

ผลลัพธ์

3

การประยุกต์ใช้

• Spell Checker / Auto-correct
• DNA Sequence Alignment
• Plagiarism Detection
• Fuzzy String Matching
• OCR Post-processing

ความซับซ้อน

• Time: O(m × n) โดย m, n = ความยาวสตริง
• Space: O(m × n) สามารถลดเหลือ O(min(m,n)) ได้ด้วยการเก็บแถวเดียว

โค้ดเวอร์ชันประหยัดหน่วยความจำ

const levenshteinOptimized = (str1, str2) => {
  if (str1.length < str2.length) [str1, str2] = [str2, str1];
  
  let prevRow = Array(str2.length + 1).fill(0).map((_, i) => i);
  let currRow = Array(str2.length + 1).fill(0);
  
  for (let i = 1; i <= str1.length; i++) {
    currRow[0] = i;
    for (let j = 1; j <= str2.length; j++) {
      const cost = str1[i-1] === str2[j-1] ? 0 : 1;
      currRow[j] = Math.min(
        prevRow[j] + 1,
        currRow[j-1] + 1,
        prevRow[j-1] + cost
      );
    }
    [prevRow, currRow] = [currRow, prevRow];
  }
  return prevRow[str2.length];
};