哈夫曼树：高效压缩数据的秘密武器

引言在前面的树系列中我们学习了二叉搜索树、AVL 树和红黑树——它们都是为了高效查找而设计的。今天要讲的哈夫曼树目的完全不同它是为了压缩数据而生。哈夫曼树Huffman Tree又称最优二叉树由 David Huffman 于 1952 年提出。它的核心思想是让出现频率高的字符用短编码出现频率低的字符用长编码从而使整体编码长度最短。这是变长编码的经典应用广泛用于 ZIP 压缩、JPEG 图片编码、MP3 音频压缩等领域。第一部分基本概念一、相关术语术语定义路径从根节点到目标节点经过的分支序列路径长度路径上的边的数量权节点上的数值通常表示频率/概率带权路径长度 (WPL)权 × 路径长度 的总和哈夫曼树WPL 最小的二叉树最优二叉树二、带权路径长度 WPL第二部分哈夫曼树的构建一、构建算法贪心策略构建步骤总结将所有带权节点各自作为一棵单节点二叉树放入集合从集合中选出权值最小的两棵树合并成一棵新树新树根权 两子树根权之和将新树放回集合重复 2-4直到集合中只剩一棵树二、哈夫曼树的特点特点说明权越大的节点离根越近保证 WPL 最小不存在度为 1 的节点每个内部节点都有左右子n 个叶子节点总节点数为 2n-1没有单分支节点不唯一同权值时合并顺序不同可能产生不同结构第三部分哈夫曼编码一、编码原理哈夫曼树构建完成后从根到叶子节点的路径就是该叶子节点的编码左分支 0右分支 1二、前缀编码哈夫曼编码是前缀编码——任何一个字符的编码都不是另一个字符编码的前缀。第四部分完整代码实现一、数据结构定义#include stdio.h #include stdlib.h #include string.h #define MAX_NODES 256 #define MAX_CODE_LEN 128 // 哈夫曼树节点 typedef struct { int weight; // 权值频率 int parent; // 父节点下标 int left; // 左子下标0 表示无 int right; // 右子下标0 表示无 } HTNode; // 哈夫曼编码表 typedef struct { char code[MAX_CODE_LEN]; // 编码如 110 int len; // 编码长度 } HuffmanCode;二、构建哈夫曼树// 在未选节点中找最小权值的两个 void selectMinTwo(HTNode* ht, int n, int* s1, int* s2) { int min1 -1, min2 -1; for (int i 1; i n; i) { if (ht[i].parent ! 0) continue; // 已选过的跳过 if (min1 -1 || ht[i].weight ht[min1].weight) { min2 min1; min1 i; } else if (min2 -1 || ht[i].weight ht[min2].weight) { min2 i; } } *s1 min1; *s2 min2; } // 构建哈夫曼树 // weights: 权值数组, n: 叶子节点数 // 返回构建好的哈夫曼树共有 2n-1 个节点下标从 1 开始 HTNode* buildHuffmanTree(int weights[], int n) { if (n 1) return NULL; int m 2 * n - 1; // 总节点数 HTNode* ht (HTNode*)malloc(sizeof(HTNode) * (m 1)); // 初始化所有节点 for (int i 1; i m; i) { ht[i].weight (i n) ? weights[i - 1] : 0; ht[i].parent 0; ht[i].left 0; ht[i].right 0; } // 构建内部节点 for (int i n 1; i m; i) { int s1, s2; selectMinTwo(ht, i - 1, s1, s2); ht[i].weight ht[s1].weight ht[s2].weight; ht[i].left s1; ht[i].right s2; ht[s1].parent i; ht[s2].parent i; } return ht; }三、生成哈夫曼编码// 从叶子向根回溯生成每个字符的哈夫曼编码 void generateHuffmanCode(HTNode* ht, int n, HuffmanCode* codes) { char temp[MAX_CODE_LEN]; for (int i 1; i n; i) { int current i; int parent ht[i].parent; int codeLen 0; // 从叶子向根回溯 while (parent ! 0) { if (ht[parent].left current) { temp[codeLen] 0; } else { temp[codeLen] 1; } current parent; parent ht[parent].parent; } // 反转编码回溯得到的是逆序 codes[i].len codeLen; for (int j 0; j codeLen; j) { codes[i].code[j] temp[codeLen - 1 - j]; } codes[i].code[codeLen] \0; } }四、编码与解码// 编码将字符串转为哈夫曼编码 void encode(const char* text, HuffmanCode* codes, char* result) { result[0] \0; for (int i 0; text[i] ! \0; i) { int idx text[i] - A 1; // 假设字符 A1, B2, ... strcat(result, codes[idx].code); } } // 解码将哈夫曼编码还原为字符串 void decode(const char* encoded, HTNode* ht, int n, char* result) { int root 2 * n - 1; // 根节点下标 int current root; int pos 0; for (int i 0; encoded[i] ! \0; i) { if (encoded[i] 0) { current ht[current].left; } else { current ht[current].right; } // 到达叶子节点 if (ht[current].left 0 ht[current].right 0) { result[pos] A current - 1; // 还原字符 current root; } } result[pos] \0; }五、完整测试int main() { int n 4; // 4 个字符 A, B, C, D int weights[] {2, 3, 4, 5}; // 对应频率 // 1. 构建哈夫曼树 HTNode* ht buildHuffmanTree(weights, n); // 2. 生成编码表 HuffmanCode codes[n 1]; generateHuffmanCode(ht, n, codes); // 3. 打印编码表 printf( 哈夫曼编码表 \n); for (int i 1; i n; i) { printf(%c: %s\n, A i - 1, codes[i].code); } // 4. 编码测试 const char* text ABCD; char encoded[512]; encode(text, codes, encoded); printf(\n原文: %s\n, text); printf(编码: %s\n, encoded); // 5. 解码测试 char decoded[128]; decode(encoded, ht, n, decoded); printf(解码: %s\n, decoded); // 6. 压缩率 int originalBits strlen(text) * 8; int compressedBits strlen(encoded); printf(\n原始: %d bit, 压缩后: %d bit, 压缩率: %.1f%%\n, originalBits, compressedBits, 100.0 * compressedBits / originalBits); free(ht); return 0; }运行结果 哈夫曼编码表 A: 110 B: 111 C: 10 D: 0 原文: ABCD 编码: 110111100 解码: ABCD 原始: 32 bit, 压缩后: 9 bit, 压缩率: 28.1%第五部分算法分析一、时间复杂度操作复杂度说明构建哈夫曼树O(n²)每次选最小的两个需要遍历构建优化小顶堆O(n log n)用小顶堆维护最小值生成编码O(n²)每个节点回溯到根编码/解码O(m)m 为编码串长度二、空间复杂度O(n)需要存储 2n-1 个节点。三、哈夫曼树的特点总结特点说明最优二叉树WPL 最小贪心策略每次选最小的两个合并前缀编码任何编码不是另一个的前缀无损压缩解码完全还原原始数据第六部分实际应用领域应用文件压缩ZIP、GZIP 的 Deflate 算法中使用了哈夫曼编码图像编码JPEG 压缩的最后一步使用哈夫曼编码音频编码MP3 编码中使用了哈夫曼树视频编码H.264/H.265 使用了基于哈夫曼的熵编码网络传输HTTP/2 的 HPACK 头部压缩总结一、核心要点要点内容定义带权路径长度 WPL 最小的二叉树构建贪心策略每次选权值最小的两棵合并编码规则左 0 右 1从根到叶的路径即编码编码特性前缀编码高频短码低频长码节点数n 个叶子的哈夫曼树共 2n-1 个节点二、构建步骤记忆1. 所有节点各自成树放入森林2. 选权值最小的两棵合并3. 新树放回4. 重复 2-3 直到只剩一棵树三、一句话记忆哈夫曼树是一种 WPL 最小的最优二叉树用贪心策略每次合并权值最小的两棵树构建。左 0 右 1 得到前缀编码高频短码低频长码广泛用于无损压缩。