Hamming Distance ระหว่างสองสตริงใน JavaScript

Hamming Distance คืออะไร

Hamming Distance ระหว่างสตริงสองตัวที่มี ความยาวเท่ากัน คือ จำนวนตำแหน่งที่ตัวอักษรต่างกัน

ตัวอย่าง

const str1 = 'delhi';
const str2 = 'delph';

ตำแหน่งที่ 4 (h vs p) และ 5 (i vs h) ต่างกัน → Hamming Distance = 2

โค้ดตัวอย่าง

const str1 = 'delhi';
const str2 = 'delph';

const hammingDistance = (str1 = '', str2 = '') => {
  // ต้องมีความยาวเท่ากัน
  if (str1.length !== str2.length) {
    return 0; // หรือ throw error
  }
  
  let dist = 0;
  for (let i = 0; i < str1.length; i++) {
    if (str1[i] !== str2[i]) {
      dist++;
    }
  }
  return dist;
};

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

ผลลัพธ์

2

วิธีทันสมัย (ES6+)

// ใช้ spread operator และ reduce
const hammingModern = (str1, str2) => {
  if (str1.length !== str2.length) throw new Error('Strings must have equal length');
  return [...str1].reduce((count, char, i) => count + (char !== str2[i]), 0);
};

// ใช้ filter
const hammingFilter = (str1, str2) => {
  if (str1.length !== str2.length) throw new Error('Strings must have equal length');
  return [...str1].filter((char, i) => char !== str2[i]).length;
};

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

• Error Detection/Correction - รหัสแก้ไขข้อผิดพลาด (Error-correcting codes)
• Bioinformatics - เปรียบเทียบ DNA sequences
• Cryptography - วิเคราะห์ความแตกต่างของคีย์
• Data Transmission - ตรวจสอบข้อมูลเสียหาย

ขยาย: Hamming Distance สำหรับตัวเลข (Bitwise)

const hammingDistanceInt = (x, y) => {
  let xor = x ^ y; // XOR จะได้บิตที่ต่างกัน
  let count = 0;
  while (xor) {
    count += xor & 1;
    xor >>= 1;
  }
  return count;
};

// หรือใช้ built-in (ES2015+)
const hammingBuiltin = (x, y) => (x ^ y).toString(2).split('0').join('').length;

console.log(hammingDistanceInt(1, 4)); // 2 (001 vs 100)
console.log(hammingBuiltin(1, 4));     // 2

สรุป

• ใช้ได้เฉพาะสตริง/ข้อมูลที่มีความยาวเท่ากัน
• Time: O(n), Space: O(1)
• สำหรับตัวเลข ใช้ Bitwise XOR จะเร็วกว่ามาก