通过前缀编码、带权路径长度与哈夫曼树掌握最优编码的构造,并用并查集实现动态集合的查找和合并。

# 一、前缀编码与带权路径长度

若一种编码中任意字符的编码都不是另一个字符编码的前缀,则称为前缀编码。对前缀编码,从左到右读取比特时,一旦读到某个完整编码就能确定一个字符,因此不需要额外分隔符即可唯一译码。

例如, {1, 01, 001, 0000} 是前缀码,每个码字都对应码树的叶子; {0, 10, 110, 1011} 不是前缀码,因为 10 是 1011 的前缀,读取到 10 时无法判断是否应立即停止。

前缀码集合的码字均位于叶子,与码字 10 是 1011 前缀的非前缀集合对比

将字符作为叶子结点、字符出现频率作为权值,令根到字符叶子的路径长度作为该字符编码长度。带权路径长度(WPL)定义为

WPL⁡=∑i=1nwili,\operatorname{WPL}=\sum_{i=1}^{n}w_i l_i,

其中 wiw_i 是第 ii 个叶子权值,lil_i 是根到该叶子的路径长度。权值越大的字符若使用较短编码,通常能降低总编码长度。

# 二、哈夫曼树

哈夫曼树(Huffman Tree)是给定叶子权值时具有最小 WPL 的二叉树,也称最优二叉树。其构造使用贪心策略:

  1. 把每个权值视为一棵只含根的二叉树,形成森林。
  2. 从森林中取出权值最小的两棵树,作为新结点的左右子树。
  3. 新结点权值等于两棵子树权值之和,放回森林。
  4. 重复上述步骤,直到森林只剩一棵树。

flowchart TD
    A[取当前最小的两棵树] --> B[新建权值为两者之和的父结点]
    B --> C[将父树放回森林]
    C --> D{森林中是否只剩一棵树}
    D -->|否| A
    D -->|是| E[得到哈夫曼树]

例题 5.1:构造哈夫曼树并计算 WPL

给定叶子权值 2,4,5,72,4,5,7。

【解】

步骤取出的权值新权值森林中权值
初始——2,4,5,72,4,5,7
12,42,4665,6,75,6,7
25,65,611117,117,11
37,117,1118181818

令每次合并中较小权值位于左侧,则一个可能的编码为 7↦07\mapsto0、5↦105\mapsto10、2↦1102\mapsto110、4↦1114\mapsto111。于是

WPL⁡=7×1+5×2+2×3+4×3=35.\operatorname{WPL}=7\times1+5\times2+2\times3+4\times3=35.

权值 2、4、5、7 的哈夫曼树构造过程、叶子编码与带权路径长度计算

左右子树互换会改变具体比特串,但不改变叶子深度和 WPL。相同权值集合可能得到多种哈夫曼树形态,最小 WPL 相同。

当叶子数为 n≥2n\ge2 时,哈夫曼树有 n−1n-1 个非叶子结点、共 2n−12n-1 个结点,且没有度为 11 的结点。每步把两棵树合并,使森林中的树数减少 11,因此共执行 n−1n-1 次合并。

# 三、并查集

并查集(Disjoint Set Union, DSU)维护一组互不相交的集合,主要支持:

  • Find(x):返回包含 xx 的集合代表元。
  • Union(a,b):合并包含 aa、bb 的两个集合。

常用数组 parent 记录父结点;若 parent [x] 为负数,表示 xx 是根且负值的绝对值为集合大小。下面的实现同时使用路径压缩与按大小合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdbool.h>

int Find(int parent[], int x) {
int root = x;
while (parent[root] >= 0) {
root = parent[root];
}

while (x != root) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}

bool Union(int parent[], int a, int b) {
int rootA = Find(parent, a);
int rootB = Find(parent, b);
if (rootA == rootB) {
return false;
}

if (parent[rootA] > parent[rootB]) {
int temp = rootA;
rootA = rootB;
rootB = temp;
}
parent[rootA] += parent[rootB];
parent[rootB] = rootA;
return true;
}

根结点保存集合大小的相反数,因此较大的集合对应更小(更负)的值。合并时把较小集合的根接到较大集合根下,避免树高无谓增加。路径压缩把查找路径上的结点直接连到根。

同时使用路径压缩和按大小或按秩合并时,mm 次操作的均摊时间近似为 O(mα(n))O(m\alpha(n)),其中 α\alpha 是增长极慢的反阿克曼函数;实际规模下可视为接近常数。空间复杂度为 O(n)O(n)。

Find 操作路径压缩前后的父指针,以及 Union 按集合大小合并并更新负大小数组

# 四、并查集的应用

并查集适合维护 “哪些元素已连通” 的动态等价类,例如:

  • 判断无向图中两个顶点是否连通;
  • 处理 Kruskal 最小生成树时,判断加入一条边是否会形成环;
  • 对集合进行动态合并并查询代表元。

并查集只保存集合划分,不保存集合内部的完整图路径。若问题要求恢复两点间的具体路径,需要额外保存图的边或搜索树。

# 五、考场检查清单

  1. 哈夫曼树每次选当前权值最小的两棵树合并,而不是一次选最小的三个。
  2. 左右分支的 0/10/1 约定可以互换;编码长度和 WPL 不变。
  3. 哈夫曼编码无歧义的关键是前缀码性质。
  4. 并查集合并前必须先比较两个代表元;代表元相同表示已经属于同一集合。
  5. 路径压缩和按大小 / 按秩合并共同使并查集操作均摊接近常数。
更新于 阅读次数 次

请我喝[茶]~( ̄▽ ̄)~*

梦前辈 微信支付

微信支付

梦前辈 支付宝

支付宝