Bài 11: Huffman Data Compression — Nén Dữ Liệu Không Mất Mát

Ở Bài 10 chúng ta dùng cây/bảng để tra cứu nhanh hơn. Bài này chuyển sang một bài toán khác hẳn: biểu diễn cùng một dữ liệu bằng ít bit hơn mà không mất thông tin gì cả — nén dữ liệu không mất mát (lossless compression). Thuật toán Huffman Coding, ra đời năm 1952, vẫn là thành phần lõi bên trong gzip, ZIP, PNG và JPEG ngày nay.

1. Vì sao cần nén dữ liệu? Từ mã cố định đến mã có độ dài thay đổi

Cách biểu diễn ký tự đơn giản nhất — ASCII — dùng đúng 8 bit cho mọi ký tự, bất kể ký tự đó xuất hiện 1 lần hay 1000 lần trong văn bản. Đây là mã có độ dài cố định (fixed-length code). Ý tưởng của Huffman đơn giản nhưng mạnh mẽ, giống hệt mã Morse: ký tự xuất hiện càng thường xuyên thì mã càng ngắn, ký tự hiếm gặp thì mã dài hơn cũng được — vì nó ít khi phải trả giá. Kết quả là độ dài trung bình trên toàn văn bản giảm đáng kể so với mã cố định.

2. Mã Tiền Tố (Prefix Code): Điều Kiện Bắt Buộc Để Giải Mã Không Mập Mờ

Nếu để độ dài mã thay đổi tự do, giải mã có thể trở nên mập mờ: giả sử a = 0 và b = 01 — khi gặp bitstream 01, không thể biết đó là a rồi 1 (không hợp lệ) hay b. Giải pháp: bắt buộc mã tiền tố (prefix-free code) — không mã nào là tiền tố của một mã khác. Cách biểu diễn tự nhiên nhất cho mã tiền tố là một cây nhị phân: đi trái = bit 0, đi phải = bit 1, và ký tự chỉ nằm ở node lá — vì lá không có node nào "đi xuyên qua" nó để tạo tiền tố trùng.

3. Thuật Toán Tham Lam Của Huffman: Xây Cây Từ Dưới Lên

Huffman xây cây theo chiều ngược lại so với trực giác — bắt đầu từ các lá (mỗi ký tự là 1 lá mang tần suất riêng), rồi gộp dần lên gốc. Ở mỗi bước, thuật toán tham lam (greedy) luôn chọn 2 node có tần suất thấp nhất hiện có, gộp chúng thành 1 node cha mới với tần suất bằng tổng — rồi lặp lại cho tới khi chỉ còn 1 node (gốc):

function buildHuffmanTree(freqMap) {
  // Mỗi ký tự bắt đầu là 1 node lá độc lập
  let nodes = Object.entries(freqMap).map(([char, freq]) => ({ char, freq, left: null, right: null }));

  while (nodes.length > 1) {
    nodes.sort((a, b) => a.freq - b.freq); // O(n log n) mỗi vòng — dùng min-heap thực tế sẽ là O(log n)
    const a = nodes.shift(); // node tần suất THẤP NHẤT
    const b = nodes.shift(); // node tần suất THẤP NHÌ
    nodes.push({ char: null, freq: a.freq + b.freq, left: a, right: b }); // node cha MỚI, không mang ký tự
  }
  return nodes[0]; // gốc của cây Huffman
}

4. Sinh Bảng Mã (Code Table) Từ Cây

Sau khi có cây, duyệt từ gốc bằng DFS, tích luỹ chuỗi bit theo hướng đi (trái nối '0', phải nối '1'); khi chạm một lá, chuỗi bit tích luỹ chính là mã của ký tự đó:

function generateCodes(node, prefix = '', codes = {}) {
  if (!node.left && !node.right) {
    codes[node.char] = prefix || '0'; // trường hợp đặc biệt: chỉ có 1 ký tự duy nhất trong văn bản
    return codes;
  }
  if (node.left) generateCodes(node.left, prefix + '0', codes);
  if (node.right) generateCodes(node.right, prefix + '1', codes);
  return codes;
}

5. Encode: Từ Chuỗi Ký Tự Sang Bitstream

Mã hoá chỉ đơn giản là nối mã nhị phân của từng ký tự lại theo đúng thứ tự xuất hiện trong văn bản gốc:

function encode(text, codes) {
  return text
    .split('')
    .map((char) => codes[char])
    .join('');
}

6. Decode: Duyệt Cây Theo Từng Bit

Giải mã đi ngược lại: bắt đầu từ gốc cây, đọc từng bit của bitstream — gặp 0 thì đi trái, gặp 1 thì đi phải. Khi chạm một lá, xuất ký tự tại đó rồi quay lại gốc để tiếp tục đọc các bit kế tiếp:

function decode(bitstream, root) {
  let result = '';
  let node = root;
  for (const bit of bitstream) {
    node = bit === '0' ? node.left : node.right;
    if (!node.left && !node.right) {
      // chạm lá — xuất ký tự và quay về gốc để đọc ký tự kế tiếp
      result += node.char;
      node = root;
    }
  }
  return result;
}

7. Tỷ Lệ Nén & Trường Hợp Xấu Nhất

Kích thước sau nén bằng tổng của tần suất × độ dài mã cho mọi ký tự — chính là công thức tính độ dài trung bình có trọng số mà thuật toán tham lam đang tối thiểu hoá:

$$\text{bits nén} = \sum_i \text{freq}_i \times \text{length}_i$$

8. So Sánh Mã Cố Định (ASCII) vs Huffman

Sân chơi tương tác: Huffman Tree Builder

Nhập một đoạn văn bản, xem thuật toán tham lam gộp node từng bước trong nhật ký, cây Huffman được vẽ trực quan, bảng mã sinh ra cho từng ký tự, và tỷ lệ nén so với ASCII 8-bit/ký tự.