數據壓縮核心算法：Huffman編碼原理與C++完整實現

Huffman算法是經典的無損壓縮算法。與LZW不同，它需要先驗知識——字符出現概率。通過統計頻率，為高頻字符分配短編碼、低頻字符分配長編碼，實現20%~90%壓縮率（視數據特性而定）。Huffman編碼屬變長編碼，且是最優前綴碼（無編碼是其他編碼前綴），保證解碼唯一性。

算法流程

1. 統計字符頻率，建立葉子節點（權重=頻率）
2. 所有節點入最小優先隊列（小頂堆）
3. 反覆取出權重最小的兩個節點
4. 創建父節點，權重=兩子節點權重之和，左右掛接兩子節點
5. 父節點重入優先隊列
6. 隊列剩單一節點時結束，該節點為Huffman樹根

編碼規則

• 從根節點出發：左枝=0，右枝=1
• 遍歷至葉子節點的路徑即該字符編碼
• 前綴碼特性保證解碼無歧義，但錯誤會傳播（1位錯誤導致後續全錯）

C++完整實現（三文件結構）

1. 主程序 main.cpp

#include 
#include 
#include "compress.h"
using namespace std;

void ShowCode(PNode root, vector &code);

int main() {
    char A[] = "xxznxznnvvccncvzzbzzvxxczbzvmnzvnnz";
    UINT Length = sizeof(A) - 1;
    Priority_Q queue(A, Length);  // 建立優先隊列

    // 輸出頻率統計
    for (UINT i = 0; i <= queue.Heap_Size; i++)
        cout << (char)(queue.table[i]->key) << " Frequency: " << queue.table[i]->Frequency << endl;
    cout << "--------------------" << endl;

    PNode root = Build_Huffman_Tree(queue);  // 構建Huffman樹
    vector code;
    ShowCode(root, code);  // 遞歸輸出編碼
    return 0;
}

void ShowCode(PNode root, vector &code) {
    if (root) {
        if (!root->_left && !root->_right) {  // 葉子節點
            cout << (char)(root->key) << " code : ";
            for (UINT i = 0; i < code.size(); i++) cout << (int)code[i];
            cout << endl;
            return;
        }
        code.push_back(0);
        ShowCode(root->_left, code);
        code[code.size()-1] = 1;
        ShowCode(root->_right, code);
        code.resize(code.size()-1);
    }
}

2. 核心邏輯 compress.cpp

包含：
• Priority_Q構造函數：統計頻率、建最小堆
• Build_Min_Heap/Min_Heapify/Swap：堆操作
• Extract_Min/Insert：隊列出入隊
• Build_Huffman_Tree：核心樹構建邏輯（循環取兩最小、合併、重入）
• CopyNode：節點深拷貝

3. 頭文件 compress.h

#ifndef COMPRESS
#define COMPRESS
#include 
#define UINT unsigned int
#define EMPTY 0xFFFFFFFF
#define Parent(i) (UINT)(((i)-1)/2)

typedef struct Node {
    UINT key; UINT Frequency;
    struct Node *_left, *_right;
    Node():key(EMPTY),Frequency(0),_left(NULL),_right(NULL){}
} Node, *PNode;

class Priority_Q {
public:
    Priority_Q(char *A, int Length);
    void Insert(PNode pnode);
    PNode Extract_Min();
    UINT Heap_Size;
    PNode table[256];
private:
    void Build_Min_Heap(UINT Length);
    void Swap(int x, int y);
    void Min_Heapify(UINT i);
};

PNode Build_Huffman_Tree(Priority_Q &queue);
#endif

運行示例輸出

程序輸出各字符頻率及對應Huffman編碼（見原文圖片），驗證高頻字符編碼更短。

參考資料

百度文檔參考資料

總結

本文完整呈現Huffman算法從原理到工程級C++實現，涵蓋優先隊列（堆）、樹構建、遞歸編碼遍歷等核心技術，是理解無損壓縮與貪心算法的優秀案例。