通过前缀编码、带权路径长度与哈夫曼树掌握最优编码的构造,并用并查集实现动态集合的查找和合并。
# 一、前缀编码与带权路径长度
若一种编码中任意字符的编码都不是另一个字符编码的前缀,则称为前缀编码。对前缀编码,从左到右读取比特时,一旦读到某个完整编码就能确定一个字符,因此不需要额外分隔符即可唯一译码。
例如, {1, 01, 001, 0000} 是前缀码,每个码字都对应码树的叶子; {0, 10, 110, 1011} 不是前缀码,因为 10 是 1011 的前缀,读取到 10 时无法判断是否应立即停止。
将字符作为叶子结点、字符出现频率作为权值,令根到字符叶子的路径长度作为该字符编码长度。带权路径长度(WPL)定义为
其中 是第 个叶子权值, 是根到该叶子的路径长度。权值越大的字符若使用较短编码,通常能降低总编码长度。
# 二、哈夫曼树
哈夫曼树(Huffman Tree)是给定叶子权值时具有最小 WPL 的二叉树,也称最优二叉树。其构造使用贪心策略:
- 把每个权值视为一棵只含根的二叉树,形成森林。
- 从森林中取出权值最小的两棵树,作为新结点的左右子树。
- 新结点权值等于两棵子树权值之和,放回森林。
- 重复上述步骤,直到森林只剩一棵树。
flowchart TD
A[取当前最小的两棵树] --> B[新建权值为两者之和的父结点]
B --> C[将父树放回森林]
C --> D{森林中是否只剩一棵树}
D -->|否| A
D -->|是| E[得到哈夫曼树]例题 5.1:构造哈夫曼树并计算 WPL
给定叶子权值 。
【解】
| 步骤 | 取出的权值 | 新权值 | 森林中权值 |
|---|---|---|---|
| 初始 | — | — | |
| 1 | |||
| 2 | |||
| 3 |
令每次合并中较小权值位于左侧,则一个可能的编码为 、、、。于是
左右子树互换会改变具体比特串,但不改变叶子深度和 WPL。相同权值集合可能得到多种哈夫曼树形态,最小 WPL 相同。
当叶子数为 时,哈夫曼树有 个非叶子结点、共 个结点,且没有度为 的结点。每步把两棵树合并,使森林中的树数减少 ,因此共执行 次合并。
# 三、并查集
并查集(Disjoint Set Union, DSU)维护一组互不相交的集合,主要支持:
- Find(x):返回包含 的集合代表元。
- Union(a,b):合并包含 、 的两个集合。
常用数组 parent 记录父结点;若 parent [x] 为负数,表示 是根且负值的绝对值为集合大小。下面的实现同时使用路径压缩与按大小合并。
1 |
|
根结点保存集合大小的相反数,因此较大的集合对应更小(更负)的值。合并时把较小集合的根接到较大集合根下,避免树高无谓增加。路径压缩把查找路径上的结点直接连到根。
同时使用路径压缩和按大小或按秩合并时, 次操作的均摊时间近似为 ,其中 是增长极慢的反阿克曼函数;实际规模下可视为接近常数。空间复杂度为 。
# 四、并查集的应用
并查集适合维护 “哪些元素已连通” 的动态等价类,例如:
- 判断无向图中两个顶点是否连通;
- 处理 Kruskal 最小生成树时,判断加入一条边是否会形成环;
- 对集合进行动态合并并查询代表元。
并查集只保存集合划分,不保存集合内部的完整图路径。若问题要求恢复两点间的具体路径,需要额外保存图的边或搜索树。
# 五、考场检查清单
- 哈夫曼树每次选当前权值最小的两棵树合并,而不是一次选最小的三个。
- 左右分支的 约定可以互换;编码长度和 WPL 不变。
- 哈夫曼编码无歧义的关键是前缀码性质。
- 并查集合并前必须先比较两个代表元;代表元相同表示已经属于同一集合。
- 路径压缩和按大小 / 按秩合并共同使并查集操作均摊接近常数。
