哈夫曼编码和哈夫曼树

哈夫曼编码（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