宇宙免责申明:
- 本文由deepseek进行了一些专业术语上的优化,可能会出现错误,如有错误,请私信联系.
- 本文的所有图均为本人手画,如果发现图中有错误,请私信联系.
- 内容为本人原创，未进允许，禁止搬运或转载。
一些关于密码学的知识
在开始我们今天的主要内容之前，我们需要了解一些关于密码学的知识，以便我们更好的理解。
- 明文
最原始、没有经过任何特殊处理，谁都能直接看懂的信息。
比如你给朋友写的小纸条：“放学后操场见”，这就是一条明文。
- 密文
为了隐藏信息的内容，按照某种规则把明文变换成另一种形式，使得不知道规则的人难以理解。
比如，我们约定把每个字都替换成它在字典里的后一个字，“放学后操场见”可能就变成了“放笔后笔场见”之类的乱码，这就成了一条密文。
将明文转换为密文的过程叫做加密，反过来，把密文恢复成明文的过程叫做解密。这套变换规则通常需要一把“钥匙”用来解密，也就是密钥。
- 加密：明文 → 密文
- 解密：密文 → 明文
- 密钥、密码本：加密与解密所依赖的“钥匙”
了解到这里，你可能会有疑问：这和哈夫曼树有什么关系？
实际上，哈夫曼树提供了一种十分精巧的编码方式。它不仅能极大压缩数据，还能根据字符出现的频率，生成独一无二的“密码本”。如果用这个密码本来对信息重新编码，在不知情的人眼里，它就是一团难以破解的0和1密文。有了这些概念垫底，我们就能更好地理解哈夫曼树在信息编码中的妙用了。
引入
一些问题
小明要参加考试，他的成绩很不好，而坐在他后面的小红是个学霸。小明花重金收买了小红并与她约定，小红做完试卷后用手指敲桌子，把选择题答案传给小明。
选择题只有 A、B、C、D 四个选项，他们定了一套最简单的暗号：
- 敲 1 下 = A
- 敲 2 下 = B
- 敲 3 下 = C
- 敲 4 下 = D
考试刚开始，小明就发现了两个大问题：
第一，容易暴露。碰上连续几道题都选 C 或 D，小红需要不停地敲，动静太大，很容易被老师发现。
第二，容易混淆。小红想传答案 “BA”——先敲 2 下表示 B，再敲 1 下表示 A。可小明耳朵里听到的是连续 3 下，他以为答案是 C！之所以会搞错，是因为 “B” 的编码“敲 2 下”和 “A” 的编码“敲 1 下”混在一起，根本无法分清边界。本质上，这是一个编码成了另一个编码的前缀，导致解码出现歧义。
那么，有没有一种编码方法，既能让总敲击次数尽量少，又绝不会有前缀歧义呢？
哈夫曼树，正是用来解决这类问题的完美工具。它能根据选项出现的频率，自动生成一套最优的、绝不会产生歧义的编码方案。接下来，我们就看看它是怎么做到的。
哈夫曼树与哈夫曼编码
哈夫曼树
定义：哈夫曼树，又称为最优二叉树，是一种带权路径长度最短的二叉树。
那他具体长啥样呢，长这样：
（数据为：5,9,16,12,13,45）
要搞懂哈夫曼树，得先明白什么叫“带权路径长度”。在一棵二叉树里，每个叶子节点都有一个权值（比如字符的出现次数），从根走到这个叶子经过的边数就是它的路径长度。把一个叶子的权值乘上它的路径长度，再把所有叶子的这个乘积加起来，得到的就是整棵树的带权路径长度，记作 WPL：
WPL=∑i=1nwi×liWPL = \sum_{i=1}^{n} w_i \times l_iWPL=i=1∑nwi×li
其中wiw_iwi是第iii个叶子的权值，lil_ili是它的深度（到根经过的边数）。哈夫曼树的目标，就是让这个 WPL 变得最小。怎么做到呢？思路很直接：让出现次数多（权值大）的叶子离根近一点，出现次数少（权值小）的叶子离根远一点。这样，权重大的乘上小的深度，总和自然就最小了。
哈夫曼树的构建
构建哈夫曼树是一个“贪心”的过程，每次挑最小的两棵树合并，自底向上长成一棵完整的大树。具体步骤如下：
- 把每个带权值的节点都看作一棵只含一个根节点的二叉树，所有树组成一片森林。
- 在森林中，每次选出根节点权值最小的两棵树，将它们合并成一棵新树。新树的根节点权值，就是这两棵子树权值之和，左右孩子分别就是这两棵子树。
- 把新树放回森林，重复第 2 步，直到森林里只剩下一棵树。这最后剩下的树，就是哈夫曼树。
回到小明的例子
还记得小明和小红敲桌子的暗号吗？假设考试选择题的四个选项 A、B、C、D 在试卷中出现的频率统计出来分别为 5、1、2、4。我们就拿这些频率作为权值，亲手建一棵哈夫曼树。
- 初始值：
5(A)、1(B)、2(C)、4(D) - 第1次合并：最小的两个是
1(B)和2(C)，合并成一个权值为333的新节点，左右孩子是 B 和 C。
此时森林变成：5(A)、3、4(D) - 第2次合并：现在最小的两个是
3和4(D)，合并成权值为777的节点，左右孩子是刚才的3和 D。
森林变为：5(A)、7 - 第3次合并：只剩下两棵树
5(A)和7，合并成权值为121212的根节点。哈夫曼树建成！
得到的树结构：
现在计算一下这棵哈夫曼树的带权路径长度 WPL：
WPL=5×1+4×2+1×3+2×3=5+8+3+6=22WPL = 5 \times 1 + 4 \times 2 + 1 \times 3 + 2 \times 3 = 5 + 8 + 3 + 6 = 22WPL=5×1+4×2+1×3+2×3=5+8+3+6=22
如果小明当初采用最简单的等长编码（每个选项用 2 位二进制表示，相当于固定路径长度为 2），总权值路径长度会是(5+1+2+4)×2=24(5+1+2+4) \times 2 = 24(5+1+2+4)×2=24。很显然，22 < 24，哈夫曼树确实让整体的“传输负担”变轻了。这也就为后面生成最优的哈夫曼编码打下了基础。
「注」：当然，在哈夫曼树并不是唯一的，叶子节点在同一层的位置是可以进行无数次调换的，因而每一组数据对应的哈夫曼树就有很多种，所以，当你在做题时发现没有选项能与你答案对应上时，不妨换一种画法。当然，哈夫曼树与哈夫曼编码的几个唯一和不唯一在后文会重新强调一遍，这里旨在解答读者在阅读时可能会遇到的问题。
哈夫曼编码
哈夫曼编码是在哈夫曼树的基础上进行的编码操作，它有好多套编码逻辑，这里简单介绍几种：
- 左1右0
- 左0右1
在图上则表示为：
在图片中，我们采用了左1右0的编码方案。于是，我们便很容易就能得到这些数据的的哈夫曼编码：
5 的编码为 1011
9 的编码为 1010
12的编码为 111
13的编码为 110
16的编码为 100
45的编码为 0
可以看到，权值最大的 45 分到了最短的编码0，而权值较小的 5 和 9 分到了较长的编码。这正是哈夫曼编码的精髓——频率越高，编码越短。
回到我们小明的例子。按照上一节构建好的哈夫曼树，如果我们采用“左0右1”的方案，A、B、C、D 的编码就是：
- A（权值 5）：
0 - D（权值 4）：
10 - B（权值 1）：
110 - C（权值 2）：
111
现在小明再让小红用这套编码敲桌子传递答案，情况就完全不同了。假设答案是“A、D、C、A”，对应编码就是0、10、111、0，连在一起敲出来是0101110。小明按编码表去切分，0只能是 A，接下来10只能是 D，再往后111只能是 C，最后0又是 A，清清楚楚，不会有任何歧义。
这就是哈夫曼编码的两个关键优势：
无前缀歧义——每一个编码都不是另一个编码的前缀。因为所有字符都在叶子节点上，编码对应的路径走到叶子就停止，绝对不会走到半路碰上另一个字符，解码时边界非常清晰。
总长度最短——数学上可以证明，哈夫曼编码是所有前缀编码中，带权路径长度最小的。对于小明来说，这意味着在保证不出错的前提下，整场考试敲桌子的总次数降到了最低。
理解了哈夫曼树和哈夫曼编码，再回头看 CSP-J 的考题，无非就是手动构建哈夫曼树、计算带权路径长度、或者根据给定的树写出编码。只要记住“每次挑两个最小的合并”这个核心步骤，这些题目都能迎刃而解。
唯一和不唯一
在学习完了上面所有内容后，下面我们来把“唯一”和“不唯一”的地方彻底理清楚。
不唯一
树的结构形态不同
哈夫曼树的表现形式并不唯一。原因在于构建过程中的“选择”上。
回忆一下构建步骤：每次从森林中选出两个权值最小的根节点合并。问题就出在这里——如果森林中存在多个权值相同的节点，或者新合并出来的节点权值和森林中原有的某个节点权值相同，那么选谁、谁当左孩子、谁当右孩子，都会影响最终树的样子。
所以：只要在合并过程中出现了相等的权值，就可能产生不同的哈夫曼树结构。
同一棵树的编码方案不同
即便哈夫曼树的结构固定下来，编码方案也不唯一。前面提到过，既可以“左 0 右 1”，也可以“左 1 右 0”。这两种方案得到的编码表恰好是“翻转”关系，但本质上都是正确的前缀编码。
另外，合并时如果两个子树权值相同，谁当左孩子、谁当右孩子都可以，交换左右孩子后，编码也会随之改变。
唯一
最小带权路径长度（WPL）
虽然树的结构多种多样，但有一个东西是铁打不变的，那就是最小带权路径长度 WPL。
不管你在权值相等时做了怎样的选择，不管左右孩子怎么安排，最终所有合法哈夫曼树的 WPL 值一定相等，而且都是该组权值下能达到的最小值。这才是哈夫曼树最本质的属性。考试中如果让你算 WPL，大可放心，只要构建过程遵循“每次取最小两个合并”的原则，最终算出的结果就是唯一的标准答案。
各字符的编码长度
这一点很多同学容易忽略。虽然编码本身（具体是011还是100）会因为左右分支约定不同而变化，但每个字符的编码长度（即它在树中的深度）在所有等价的哈夫曼树中是一致的。
也就是说，在给定频率分布下，出现最频繁的字符一定拿到最短的编码，出现最少的字符一定拿到最长的编码，而且这些编码的位数是确定不变的。所以，如果题目只问你某个字符的编码是几位，答案也是唯一的。
小结
| 项目 | 唯一？ |
|---|---|
| 哈夫曼树的形态结构 | 不唯一（权值相等时选择不同） |
| 具体编码值（0/1 序列） | 不唯一（左右分支约定可交换） |
| 最小带权路径长度（WPL） | 唯一 |
| 每个字符的编码长度 | 唯一 |
搞清楚这几点，以后再遇到关于哈夫曼树“是不是唯一”的问题，思路就不会乱了。
