Thuật toán Huffman Coding (Mã hóa Huffman)

Huffman coding là thuật toán nén dữ liệu không mất thông tin (lossless). Gán mã độ dài biến thiên cho các ký tự: ký tự xuất hiện nhiều nhất có mã ngắn nhất, ký tự hiếm có mã dài hơn.

Hai phần chính: xây cây Huffman, và duyệt cây để tìm mã.

Ví dụ: chuỗi "YYYZXXYYX", tần suất Y > X > Z. Do đó mã Y ngắn hơn X, X ngắn hơn Z.

Độ phức tạp gán mã: O(n log n)

Input và Output

Input: Chuỗi "ACCEBFFFFAAXXBLKE"
Output: Mã cho các ký tự:
Data: K, Frequency: 1, Code: 0000
Data: L, Frequency: 1, Code: 0001
Data: E, Frequency: 2, Code: 001
Data: F, Frequency: 4, Code: 01
Data: B, Frequency: 2, Code: 100
Data: C, Frequency: 2, Code: 101
Data: X, Frequency: 2, Code: 110
Data: A, Frequency: 3, Code: 111

Thuật toán

huffmanCoding(string)

Begin
  định nghĩa node: ký tự, tần suất, con trái, con phải
  tạo list 'freq' lưu tần suất, khởi tạo 0
  for mỗi ký tự c trong string do tăng freq[c] done
  for tất cả ký tự ch có freq > 0 do
    thêm node (ch, freq) vào priority queue Q
  done
  while Q không rỗng do
    lấy item từ Q gán cho con trái node
    lấy item từ Q gán cho con phải node
    duyệt node để tìm mã gán
  done
End

traverseNode(node, code)

if leftChild(node) ≠ ∅ then traverseNode(leftChild, code+'0')
if rightChild(node) ≠ ∅ then traverseNode(rightChild, code+'1')
else hiển thị ký tự và mã của node hiện tại

Ví dụ (C++)

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct node {
    int freq; char data;
    const node *child0, *child1;
    node(char d, int f = -1) : data(d), freq(f), child0(NULL), child1(NULL) {}
    node(const node *c0, const node *c1) : data(0), freq(c0->freq + c1->freq), child0(c0), child1(c1) {}
    bool operator<(const node &a) const { return freq > a.freq; } // min-heap
    void traverse(string code = "") const {
        if(child0) { child0->traverse(code + '0'); child1->traverse(code + '1'); }
        else { cout << "Data: " << data << ", Frequency: " << freq << ", Code: " << code << endl; }
    }
};

int main() {
    string str = "ACCEBFFFFAAXXBLKE";
    int freq[256] = {0};
    for(char c : str) freq[(int)c]++;
    priority_queue<node> q;
    for(int i = 0; i < 256; i++)
        if(freq[i]) q.push(node((char)i, freq[i]));
    while(q.size() > 1) {
        node *c0 = new node(q.top()); q.pop();
        node *c1 = new node(q.top()); q.pop();
        q.push(node(c0, c1));
    }
    cout << "Huffman Codes:" << endl;
    q.top().traverse();
}

Kết quả

Data: K, Frequency: 1, Code: 0000
Data: L, Frequency: 1, Code: 0001
Data: E, Frequency: 2, Code: 001
Data: F, Frequency: 4, Code: 01
Data: B, Frequency: 2, Code: 100
Data: C, Frequency: 2, Code: 101
Data: X, Frequency: 2, Code: 110
Data: A, Frequency: 3, Code: 111

Đặc điểm: Huffman code là prefix code (không mã nào là tiền tố của mã khác) → giải mã duy nhất. Dùng priority queue (min-heap) để luôn lấy 2 node tần suất nhỏ nhất. Ứng dụng: nén file (ZIP, JPEG, MP3, PNG).