算法简介
哈夫曼编码（Huffman Coding）是由美国计算机科学家大卫·哈夫曼（David A. Huffman）在1952年提出的一种无损数据压缩算法。 它通过构建最优二叉树（哈夫曼树），为不同频率的字符分配不同长度的编码。
核心目标
- 压缩数据：频率越高的字符，编码越短，减少总编码长度（总长度=Σ(字符频率×编码长度)）
- 无歧义解码：确保任何字符的编码都不是其他编码的前缀（前缀码特性），避免解码时混淆
算法步骤
哈夫曼编码的生成过程可分为构建哈夫曼树和生成编码两部分，具体步骤如下：
1
统计字符频率
首先统计所有字符出现的频率（或概率），作为构建哈夫曼树的基础。
例如：字符集 {a,b,c,d,e,f}，频率分别为：
a: 5%
b: 9%
c: 12%
d: 13%
e: 16%
f: 45%
2
构建哈夫曼树（最优二叉树）
哈夫曼树是一种带权路径长度（WPL）最短的二叉树，构建规则如下：
初始化
将每个字符视为一个独立的"叶子节点"，节点的权值为其频率。
初始节点集：{a(5), b(9), c(12), d(13), e(16), f(45)}
合并节点
- 从当前节点集中选出权值最小的两个节点，作为新节点的左右子树
- 新节点的权值为两个子节点的权值之和（称为"合并权值"）
- 将新节点加入节点集，同时移除被合并的两个节点
重复合并
直到节点集中只剩下一个节点（即哈夫曼树的根节点）。
案例演示（以上例字符集）：
第1次合并：最小的两个节点是
a(5) 和 b(9)，合并为新节点 N1(14)第2次合并：最小的两个节点是
c(12) 和 d(13)，合并为 N2(25)第3次合并：最小的两个节点是
N1(14) 和 e(16)，合并为 N3(30)第4次合并：最小的两个节点是
N2(25) 和 N3(30)，合并为 N4(55)第5次合并：最后两个节点
f(45) 和 N4(55) 合并为根节点 Root(100)哈夫曼树结构
Root(100) / \ f(45) N4(55) / \ N2(25) N3(30) / \ / \ c(12) d(13) N1(14) e(16) / \ a(5) b(9)
3
生成哈夫曼编码
从哈夫曼树的根节点出发，沿路径到每个叶子节点（字符），左分支记为0，右分支记为1，路径上的数字序列即为该字符的哈夫曼编码。
以上例生成的编码：
f (45%)0
e (16%)110
d (13%)100
c (12%)101
b (9%)1110
a (5%)1111
关键特性
前缀码
由于每个字符都是哈夫曼树的叶子节点，路径不会重叠，因此任何编码都不是其他编码的前缀，解码时可唯一识别。
最优性
哈夫曼树的带权路径长度（WPL）最短，即总编码长度最小，是理论上最优的前缀编码方案。
非唯一性
哈夫曼树的结构可能因"合并时左右子节点顺序"不同而略有差异，导致编码不同，但总长度不变。
应用场景
哈夫曼编码广泛用于数据压缩领域，其核心优势是能根据数据分布动态优化编码，比固定长度编码（如ASCII）更节省空间。
文件压缩
广泛应用于ZIP、GZIP、7-Zip等主流压缩格式中，作为核心压缩算法之一。
图像压缩
在JPEG、PNG等图像格式的熵编码阶段使用，有效减少图像文件大小。
通信传输
在数据通信中用于高效传输数据，减少带宽占用，提高传输效率。
数据存储
用于数据库和文件系统中，减少存储空间占用，提高存储效率。
