---

前言

隨著信息時代的發展，數據壓縮變得越來越重要。哈夫曼編碼（Huffman Coding）是一種經典的前綴編碼方法，能夠為出現頻率不同的符號分配不同長度的二進制編碼，從而達到壓縮的效果。

---

一、哈夫曼樹與哈夫曼編碼簡介

1. 什么是哈夫曼樹？

哈夫曼樹是一棵用于生成最優前綴編碼（二進制）的二叉樹，原理來源于 David A. Huffman 在 1952 年提出的貪心算法。對于待編碼的各個符號，根據其出現頻率（或權重）構造一顆二叉樹；較高頻次的符號被分配較短的編碼，較低頻次的符號被分配較長的編碼，從而在總的編碼長度上達到最小。

2. 為什么需要哈夫曼編碼？

• 可變長度編碼：相比固定長度編碼（例如 ASCII 固定 8 位），哈夫曼編碼根據符號頻率分配長度，能顯著減少總編碼長度。
• 前綴屬性：編碼具有前綴屬性，即任何一個編碼都不是另一個編碼的前綴，從而保證了解碼的唯一可區分性，不需分隔符即可逐位解析。
• 廣泛應用：常見于文件壓縮（如 ZIP）、圖像壓縮（如 JPEG 的某些階段）等場景。

---

二、哈夫曼編碼原理

哈夫曼編碼的核心是構建一棵最優二叉樹（哈夫曼樹），步驟概括如下：

1. 統計各符號的頻率：對待處理的數據進行掃描，記錄每個符號出現的次數。
2. 初始化森林：將每個符號視為一棵單節點二叉樹，節點權重即頻率，將這些節點放入最小堆（或其他可快速取最小的結構）。
3. 合并最小節點：每次從堆中取出兩個權重最小的節點，創建一個新節點，其權重為兩節點之和，新節點的左、右子節點指向這兩個取出的節點，然后將新節點插回堆中。
4. 重復合并：直到堆中只剩下一個節點，該節點即哈夫曼樹的根。
5. 生成編碼表：從根出發，對左右分支分別約定 “0”/“1” （或反之），遍歷到葉子時得到對應符號的二進制編碼。
6. 編碼與解碼：使用編碼表將原始數據轉換為比特串；解碼時從根沿著比特（0/1）路徑走到葉子，即得到符號，直到處理完整個比特流。

---

三、哈夫曼樹的構建步驟詳解

1. 統計字符頻率

• 對于待編碼的文本（或文件內容），遍歷每個字符，使用 std::unordered_map<char, int> 或 std::map<char, int> 記錄出現次數。
• 如果處理更廣泛的符號集（如擴展 ASCII，或多字節符號），可將鍵類型改為 std::string 或 uint8_t 等。

示例偽代碼：

std::unordered_map<char, int> freq;
for (char c : input) {freq[c]++;
}

2. 定義哈夫曼樹節點

• 每個節點包含：

  • 符號（僅葉子節點有效）
  • 頻率/權重
  • 左右子節點指針

示例：

struct HuffmanNode {char ch;                  // 符號int freq;                 // 頻率HuffmanNode *left, *right;HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}HuffmanNode(int f, HuffmanNode* l, HuffmanNode* r) : ch('\0'), freq(f), left(l), right(r) {}
};

3. 最小堆（優先隊列）的構造

• 使用 std::priority_queue，并提供自定義比較器，使得頻率小的節點優先級高（即堆頂為最小頻率節點）。
• 比較器可定義為：

struct CompareNode {bool operator()(HuffmanNode* a, HuffmanNode* b) {return a->freq > b->freq; // 小頂堆}
};

• 初始化時：對于頻率表中的每個 (字符, 頻率)，創建一個 HuffmanNode* 并推入優先隊列。

std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, CompareNode> pq;
for (auto &p : freq) {pq.push(new HuffmanNode(p.first, p.second));
}

4. 合并節點，構建哈夫曼樹

• 當 pq.size() > 1 時：

  1. 取出 node1 = pq.top(); pq.pop();
  2. 取出 node2 = pq.top(); pq.pop();
  3. 創建新節點 merged = new HuffmanNode(node1->freq + node2->freq, node1, node2);
  4. 將 merged 推回 pq。

• 循環結束后，堆中唯一節點即哈夫曼樹根 root = pq.top();

5. 生成編碼表（遞歸/迭代遍歷）

• 從根開始，維護一個字符串 code：

  • 到左子節點時，code.push_back('0')
  • 到右子節點時，code.push_back('1')
  • 訪問到葉子節點（left==nullptr && right==nullptr），將 code 對應當前葉子符號保存到編碼表 std::unordered_map<char, std::string>。

• 遞歸示例：

void buildCodes(HuffmanNode* node, const std::string &prefix, std::unordered_map<char, std::string> &codeTable) {if (!node) return;if (!node->left && !node->right) {// 葉子節點codeTable[node->ch] = prefix;} else {buildCodes(node->left, prefix + '0', codeTable);buildCodes(node->right, prefix + '1', codeTable);}
}

6. 編碼過程

• 遍歷原始輸入串，每個字符查表拼接對應二進制字符串，例如 std::string encoded; for (char c: input) encoded += codeTable[c];
• 注意：實際壓縮通常需要把這些“字符 ‘0’/‘1’”轉換成位并打包存儲；這里示例為演示流程，可用 std::vector<bool> 或自定義位操作將比特寫入文件/內存。

7. 解碼過程

• 給定哈夫曼樹根和編碼后的二進制串，逐位遍歷：

  • 從根開始，遇 ‘0’ 則走左子樹，遇 ‘1’ 則走右子樹。
  • 到達葉子節點時，輸出該葉子符號，指針重置到根，繼續處理后續比特，直到遍歷完整個比特串。

示例：

std::string decode(HuffmanNode* root, const std::string &encoded) {std::string result;HuffmanNode* node = root;for (char bit : encoded) {if (bit == '0') node = node->left;else node = node->right;if (!node->left && !node->right) {// 葉子result.push_back(node->ch);node = root;}}return result;
}

---

四、C++ 實現示例

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>
#include <vector>// 哈夫曼樹節點定義
struct HuffmanNode {char ch;int freq;HuffmanNode *left, *right;// 葉子節點構造HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}// 非葉子節點構造HuffmanNode(int f, HuffmanNode* l, HuffmanNode* r) : ch('\0'), freq(f), left(l), right(r) {}
};// 比較器：頻率小的優先
struct CompareNode {bool operator()(HuffmanNode* a, HuffmanNode* b) {return a->freq > b->freq;}
};// 遞歸釋放哈夫曼樹內存
void freeTree(HuffmanNode* node) {if (!node) return;freeTree(node->left);freeTree(node->right);delete node;
}// 構建頻率表
std::unordered_map<char, int> buildFrequency(const std::string &input) {std::unordered_map<char, int> freq;for (char c : input) {freq[c]++;}return freq;
}// 構建哈夫曼樹，返回根指針
HuffmanNode* buildHuffmanTree(const std::unordered_map<char,int> &freq) {std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, CompareNode> pq;// 初始化：所有葉節點入堆for (auto &p : freq) {pq.push(new HuffmanNode(p.first, p.second));}// 特殊情況：只有一種字符if (pq.size() == 1) {// 復制一個節點使得樹有兩層HuffmanNode* only = pq.top();pq.pop();// 新建一個虛擬節點，頻率為 0HuffmanNode* dummy = new HuffmanNode('\0', 0);HuffmanNode* root = new HuffmanNode(only->freq + dummy->freq, only, dummy);return root;}// 合并過程while (pq.size() > 1) {HuffmanNode* n1 = pq.top(); pq.pop();HuffmanNode* n2 = pq.top(); pq.pop();HuffmanNode* merged = new HuffmanNode(n1->freq + n2->freq, n1, n2);pq.push(merged);}return pq.top();
}// 生成編碼表
void buildCodes(HuffmanNode* node, const std::string &prefix, std::unordered_map<char, std::string> &codeTable) {if (!node) return;if (!node->left && !node->right) {// 葉子節點codeTable[node->ch] = prefix.empty() ? "0" : prefix; // 若只有一個字符，prefix 可能為空，此處設為 "0"} else {buildCodes(node->left, prefix + '0', codeTable);buildCodes(node->right, prefix + '1', codeTable);}
}// 編碼
std::string encode(const std::string &input, const std::unordered_map<char, std::string> &codeTable) {std::string encoded;for (char c : input) {encoded += codeTable.at(c);}return encoded;
}// 解碼
std::string decode(HuffmanNode* root, const std::string &encoded) {std::string result;HuffmanNode* node = root;for (char bit : encoded) {if (bit == '0') node = node->left;else node = node->right;// 到達葉子if (!node->left && !node->right) {result.push_back(node->ch);node = root;}}return result;
}int main() {// 示例文本std::string text;std::cout << "請輸入要編碼的文本: ";std::getline(std::cin, text);if (text.empty()) {std::cout << "輸入為空，退出。\n";return 0;}// 1. 統計頻率auto freq = buildFrequency(text);// 2. 構建哈夫曼樹HuffmanNode* root = buildHuffmanTree(freq);// 3. 生成編碼表std::unordered_map<char, std::string> codeTable;buildCodes(root, "", codeTable);// 4. 打印編碼表std::cout << "字符  哈夫曼編碼\n";for (auto &p : codeTable) {// 注意：部分字符（如空格）打印可能不易區分，可轉義顯示if (p.first == ' ') std::cout << "' '";else std::cout << p.first;std::cout << "    " << p.second << "\n";}// 5. 編碼std::string encoded = encode(text, codeTable);std::cout << "編碼后比特串長度: " << encoded.size() << "\n";// 可視化輸出前若長度過長可只顯示前若干std::cout << "編碼比特串示例(前100位): " << encoded.substr(0, std::min(size_t(100), encoded.size())) << (encoded.size() > 100 ? "..." : "") << "\n";// 6. 解碼驗證std::string decoded = decode(root, encoded);std::cout << "解碼后文本: " << decoded << "\n";if (decoded == text) {std::cout << "解碼驗證通過，原文與解碼結果一致。\n";} else {std::cout << "解碼驗證失敗！\n";}// 7. 釋放內存freeTree(root);return 0;
}

代碼說明

• 使用 std::getline 讀取整行文本，可包含空格。
• 頻率統計用 unordered_map；若需要對多字節符號（如 UTF-8 多字節），需改為按字節或按寬字符處理。
• 哈夫曼樹構建時，若僅一種符號，需要特別處理確保編碼至少一位。
• 編碼表生成時，若 prefix 為空（僅一種葉子），指定 “0” 作為編碼。
• 示例中直接以 std::string 存儲“0”“1”，實際壓縮應用中，需將這些比特打包成字節或寫入文件。
• 解碼時遍歷比特流，走樹直到葉子，輸出字符。
• 注意釋放動態分配的節點，避免內存泄漏；也可用智能指針（如 std::unique_ptr）做改進。

---

五、測試

• 示例輸入：
  "this is an example for huffman encoding"

• 頻率統計：
  統計各字符出現次數，如 ' ' 頻率最高等。

• 編碼表：
  輸出各字符的二進制編碼，頻率高的字符（空格、e、…）對應較短編碼。

• 壓縮比估算：

  • 原始：假設使用 ASCII，每字符 8 位，總長度 ≈ 輸入長度 × 8。
  • 哈夫曼：總比特長度為編碼后 encoded.size()。壓縮比 = encoded.size() / (input.size() * 8)。

• 測試：
  在本地編譯運行，驗證編碼-解碼過程正確性，并對不同文本測試壓縮率。

---

六、復雜度分析

• 時間復雜度：

  • 頻率統計：O(N)，N 為輸入長度。
  • 堆初始化：若 M 為不同符號個數，則 O(M) 節點推入堆，建堆 O(M)。
  • 合并過程：需要做 M-1 次合并，每次從堆中取兩次和插入一次，時間 O(log M)，故總 O(M log M)。
  • 生成編碼表：遍歷哈夫曼樹，節點總數約 2M-1，時間 O(M)。
  • 編碼/解碼：編碼 O(N * average_code_length) → 實際拼接字符串為 O(N * L)，但若打包為位操作可做到 O(N)；解碼 O(encoded_length) ≈ O(N * average_code_length)。一般平均編碼長度有限。

• 空間復雜度：

  • 頻率表：O(M)。
  • 哈夫曼樹：O(M)節點。
  • 編碼表：O(M)存儲每個符號對應字符串。
  • 編碼輸出：O(encoded_length)。

• M 通常遠小于 N（字符總種類有限），因此主要成本在 O(N) 級別。

---

七、應用場景與擴展

• 文件壓縮：ZIP、GZIP 等，哈夫曼編碼常作為最后一步變長編碼，但通常結合其他算法（如 LZ77）先做模式替換，再做哈夫曼編碼。
• 圖像/音頻壓縮：JPEG、MP3 等在某些階段使用哈夫曼編碼對量化后的符號進行壓縮。
• 網絡傳輸：可對文本或協議字段做哈夫曼編碼以節省帶寬（需雙方約定編碼表）。
• 擴展到字典外符號：若在線構建編碼表，可考慮動態哈夫曼（如 FGK 算法）或自適應哈夫曼。