哈夫曼編碼（Huffman Coding） 是一種基于字符出現頻率的無損數據壓縮算法，通過構建哈夫曼樹（Huffman Tree） 來生成最優前綴編碼，使得高頻字符用短編碼，低頻字符用長編碼，從而實現高效壓縮。

---

1. 哈夫曼樹（Huffman Tree）

• 定義：哈夫曼樹是一棵帶權路徑長度（WPL）最小的二叉樹。
  • 權值：字符的出現頻率（或概率）。
  • 帶權路徑長度：每個葉子節點的權值 × 其到根節點的路徑長度之和。
• 特點：
  • 沒有度為1的節點（嚴格的二叉樹）。
  • 頻率越高的字符離根越近，編碼越短。

構建哈夫曼樹的步驟

1. 統計字符頻率：為每個字符賦予權值（頻率）。
2. 創建節點集合：每個字符作為一個葉子節點，組成初始森林。
3. 合并最小權值節點：
   • 每次選擇權值最小的兩個節點，合并成一個新父節點，權值為兩者之和。
   • 重復合并，直到只剩一棵樹。
4. 生成編碼：從根到葉子的路徑，左分支為 0，右分支為 1（或相反）。

示例：
假設字符 A(5), B(9), C(12), D(13), E(16), F(45)
構建過程如下：

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
   最終哈夫曼樹結構如下：

         (100)/       \F(45)     (55)/      \(25)      (30)/    \     /   \C(12)   D(13)(14)  E(16)/ \A(5) B(9)

---

2. 哈夫曼編碼（Huffman Coding）

• 規則：從根到葉子節點的路徑生成二進制編碼。
  • 左分支為 0，右分支為 1（或相反）。
• 示例（基于上述哈夫曼樹）：
  • F(45) → 0
  • C(12) → 100
  • D(13) → 101
  • A(5) → 1100
  • B(9) → 1101
  • E(16) → 111

編碼特點

1. 前綴碼（Prefix Code）：任何字符的編碼都不是其他編碼的前綴，避免解碼歧義。
2. 最優性：在所有前綴碼中，哈夫曼編碼的壓縮效率最高（WPL最小）。

---

3. 哈夫曼編碼的壓縮與解壓

壓縮過程

1. 統計字符頻率，構建哈夫曼樹。
2. 生成字符到二進制編碼的映射表。
3. 將原始數據替換為哈夫曼編碼的二進制流。

解壓過程

1. 根據哈夫曼樹或編碼表，從二進制流中逐位解碼。
2. 從根節點開始，根據 0/1 向左/右子樹移動，直到到達葉子節點，輸出對應字符。

---

4. 代碼實現（C++ 示例）

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;// 哈夫曼樹節點
struct Node {char ch;int freq;Node *left, *right;Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};// 優先隊列的比較器（按頻率升序）
struct Compare {bool operator()(Node* a, Node* b) {return a->freq > b->freq;}
};// 構建哈夫曼樹
Node* buildHuffmanTree(const unordered_map<char, int>& freqMap) {priority_queue<Node*, vector<Node*>, Compare> pq;for (auto& pair : freqMap) {pq.push(new Node(pair.first, pair.second));}while (pq.size() > 1) {Node* left = pq.top(); pq.pop();Node* right = pq.top(); pq.pop();Node* parent = new Node('\0', left->freq + right->freq);parent->left = left;parent->right = right;pq.push(parent);}return pq.top();
}// 生成編碼表
void generateCodes(Node* root, string code, unordered_map<char, string>& codes) {if (!root) return;if (root->ch != '\0') {codes[root->ch] = code;return;}generateCodes(root->left, code + "0", codes);generateCodes(root->right, code + "1", codes);
}int main() {unordered_map<char, int> freqMap = {{'A',5}, {'B',9}, {'C',12}, {'D',13}, {'E',16}, {'F',45}};Node* root = buildHuffmanTree(freqMap);unordered_map<char, string> codes;generateCodes(root, "", codes);for (auto& pair : codes) {cout << pair.first << ": " << pair.second << endl;}return 0;
}

---

5. 應用場景

• 文件壓縮：如 ZIP、GZIP、JPEG、MP3 等格式。
• 數據傳輸：減少帶寬占用。
• 數據庫存儲：壓縮文本字段。

---

6. 優缺點

• 優點：
  • 無損壓縮，解壓后數據完全恢復。
  • 對高頻字符優化，壓縮效率高。
• 缺點：
  • 需要存儲哈夫曼樹或編碼表，可能增加額外開銷。
  • 不適合字符頻率分布均勻的場景。

---

總結

哈夫曼編碼通過構建最優二叉樹實現高效壓縮，是經典的數據壓縮算法之一。理解其核心思想（貪心算法）和實現步驟（構建樹、生成編碼），是掌握數據壓縮技術的基礎。

---

練一練

答案：B

答案：A