哈夫曼樹簡介與編碼實例

哈夫曼樹簡介

哈夫曼樹（Huffman Tree）是一種帶權路徑長度最短的二叉樹，由David A. Huffman于1952年提出，廣泛應用于數據壓縮領域。

基本概念

1. 路徑長度：從根節點到某節點的路徑上的邊數
2. 節點的帶權路徑長度：節點權值 × 路徑長度
3. 樹的帶權路徑長度(WPL)：所有葉子節點的帶權路徑長度之和

構建原則

• 頻率高的字符使用短編碼
• 頻率低的字符使用長編碼
• 任一字符的編碼都不是其他字符編碼的前綴（前綴編碼性質）

構建步驟

1. 將每個數據看作一個單獨的樹，組成森林
2. 選擇權值最小的兩棵樹合并，新樹根節點權值為子樹權值之和
3. 重復步驟2，直到只剩一棵樹

給定數據的哈夫曼編碼

給定頻率數組：vector<int> frequent = {5, 9, 12, 13, 45, 16}

步驟1：構建哈夫曼樹

構建過程：

1. 排序：[5,9,12,13,16,45]
2. 合并5和9 → 新節點14
3. 合并12和13 → 新節點25
4. 合并14和16 → 新節點30
5. 合并25和30 → 新節點55
6. 合并45和55 → 根節點100

步驟2：分配編碼

從根節點開始，向左為0，向右為1：

哈夫曼編碼的特點

1. 最優前綴編碼：沒有任何編碼是其他編碼的前綴
2. 貪心算法應用：每次合并兩個頻率最小的節點
3. 壓縮效率：對于非均勻分布數據壓縮效果顯著
4. 唯一性：相同頻率可能產生不同結構的樹，但WPL相同

此哈夫曼樹編碼可以有效地壓縮原始數據，高頻數據(如45)獲得了最短的編碼(0)，而低頻數據(如5)獲得了較長的編碼(111)。

代碼實現（C++實現）

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <unordered_map>
#include <iomanip>
using namespace std;

struct Node {
    int value;    // 存儲原始值（葉子節點）
    int freq;     // 存儲頻率
    Node* left;
    Node* right;
    
    // 葉子節點構造函數
    Node(int v, int f) : value(v), freq(f), left(nullptr), right(nullptr) {}
    
    // 內部節點構造函數
    Node(int f, Node* l, Node* r) : value(-1), freq(f), left(l), right(r) {}
};

// 自定義比較函數（小頂堆）
struct CompareNode {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq; // 注意：大于號實現小頂堆
    }
};

// 打印樹結構
void printTree(Node* node, int depth = 0) {
    if (!node) return;
    
    string indent(depth * 2, ' ');
    if (node->value != -1) {
        cout << indent << "Leaf: " << setw(2) << node->value 
             << " (freq: " << setw(2) << node->freq << ")" << endl;
    } else {
        cout << indent << "Node: " << setw(2) << node->freq << endl;
    }
    
    printTree(node->left, depth + 1);
    printTree(node->right, depth + 1);
}

// 生成哈夫曼編碼
void generateCodes(Node* root, string code, unordered_map<int, string>& codes) {
    if (!root) return;
    
    if (root->value != -1) { // 葉子節點
        codes[root->value] = code;
        return;
    }
    
    generateCodes(root->left, code + "0", codes);
    generateCodes(root->right, code + "1", codes);
}

// 計算帶權路徑長度(WPL)
int calculateWPL(Node* root, int depth = 0) {
    if (!root) return 0;
    
    if (root->value != -1) { // 葉子節點
        return root->freq * depth;
    }
    
    return calculateWPL(root->left, depth + 1) + 
           calculateWPL(root->right, depth + 1);
}

// 釋放樹內存
void deleteTree(Node* root) {
    if (!root) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

// 哈夫曼樹構建與編碼
void buildHuffmanTree(vector<int> freqs) {
    // 使用小頂堆優先隊列
    priority_queue<Node*, vector<Node*>, CompareNode> minHeap;
    
    // 創建葉子節點
    for (int f : freqs) {
        minHeap.push(new Node(f, f)); // 存儲原始值
    }
    
    // 構建哈夫曼樹
    while (minHeap.size() > 1) {
        Node* left = minHeap.top();
        minHeap.pop();
        
        Node* right = minHeap.top();
        minHeap.pop();
        
        Node* parent = new Node(left->freq + right->freq, left, right);
        minHeap.push(parent);
    }
    
    Node* root = minHeap.top();
    
    // 打印樹結構
    cout << "哈夫曼樹結構:" << endl;
    printTree(root);
    cout << endl;
    
    // 生成哈夫曼編碼
    unordered_map<int, string> huffmanCodes;
    generateCodes(root, "", huffmanCodes);
    
    // 計算WPL
    int wpl = calculateWPL(root);
    
    // 輸出結果
    cout << "哈夫曼編碼表:" << endl;
    cout << "┌───────┬───────┬──────────────┐" << endl;
    cout << "│ 值    │ 頻率  │ 編碼         │" << endl;
    cout << "├───────┼───────┼──────────────┤" << endl;
    
    for (auto& pair : huffmanCodes) {
        cout << "│ " << setw(5) << pair.first << " │ " 
             << setw(5) << pair.first << " │ "
             << setw(12) << pair.second << " │" << endl;
    }
    cout << "└───────┴───────┴──────────────┘" << endl;
    
    cout << "\n帶權路徑長度(WPL): " << wpl << endl;
    cout << "壓縮效率: " << fixed << setprecision(2) 
         << (static_cast<double>(wpl) / (root->freq * 8)) * 100 
         << "% (相比8位固定編碼)" << endl;
    
    // 釋放內存
    deleteTree(root);
}

int main() {
    vector<int> frequent = {5, 9, 12, 13, 16, 45};
    
    cout << "原始數據頻率:" << endl;
    cout << "┌───────┬───────┐" << endl;
    cout << "│ 值    │ 頻率  │" << endl;
    cout << "├───────┼───────┤" << endl;
    for (int f : frequent) {
        cout << "│ " << setw(5) << f << " │ " 
             << setw(5) << f << " │" << endl;
    }
    cout << "└───────┴───────┘" << endl << endl;
    
    buildHuffmanTree(frequent);
    return 0;
}

運行結果

原始數據頻率:
┌───────┬───────┐
│ 值    │ 頻率  │
├───────┼───────┤
│     5 │     5 │
│     9 │     9 │
│    12 │    12 │
│    13 │    13 │
│    16 │    16 │
│    45 │    45 │
└───────┴───────┘

哈夫曼樹結構:
Node: 100
  Leaf: 45 (freq: 45)
  Node: 55
    Node: 25
      Leaf: 12 (freq: 12)
      Leaf: 13 (freq: 13)
    Node: 30
      Node: 14
        Leaf:  5 (freq:  5)
        Leaf:  9 (freq:  9)
      Leaf: 16 (freq: 16)

哈夫曼編碼表:
┌───────┬───────┬──────────────┐
│ 值    │ 頻率  │ 編碼         │
├───────┼───────┼──────────────┤
│     5 │     5 │         1100 │
│    13 │    13 │          101 │
│    45 │    45 │            0 │
│    12 │    12 │          100 │
│     9 │     9 │         1101 │
│    16 │    16 │          111 │
└───────┴───────┴──────────────┘

帶權路徑長度(WPL): 224
壓縮效率: 28.00% (相比8位固定編碼)