霍夫曼編碼原理與 C++ 完整實作：從頻率統計到最優前綴碼構建

霍夫曼編碼核心概念

• 無損壓縮：根據字元出現頻率分配變長編碼
• 最優前綴碼：高頻字元編碼短、低頻字元編碼長，無編碼是其他編碼前綴，解碼唯一
• 空間節省：典型文本可壓縮 20%~90%，視資料分布而定
• 先驗知識：需先掃描全文統計頻率 (雙掃描或儲存頻率表)

演算法流程

1. 統計各字元頻率，建立葉節點 (權重 = 頻率)
2. 所有節點加入最小優先佇列 (Min-Heap)
3. 重複直到佇列剩一個節點：
   • 取出權重最小的兩個節點
   • 建立父節點，權重 = 兩子節點權重之和
   • 父節點加入佇列
4. 剩餘節點為霍夫曼樹根
5. 編碼規則：左邊 0、右邊 1，從根到葉的路徑即字元編碼

核心資料結構

struct Node {
    UINT key;          // 字元值
    UINT frequency;    // 權重
    Node *_left, *_right;
    Node(): key(EMPTY), frequency(0), _left(NULL), _right(NULL) {}
};
typedef Node* PNode;

class PriorityQueue {
    PNode table[256];  // 固定 256 字元集
    UINT heapSize;
    // Min-Heap 操作: build, insert, extractMin, minHeapify, swap
};

關鍵實作細節

頻率統計與建堆

PriorityQueue::PriorityQueue(char *data, int len) {
    for (int i = 0; i < len; ++i) {
        bool found = false;
        for (int j = 0; j < heapSize; ++j)
            if (table[j]->key == data[i]) {
                table[j]->frequency++;
                found = true; break;
            }
        if (!found) {
            table[heapSize]->key = data[i];
            table[heapSize]->frequency = 1;
            heapSize++;
        }
    }
    heapSize--;
    buildMinHeap(heapSize);
}

霍夫曼樹構建

PNode BuildHuffmanTree(PriorityQueue &q) {
    PNode parent, left, right;
    while (q.heapSize != EMPTY) {
        left = new Node; right = new Node; parent = new Node;
        copyNode(q.extractMin(), left);
        copyNode(q.extractMin(), right);
        parent->frequency = left->frequency + right->frequency;
        parent->_left = left; parent->_right = right;
        if (q.heapSize == EMPTY) break;
        q.insert(parent);
    }
    return parent;
}

編碼輸出 (遞歸遍歷)

void showCode(PNode root, vector &code) {
    if (!root) return;
    if (!root->_left && !root->_right) {  // 葉節點
        cout << (char)root->key << " code: ";
        for (char bit : code) cout << (int)bit;
        cout << endl;
        return;
    }
    code.push_back(0); showCode(root->_left, code);
    code.back() = 1; showCode(root->_right, code);
    code.pop_back();
}

測試結果範例

輸入："xxznxznnvvccncvzzbzzvxxczbzvmnzvnnz"

霍夫曼編碼雖最優，但錯誤傳播性強：1 bit 錯誤導致後續解碼全錯。實務常配合同步標記或分塊獨立編碼緩解。