Huffman Coding — Nén dữ liệu với chiến lược Greedy

Mỗi lần bạn nén file ZIP, gửi request HTTP/2, hay lưu ảnh JPEG — Huffman Coding đang chạy ngầm bên dưới. Thuật toán này, được David Huffman công bố năm 1952, giải quyết một bài toán tưởng đơn giản: gán mã nhị phân ngắn hơn cho ký tự xuất hiện nhiều hơn để giảm tổng kích thước dữ liệu. Kết quả là nén lossless — không mất một bit thông tin nào.

Điều thú vị nằm ở chiến lược xây dựng: Huffman Coding là một thuật toán Greedy thuần túy. Tại mỗi bước, nó chọn hai node có tần suất nhỏ nhất để gộp, và quyết định này không bao giờ cần xem xét lại. Chiến lược tham lam này — khác với nhiều bài toán tham lam khác — được chứng minh toán học là luôn cho mã tối ưu cho mô hình mã hóa symbol-by-symbol.

Nắm vững Huffman Coding không chỉ giúp bạn hiểu nền tảng của hệ sinh thái nén dữ liệu hiện đại (DEFLATE, GZIP, Brotli), mà còn rèn luyện tư duy thiết kế thuật toán Greedy — kỹ năng xuất hiện trong hàng loạt bài toán từ scheduling đến network routing.

Bức tranh tư duy

Hình dung bạn là quản lý một kho hàng ở Bình Dương, cần gửi hàng ngàn kiện hàng mỗi ngày. Mỗi kiện cần dán nhãn mã vạch để phân loại. Nếu dùng mã cố định 8 ký tự cho mọi kiện, bạn tốn rất nhiều mực in và thời gian quét. Nhưng nếu kiện hàng loại A chiếm 60% tổng lượng — bạn gán mã ngắn nhất cho A (ví dụ chỉ 1 ký tự), mã dài hơn cho các loại hiếm. Tổng chi phí in ấn giảm đáng kể.

Huffman Coding hoạt động theo nguyên tắc tương tự, nhưng với bit thay vì ký tự:

text

Ví dụ cụ thể: Chuỗi "AAAAABBBCCCD" (12 ký tự)

Mã cố định (fixed-length, 2 bit/ký tự vì có 4 loại):
  A=00  B=01  C=10  D=11
  Tổng: 12 × 2 = 24 bit

Mã Huffman (variable-length):
  A=0   B=10  C=110  D=111
  Tổng: 5×1 + 3×2 + 3×3 + 1×3 = 5 + 6 + 9 + 3 = 23 bit

  → Tiết kiệm ~4% ngay cả trên chuỗi ngắn.
    Trên dữ liệu thực tế (văn bản, log file), tỷ lệ nén đạt 40-60%.

Điều kiện then chốt: mã phải là prefix-free — không mã nào là tiền tố của mã khác. Nếu A=0 và B=01, khi đọc chuỗi bit "01", không thể phân biệt "AB" hay "B". Huffman tự động đảm bảo tính chất này nhờ cấu trúc cây nhị phân — mỗi ký tự chỉ nằm ở lá (leaf), không bao giờ ở node nội bộ.

Cốt lõi kỹ thuật

Quy trình xây dựng cây Huffman

Thuật toán gồm 4 bước, mỗi bước xây trên kết quả bước trước:

Bước 1 — Đếm tần suất:

text

"AAAAABBBCCCD"  →  A:5, B:3, C:3, D:1

Bước 2 — Khởi tạo min-heap (priority queue):

Mỗi ký tự trở thành một node lá, đưa vào min-heap sắp theo tần suất:

text

Min-Heap: [D:1, B:3, C:3, A:5]

Bước 3 — Gộp Greedy lặp lại:

Tại mỗi bước, lấy 2 node có tần suất nhỏ nhất, tạo node cha mới:

text

Lần 1: Lấy D(1) và B(3) → tạo node DB(4)
  Heap: [C:3, DB:4, A:5]

Lần 2: Lấy C(3) và DB(4) → tạo node CDB(7)
  Heap: [A:5, CDB:7]

Lần 3: Lấy A(5) và CDB(7) → tạo gốc ACDB(12)
  Heap: [ACDB:12]  → Hoàn tất!

Bước 4 — Gán mã nhị phân:

Duyệt cây từ gốc, rẽ trái = 0, rẽ phải = 1. Mã tại mỗi lá là đường đi từ gốc:

text

            [12]
           /    \
        A(5)   [7]
        "0"   /    \
            C(3)  [4]
            "10"  /   \
                D(1)  B(3)
               "110" "111"

Bảng mã: A → 0 | C → 10 | D → 110 | B → 111

Triển khai polyglot

C++PythonJavaGo

cpp

#include <queue>
#include <unordered_map>
#include <string>
#include <vector>

struct HuffmanNode {
    char ch;
    int freq;
    HuffmanNode* left;
    HuffmanNode* right;

    HuffmanNode(char c, int f)
        : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct NodeCompare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

class HuffmanCoding {
public:
    HuffmanNode* root = nullptr;
    std::unordered_map<char, std::string> codes;

    void buildTree(const std::string& text) {
        // Bước 1: Đếm tần suất
        std::unordered_map<char, int> freq;
        for (char c : text) freq[c]++;

        // Bước 2: Khởi tạo min-heap
        std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>,
                            NodeCompare> pq;
        for (auto& [ch, f] : freq) {
            pq.push(new HuffmanNode(ch, f));
        }

        // Edge case: chỉ 1 loại ký tự
        if (pq.size() == 1) {
            auto node = pq.top(); pq.pop();
            root = new HuffmanNode('\0', node->freq);
            root->left = node;
            generateCodes(root, "");
            return;
        }

        // Bước 3: Gộp greedy
        while (pq.size() > 1) {
            auto left = pq.top(); pq.pop();
            auto right = pq.top(); pq.pop();
            auto merged = new HuffmanNode('\0', left->freq + right->freq);
            merged->left = left;
            merged->right = right;
            pq.push(merged);
        }
        root = pq.top();

        // Bước 4: Sinh mã
        generateCodes(root, "");
    }

    std::string encode(const std::string& text) {
        std::string result;
        result.reserve(text.size() * 4);
        for (char c : text) result += codes[c];
        return result;
    }

    std::string decode(const std::string& encoded) {
        std::string result;
        HuffmanNode* cur = root;
        for (char bit : encoded) {
            cur = (bit == '0') ? cur->left : cur->right;
            if (!cur->left && !cur->right) {
                result += cur->ch;
                cur = root;
            }
        }
        return result;
    }

private:
    void generateCodes(HuffmanNode* node, const std::string& code) {
        if (!node) return;
        if (!node->left && !node->right) {
            codes[node->ch] = code.empty() ? "0" : code;
            return;
        }
        generateCodes(node->left, code + "0");
        generateCodes(node->right, code + "1");
    }
};

python

import heapq
from collections import Counter
from dataclasses import dataclass, field
from typing import Optional


@dataclass(order=True)
class HuffmanNode:
    freq: int
    char: Optional[str] = field(compare=False, default=None)
    left: Optional['HuffmanNode'] = field(compare=False, default=None)
    right: Optional['HuffmanNode'] = field(compare=False, default=None)

    def is_leaf(self) -> bool:
        return self.left is None and self.right is None


class HuffmanCoding:
    def __init__(self):
        self.root: Optional[HuffmanNode] = None
        self.codes: dict[str, str] = {}

    def build_tree(self, text: str) -> None:
        """Xây cây Huffman từ chuỗi đầu vào."""
        freq = Counter(text)
        heap = [HuffmanNode(f, c) for c, f in freq.items()]
        heapq.heapify(heap)

        if len(heap) == 1:
            node = heapq.heappop(heap)
            self.root = HuffmanNode(node.freq, None, node, None)
            self._generate_codes(self.root, "")
            return

        while len(heap) > 1:
            left = heapq.heappop(heap)
            right = heapq.heappop(heap)
            merged = HuffmanNode(left.freq + right.freq,
                                 None, left, right)
            heapq.heappush(heap, merged)

        self.root = heap[0]
        self._generate_codes(self.root, "")

    def encode(self, text: str) -> str:
        return ''.join(self.codes[c] for c in text)

    def decode(self, encoded: str) -> str:
        result = []
        cur = self.root
        for bit in encoded:
            cur = cur.left if bit == '0' else cur.right
            if cur.is_leaf():
                result.append(cur.char)
                cur = self.root
        return ''.join(result)

    def _generate_codes(self, node: HuffmanNode, code: str) -> None:
        if node is None:
            return
        if node.is_leaf():
            self.codes[node.char] = code if code else "0"
            return
        self._generate_codes(node.left, code + "0")
        self._generate_codes(node.right, code + "1")

java

import java.util.*;

class HuffmanNode implements Comparable<HuffmanNode> {
    char ch;
    int freq;
    HuffmanNode left, right;

    HuffmanNode(char ch, int freq) {
        this.ch = ch;
        this.freq = freq;
    }

    boolean isLeaf() {
        return left == null && right == null;
    }

    @Override
    public int compareTo(HuffmanNode other) {
        return Integer.compare(this.freq, other.freq);
    }
}

public class HuffmanCoding {
    private HuffmanNode root;
    private Map<Character, String> codes = new HashMap<>();

    public void buildTree(String text) {
        // Bước 1: Đếm tần suất
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : text.toCharArray()) {
            freq.merge(c, 1, Integer::sum);
        }

        // Bước 2: Min-heap
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
        for (var entry : freq.entrySet()) {
            pq.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
        }

        if (pq.size() == 1) {
            HuffmanNode node = pq.poll();
            root = new HuffmanNode('\0', node.freq);
            root.left = node;
            generateCodes(root, "");
            return;
        }

        // Bước 3: Gộp greedy
        while (pq.size() > 1) {
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();
            HuffmanNode merged = new HuffmanNode('\0',
                left.freq + right.freq);
            merged.left = left;
            merged.right = right;
            pq.offer(merged);
        }
        root = pq.poll();
        generateCodes(root, "");
    }

    public String encode(String text) {
        StringBuilder sb = new StringBuilder();
        for (char c : text.toCharArray()) sb.append(codes.get(c));
        return sb.toString();
    }

    public String decode(String encoded) {
        StringBuilder sb = new StringBuilder();
        HuffmanNode cur = root;
        for (char bit : encoded.toCharArray()) {
            cur = (bit == '0') ? cur.left : cur.right;
            if (cur.isLeaf()) {
                sb.append(cur.ch);
                cur = root;
            }
        }
        return sb.toString();
    }

    private void generateCodes(HuffmanNode node, String code) {
        if (node == null) return;
        if (node.isLeaf()) {
            codes.put(node.ch, code.isEmpty() ? "0" : code);
            return;
        }
        generateCodes(node.left, code + "0");
        generateCodes(node.right, code + "1");
    }
}

package huffman

import "container/heap"

type HuffmanNode struct {
	Char  byte
	Freq  int
	Left  *HuffmanNode
	Right *HuffmanNode
}

func (n *HuffmanNode) IsLeaf() bool {
	return n.Left == nil && n.Right == nil
}

// Min-heap cho priority queue
type nodeHeap []*HuffmanNode

func (h nodeHeap) Len() int            { return len(h) }
func (h nodeHeap) Less(i, j int) bool  { return h[i].Freq < h[j].Freq }
func (h nodeHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *nodeHeap) Push(x interface{}) { *h = append(*h, x.(*HuffmanNode)) }
func (h *nodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

type HuffmanCoding struct {
	Root  *HuffmanNode
	Codes map[byte]string
}

func NewHuffmanCoding() *HuffmanCoding {
	return &HuffmanCoding{Codes: make(map[byte]string)}
}

func (hc *HuffmanCoding) BuildTree(text string) {
	freq := make(map[byte]int)
	for i := 0; i < len(text); i++ {
		freq[text[i]]++
	}

	h := &nodeHeap{}
	heap.Init(h)
	for ch, f := range freq {
		heap.Push(h, &HuffmanNode{Char: ch, Freq: f})
	}

	if h.Len() == 1 {
		node := heap.Pop(h).(*HuffmanNode)
		hc.Root = &HuffmanNode{Freq: node.Freq, Left: node}
		hc.generateCodes(hc.Root, "")
		return
	}

	for h.Len() > 1 {
		left := heap.Pop(h).(*HuffmanNode)
		right := heap.Pop(h).(*HuffmanNode)
		merged := &HuffmanNode{
			Freq: left.Freq + right.Freq,
			Left: left, Right: right,
		}
		heap.Push(h, merged)
	}
	hc.Root = heap.Pop(h).(*HuffmanNode)
	hc.generateCodes(hc.Root, "")
}

func (hc *HuffmanCoding) Encode(text string) string {
	result := ""
	for i := 0; i < len(text); i++ {
		result += hc.Codes[text[i]]
	}
	return result
}

func (hc *HuffmanCoding) Decode(encoded string) string {
	result := []byte{}
	cur := hc.Root
	for _, bit := range encoded {
		if bit == '0' {
			cur = cur.Left
		} else {
			cur = cur.Right
		}
		if cur.IsLeaf() {
			result = append(result, cur.Char)
			cur = hc.Root
		}
	}
	return string(result)
}

func (hc *HuffmanCoding) generateCodes(node *HuffmanNode, code string) {
	if node == nil {
		return
	}
	if node.IsLeaf() {
		if code == "" {
			code = "0"
		}
		hc.Codes[node.Char] = code
		return
	}
	hc.generateCodes(node.Left, code+"0")
	hc.generateCodes(node.Right, code+"1")
}

Tính chất Prefix-Free

Tính chất quan trọng nhất của Huffman code: không mã nào là tiền tố của mã khác. Đây là điều kiện cần và đủ để giải mã (decode) không mơ hồ — chỉ cần đọc tuần tự chuỗi bit từ trái sang phải.

Tính chất này được đảm bảo tự nhiên bởi cấu trúc cây nhị phân: mỗi ký tự chỉ nằm ở node lá. Nếu ký tự A có mã "0", không node lá nào khác có thể có mã bắt đầu bằng "0" — vì A đã chiếm node con trái của gốc, mọi mã khác đều đi qua nhánh phải ("1...").

Phân tích tỷ lệ nén

Tỷ lệ nén phụ thuộc vào entropy — mức độ bất đồng đều trong phân bố tần suất:

Phân bố tần suất	Tỷ lệ nén	Giải thích
Rất lệch (A: 90%, B: 10%)	Cao (~70-80%)	Ký tự phổ biến nhận mã rất ngắn
Tương đối lệch (thực tế)	Trung bình (~40-60%)	Phổ biến với text, log
Đồng đều (A: 25%, B: 25%...)	Gần 0%	Mã Huffman ≈ mã cố định

Thực chiến

Tình huống: Nén header HTTP/2 với HPACK

Bối cảnh: Hệ thống API gateway xử lý 50.000 request/giây. Mỗi HTTP request mang theo 10-20 header lặp lại (Authorization, Content-Type, Accept...). Trước HTTP/2, header truyền dạng text thuần — lãng phí bandwidth đáng kể.

Giải pháp: HTTP/2 sử dụng HPACK — thuật toán nén header kết hợp bảng tĩnh (61 header phổ biến được đánh index) và Huffman Coding cho giá trị header. Bảng mã Huffman trong HPACK là cố định (static Huffman table), được tính trước dựa trên thống kê tần suất byte trong header HTTP thực tế.

Python

python

# Minh họa logic nén kiểu HPACK (đơn giản hóa)
from collections import Counter


def analyze_header_compression(headers: list[tuple[str, str]]) -> dict:
    """Phân tích hiệu quả nén header HTTP dùng Huffman."""
    all_bytes = ''.join(f'{k}: {v}\r\n' for k, v in headers)
    original_bits = len(all_bytes) * 8

    freq = Counter(all_bytes)
    huffman = HuffmanCoding()
    huffman.build_tree(all_bytes)
    compressed_bits = sum(
        len(huffman.codes[c]) * count
        for c, count in freq.items()
    )

    return {
        'original_bytes': len(all_bytes),
        'original_bits': original_bits,
        'compressed_bits': compressed_bits,
        'ratio': f"{(1 - compressed_bits / original_bits) * 100:.1f}%",
        'avg_bits_per_byte': f"{compressed_bits / len(all_bytes):.2f}",
    }


# Ví dụ: 5 request điển hình với header lặp lại
sample_headers = [
    ('Content-Type', 'application/json'),
    ('Authorization', 'Bearer eyJhbGciOiJSUzI1NiIsInR5cCI6IkpXVCJ9'),
    ('Accept', 'application/json'),
    ('X-Request-ID', 'a1b2c3d4-e5f6-7890'),
    ('Cache-Control', 'no-cache'),
]

result = analyze_header_compression(sample_headers)
# Kết quả: tỷ lệ nén ~35-45% chỉ riêng Huffman,
# kết hợp bảng tĩnh HPACK → nén tổng thể ~60-85%

Phân tích:

HPACK kết hợp hai kỹ thuật: indexing (tra bảng) giảm header lặp lại xuống 1 byte, Huffman nén phần giá trị còn lại
Bảng Huffman tĩnh trong HPACK được tính trước — không cần truyền cây cùng dữ liệu, tiết kiệm overhead
Trong production, header HTTP có phân bố byte rất lệch (nhiều chữ cái thường, ít ký tự đặc biệt) → Huffman đặc biệt hiệu quả

Tình huống: Nén file log hệ thống

Bối cảnh: Hệ thống microservice sinh 2GB log mỗi ngày. Log có tính lặp cao (timestamp format, log level, service name). Cần nén trước khi lưu S3 để giảm chi phí storage.

python

import os

def compress_log_file(input_path: str, output_path: str) -> dict:
    """Nén file log sử dụng Huffman coding."""
    with open(input_path, 'r', encoding='utf-8') as f:
        text = f.read()

    huffman = HuffmanCoding()
    huffman.build_tree(text)
    encoded = huffman.encode(text)

    # Đệm để đủ bội số 8 bit
    padding = (8 - len(encoded) % 8) % 8
    encoded_padded = encoded + '0' * padding

    # Chuyển chuỗi bit thành byte
    byte_array = bytearray()
    for i in range(0, len(encoded_padded), 8):
        byte_array.append(int(encoded_padded[i:i+8], 2))

    with open(output_path, 'wb') as f:
        f.write(bytes([padding]))
        f.write(byte_array)

    original_size = os.path.getsize(input_path)
    compressed_size = os.path.getsize(output_path)

    return {
        'original_kb': original_size / 1024,
        'compressed_kb': compressed_size / 1024,
        'ratio': f"{(1 - compressed_size / original_size) * 100:.1f}%",
    }

Sai lầm điển hình

❌ Sai lầm 1: Không xử lý trường hợp chuỗi chỉ có 1 loại ký tự

Vấn đề: Chuỗi "AAAA" chỉ có 1 ký tự duy nhất, heap chỉ còn 1 node → vòng lặp gộp không chạy, cây không được xây.

python

# SAI: Không xử lý edge case
def build_tree_broken(text):
    freq = Counter(text)
    heap = [HuffmanNode(f, c) for c, f in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:  # Không chạy khi len == 1
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        # ...
    return heap[0]  # Node lá, không có mã nào được gán

Tại sao sai: Trong production, log file hoặc dữ liệu sensor thường có giai đoạn lặp duy nhất một giá trị (ví dụ: chuỗi heartbeat "0000...0000"). Nếu không xử lý, encode() sẽ crash vì codes dictionary rỗng.

python

# ĐÚNG: Tạo node gốc giả khi chỉ có 1 loại ký tự
if len(heap) == 1:
    node = heapq.heappop(heap)
    root = HuffmanNode(node.freq, None, node, None)
    # Node lá nhận mã "0"

❌ Sai lầm 2: Dùng mã Huffman không prefix-free

Vấn đề: Tự thiết kế bảng mã "tối ưu" bằng tay thay vì xây cây Huffman, vô tình tạo mã không prefix-free.

text

# SAI: Mã không prefix-free
A = 0
B = 01    ← "0" là prefix của "01"!
C = 10
D = 11

Chuỗi bit "010" → "AB"? hay "ACA"? → Mơ hồ, không giải mã được!

Tại sao sai: Đây là lỗi phổ biến khi kỹ sư cố gắng "tối ưu bằng tay" thay vì tin tưởng thuật toán. Huffman Coding tự động đảm bảo prefix-free nhờ cấu trúc cây — mỗi ký tự luôn nằm ở node lá.

text

# ĐÚNG: Mã prefix-free (tạo bởi cây Huffman)
A = 0
B = 111
C = 10
D = 110

Chuỗi bit "010" → A(0) + C(10) → "AC" — giải mã duy nhất, không mơ hồ.

❌ Sai lầm 3: Quên truyền bảng mã khi lưu file nén

Vấn đề: Nén file và lưu chuỗi bit, nhưng không lưu cây Huffman hoặc bảng mã cùng file.

python

# SAI: Chỉ lưu dữ liệu nén, quên metadata
with open('compressed.bin', 'wb') as f:
    f.write(compressed_bytes)  # Không có cách nào giải mã!

Tại sao sai: Mỗi file có phân bố tần suất khác nhau → cây Huffman khác nhau. Không có cây hoặc bảng mã, file nén trở thành dữ liệu vô nghĩa. Định dạng thực tế (ZIP, GZIP) luôn lưu metadata nén trong header file.

python

# ĐÚNG: Lưu cả bảng mã (hoặc tần suất để rebuild cây)
import json

metadata = {
    'padding': padding,
    'freq': dict(Counter(text)),  # Đủ để rebuild cây khi giải mã
}
with open('compressed.bin', 'wb') as f:
    meta_bytes = json.dumps(metadata).encode('utf-8')
    f.write(len(meta_bytes).to_bytes(4, 'big'))
    f.write(meta_bytes)
    f.write(compressed_bytes)

Under the Hood

Phân tích độ phức tạp

Thao tác	Time	Space	Ghi chú
Đếm tần suất	O(n)	O(k)	n = độ dài chuỗi, k = số ký tự phân biệt
Xây min-heap	O(k)	O(k)	heapify từ mảng k phần tử
Xây cây Huffman	O(k log k)	O(k)	k-1 lần gộp, mỗi lần O(log k)
Sinh bảng mã	O(k)	O(k)	Duyệt cây k node lá
Mã hóa (encode)	O(n)	O(n)	Tra bảng O(1) cho mỗi ký tự
Giải mã (decode)	O(n)	O(n)	Duyệt cây cho mỗi bit, trung bình O(1) per symbol

Tổng: Xây dựng O(n + k log k), mã hóa/giải mã O(n). Với k << n (thường k ≤ 256 cho ASCII), chi phí xây cây là không đáng kể.

Chứng minh tính tối ưu (Greedy Proof)

Định lý: Huffman Coding tạo mã prefix-free có tổng chiều dài mã hóa tối thiểu cho mô hình mã hóa symbol-by-symbol.

Chứng minh bằng phản chứng (exchange argument):

Giả sử tồn tại cây tối ưu T* mà hai ký tự tần suất nhỏ nhất (x, y) không là anh em ở mức sâu nhất
Gọi a, b là hai node lá anh em ở mức sâu nhất trong T*
Hoán đổi x với a (nếu x ≠ a): Vì freq(x) ≤ freq(a) và depth(x_mới) ≥ depth(x_cũ), tổng cost không tăng
Tương tự hoán đổi y với b
Kết quả: T** có cost ≤ T* và x, y là anh em ở mức sâu nhất
Vậy gộp x, y trước (quyết định greedy) là an toàn → quy nạp cho bài toán con

Huffman so với các thuật toán nén khác

Thuật toán	Loại	Ưu điểm	Nhược điểm	Ứng dụng
Huffman	Lossless, thống kê	Đơn giản, chứng minh tối ưu	Chỉ tối ưu symbol-by-symbol	DEFLATE, JPEG
Arithmetic Coding	Lossless, thống kê	Tối ưu hơn Huffman ~5-10%	Phức tạp, bằng sáng chế (lịch sử)	H.264, JPEG 2000
LZ77/LZ78	Lossless, từ điển	Phát hiện chuỗi lặp dài	Cần bộ nhớ cho sliding window	GZIP, PNG
LZW	Lossless, từ điển	Xây từ điển online	Kém hiệu quả trên dữ liệu ngẫu nhiên	GIF

Thực tế: Hầu hết hệ thống nén hiện đại (DEFLATE trong ZIP/GZIP, Brotli) kết hợp LZ77 (nén từ điển) với Huffman (nén thống kê) để đạt hiệu quả cao nhất. Huffman đơn lẻ hiếm khi dùng trong production — nhưng hiểu Huffman là nền tảng để hiểu toàn bộ pipeline nén.

Khi nào KHÔNG nên dùng Huffman

Dữ liệu phân bố đồng đều (entropy cao): mã Huffman xấp xỉ mã cố định, không lợi ích
Dữ liệu rất nhỏ (< 1KB): overhead lưu bảng mã/cây có thể lớn hơn phần tiết kiệm
Cần nén adaptive (streaming): Huffman tĩnh yêu cầu 2 pass (đếm tần suất + mã hóa). Xem xét Adaptive Huffman hoặc Arithmetic Coding
Cần tỷ lệ nén tối đa: Arithmetic Coding cho kết quả tốt hơn ~5-10%

Checklist ghi nhớ

✅ Checklist triển khai

Xây dựng cây Huffman

[ ] Đếm tần suất mỗi ký tự → tạo node lá
[ ] Đưa tất cả node lá vào min-heap (priority queue)
[ ] Lặp: lấy 2 node nhỏ nhất → gộp thành node cha → đưa lại heap
[ ] Dừng khi heap còn 1 node (gốc cây)
[ ] Xử lý edge case: chuỗi chỉ có 1 loại ký tự

Mã hóa & Giải mã

[ ] Gán mã: duyệt cây từ gốc, trái = 0, phải = 1
[ ] Mã hóa: tra bảng O(1) cho mỗi ký tự
[ ] Giải mã: duyệt cây theo chuỗi bit, reset về gốc khi đến lá
[ ] Lưu file: bao gồm bảng mã/tần suất + padding info trong header

Tính chất quan trọng

[ ] Prefix-free: không mã nào là tiền tố của mã khác → giải mã không mơ hồ
[ ] Greedy-choice property: gộp 2 node nhỏ nhất trước là an toàn (chứng minh bằng exchange argument)
[ ] Tối ưu: minimizes tổng chiều dài mã hóa cho mô hình symbol-by-symbol
[ ] Lossless: giải mã chính xác dữ liệu gốc, không mất thông tin

Ứng dụng thực tế

[ ] DEFLATE (ZIP, GZIP): Huffman + LZ77
[ ] HTTP/2 HPACK: bảng Huffman tĩnh cho header compression
[ ] JPEG: Huffman mã hóa hệ số DCT sau quantization

Bài tập luyện tập

Bài 1: Xây cây Huffman thủ công — Foundation

Đề bài: Cho chuỗi "ABRACADABRA". Hãy:

Tính bảng tần suất
Xây cây Huffman (vẽ từng bước gộp)
Xác định bảng mã
Tính tổng số bit sau khi mã hóa và tỷ lệ nén so với mã ASCII 8-bit

🧠 Quiz

Câu hỏi: Chuỗi "ABRACADABRA" có bao nhiêu ký tự phân biệt?

[ ] A. 3
[ ] B. 4
[x] C. 5
[ ] D. 6 Giải thích: A(5), B(2), R(2), C(1), D(1) → 5 ký tự phân biệt. A xuất hiện nhiều nhất nên sẽ nhận mã ngắn nhất.

💡 Gợi ý

Tần suất: A=5, B=2, R=2, C=1, D=1
Bắt đầu gộp từ hai node nhỏ nhất: C(1) và D(1)
Tiếp tục gộp cho đến khi còn 1 gốc

✅ Lời giải

text

Tần suất: A:5, B:2, R:2, C:1, D:1   Tổng: 11 ký tự

Bước 1: Gộp C(1) + D(1) → CD(2)
  Heap: [B:2, R:2, CD:2, A:5]

Bước 2: Gộp B(2) + R(2) → BR(4)
  Heap: [CD:2, A:5, BR:4]

Bước 3: Gộp CD(2) + BR(4) → CDBR(6)
  Heap: [A:5, CDBR:6]

Bước 4: Gộp A(5) + CDBR(6) → Root(11)

Cây:
          [11]
         /    \
       A(5)   [6]
       "0"   /    \
           [2]   [4]
          / \    / \
        C(1) D(1) B(2) R(2)
       "100" "101" "110" "111"

Mã: A=0, C=100, D=101, B=110, R=111

Tổng bit: 5×1 + 1×3 + 1×3 + 2×3 + 2×3 = 5 + 3 + 3 + 6 + 6 = 23 bit
ASCII 8-bit: 11 × 8 = 88 bit
Tỷ lệ nén: (1 - 23/88) × 100 ≈ 73.9%

Bài 2: Kiểm chứng tính Prefix-Free — Intermediate

Đề bài: Viết hàm kiểm tra xem một bảng mã có phải prefix-free hay không. Trả về True nếu prefix-free, False kèm cặp vi phạm nếu không.

🧠 Quiz

Câu hỏi: Bảng mã {A: "0", B: "10", C: "110", D: "11"} có prefix-free không?

[ ] A. Có, vì không mã nào giống nhau
[x] B. Không, vì "11" (D) là prefix của "110" (C)
[ ] C. Có, vì mỗi mã có độ dài khác nhau
[ ] D. Không thể xác định Giải thích: D="11" là tiền tố của C="110". Khi đọc chuỗi bit "110", không biết đó là D+"0..." hay C. Bảng mã Huffman hợp lệ không bao giờ xảy ra trường hợp này vì mỗi ký tự nằm ở node lá.

✅ Lời giải

python

def verify_prefix_free(codes: dict[str, str]) -> tuple[bool, str]:
    """Kiểm tra bảng mã có prefix-free không."""
    sorted_codes = sorted(codes.items(), key=lambda x: len(x[1]))

    for i, (char_i, code_i) in enumerate(sorted_codes):
        for char_j, code_j in sorted_codes[i + 1:]:
            if code_j.startswith(code_i):
                return False, f"'{char_i}'={code_i} là prefix của '{char_j}'={code_j}"

    return True, "Bảng mã hợp lệ (prefix-free)"


# Test
print(verify_prefix_free({'A': '0', 'B': '10', 'C': '110', 'D': '111'}))
# (True, "Bảng mã hợp lệ (prefix-free)")

print(verify_prefix_free({'A': '0', 'B': '10', 'C': '110', 'D': '11'}))
# (False, "'D'=11 là prefix của 'C'=110")

Phân tích: Time O(k² × L) với k = số mã, L = chiều dài mã tối đa. Space O(k). Có thể tối ưu xuống O(k × L) bằng Trie.

Bài 3: Huffman Coding cho file nén — Advanced

Đề bài: Triển khai chương trình nén/giải nén file hoàn chỉnh:

Đọc file text, xây cây Huffman, mã hóa
Lưu file nén kèm metadata (tần suất, padding) vào header
Giải nén: đọc metadata, rebuild cây, giải mã
Kiểm chứng: file giải nén phải giống hệt file gốc

💡 Gợi ý

Lưu metadata dạng JSON ở đầu file nén
Dùng 4 byte đầu lưu kích thước metadata
Padding cuối chuỗi bit để đủ bội số 8

✅ Lời giải

python

import json
import os
from collections import Counter


def compress_file(input_path: str, output_path: str) -> dict:
    with open(input_path, 'r', encoding='utf-8') as f:
        text = f.read()

    if not text:
        raise ValueError("File rỗng, không có gì để nén")

    huffman = HuffmanCoding()
    huffman.build_tree(text)
    encoded = huffman.encode(text)

    padding = (8 - len(encoded) % 8) % 8
    encoded_padded = encoded + '0' * padding

    byte_array = bytearray()
    for i in range(0, len(encoded_padded), 8):
        byte_array.append(int(encoded_padded[i:i + 8], 2))

    metadata = {
        'padding': padding,
        'freq': dict(Counter(text)),
    }
    meta_bytes = json.dumps(metadata, ensure_ascii=False).encode('utf-8')

    with open(output_path, 'wb') as f:
        f.write(len(meta_bytes).to_bytes(4, 'big'))
        f.write(meta_bytes)
        f.write(byte_array)

    return {
        'original': os.path.getsize(input_path),
        'compressed': os.path.getsize(output_path),
    }


def decompress_file(input_path: str, output_path: str) -> None:
    with open(input_path, 'rb') as f:
        meta_size = int.from_bytes(f.read(4), 'big')
        metadata = json.loads(f.read(meta_size).decode('utf-8'))
        compressed_bytes = f.read()

    bits = ''.join(f'{byte:08b}' for byte in compressed_bytes)
    if metadata['padding'] > 0:
        bits = bits[:-metadata['padding']]

    # Rebuild cây từ tần suất
    text_for_tree = ''.join(
        c * int(freq) for c, freq in metadata['freq'].items()
    )
    huffman = HuffmanCoding()
    huffman.build_tree(text_for_tree)
    decoded = huffman.decode(bits)

    with open(output_path, 'w', encoding='utf-8') as f:
        f.write(decoded)

Phân tích: Nén O(n + k log k), giải nén O(n + k log k). Overhead metadata ~vài trăm byte, không đáng kể cho file > 1KB.

Liên kết học tiếp

Từ khóa glossary: Huffman Coding, Greedy Algorithm, Prefix-Free Code, Lossless Compression, Priority Queue, Binary Tree, DEFLATE, HPACK

Tìm kiếm liên quan: nén dữ liệu, mã hóa Huffman, thuật toán tham lam, cây nhị phân, nén file ZIP

Huffman Coding — Nén dữ liệu với chiến lược Greedy ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Quy trình xây dựng cây Huffman ​

Triển khai polyglot ​

Tính chất Prefix-Free ​

Phân tích tỷ lệ nén ​

Thực chiến ​

Tình huống: Nén header HTTP/2 với HPACK ​

Tình huống: Nén file log hệ thống ​

Sai lầm điển hình ​

❌ Sai lầm 1: Không xử lý trường hợp chuỗi chỉ có 1 loại ký tự ​

❌ Sai lầm 2: Dùng mã Huffman không prefix-free ​

❌ Sai lầm 3: Quên truyền bảng mã khi lưu file nén ​

Under the Hood ​

Phân tích độ phức tạp ​

Chứng minh tính tối ưu (Greedy Proof) ​

Huffman so với các thuật toán nén khác ​

Khi nào KHÔNG nên dùng Huffman ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Xây cây Huffman thủ công — Foundation ​

Bài 2: Kiểm chứng tính Prefix-Free — Intermediate ​

Bài 3: Huffman Coding cho file nén — Advanced ​

Liên kết học tiếp ​

Huffman Coding — Nén dữ liệu với chiến lược Greedy

Bức tranh tư duy

Cốt lõi kỹ thuật

Quy trình xây dựng cây Huffman

Triển khai polyglot

Tính chất Prefix-Free

Phân tích tỷ lệ nén

Thực chiến

Tình huống: Nén header HTTP/2 với HPACK

Tình huống: Nén file log hệ thống

Sai lầm điển hình

❌ Sai lầm 1: Không xử lý trường hợp chuỗi chỉ có 1 loại ký tự

❌ Sai lầm 2: Dùng mã Huffman không prefix-free

❌ Sai lầm 3: Quên truyền bảng mã khi lưu file nén

Under the Hood

Phân tích độ phức tạp

Chứng minh tính tối ưu (Greedy Proof)

Huffman so với các thuật toán nén khác

Khi nào KHÔNG nên dùng Huffman

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Xây cây Huffman thủ công — Foundation

Bài 2: Kiểm chứng tính Prefix-Free — Intermediate

Bài 3: Huffman Coding cho file nén — Advanced

Liên kết học tiếp