CSCI3160 Special 5：Huffman 编码与平均码长

原件：Sp05 题目（本地课件） p.1。 每题先题解后解析；无官方答案。频率按题目给出的百分数计算，平均长度再除100。

Problem 1：八字母最优前缀码

题解

一种合法最优编码为a=11100、b=11101、c=1111、d=100、e=101、f=110、g=00、h=01。平均码长为2.86 bit。

具体解析

频率依次为3、5、10、12、14、16、18、22。固定同权时优先处理字母标签字典序较小的节点；合并过程为：

给每次合并的左、右边分别标0、1，得到上述码。两次权重18的出现意味着编码并不唯一，交换孩子或采用另一种平局规则均可保持最优长度。

验算加权码长：3×5+5×5+10×4+12×3+14×3+16×3+18×2+22×2=286，除100得2.86。再用合并权重之和8+18+26+34+40+60+100=286交叉核验；每次合并让该子树所有字母的深度增加1，因而其增加的加权码长正是合并权重。

最优性的核心：两个最小频率可以交换到最深兄弟叶子而不增加总代价，收缩后成为一个频率和的伪字母。最优子结构使反复合并两最小安全；不是因为“看起来平衡”。

用编码和合并树交叉核算。 原表码长依次为 $5,5,4,3,3,3,2,2$，加权总长为

七次合并重量之和也为 $8+18+26+34+40+60+100=286$；总频次 100，因此平均 2.86 位。每次合并把该子树的全部字母深度增加 1，这解释了两种算法为何必须相同。

Problem 2：平均长度至多ceil(log₂ n)

题解

当n=2^h且n≥2时，构造所有码字恰长h的完全二叉码树，其平均码长为h。Huffman最优，故其平均码长≤h=ceil(log₂n)。

具体解析

上界证明只需一个可行比较方案，不必证明Huffman树本身每个叶子都在h层。频率很不均匀时，某些Huffman码可能比h长，但高频码更短，平均仍不超过h。

自取4字母频率0.7、0.1、0.1、0.1，固定两位编码平均2；Huffman可给长度1、2、3、3，平均1.5，其中两个长度3大于2，因此不能把平均界逐字母套用。

n=1若按课程非空码字约定，最优长度为1，而ceil(log₂1)=0，原命题需排除该边界或允许单字母空码。这里明确采用n≥2的通常编码情形。

Problem 3：最坏O(n log n)实现

题解

用按频率排序的二叉最小堆保存当前子树根。建堆O(n)，每轮两次DeleteMin、一次Insert，执行n−1轮，每轮O(log n)，建码树共O(n log n)、空间O(n)。

具体解析

堆内元素不仅有权重，还保存子树根指针。新父节点记两个孩子及频率和，旧子树无需复制。节点总数2n−1，所以结构线性。若每轮排序所有剩余根，会比所需界更慢；若每次合并复制整个子树，也会引入不必要开销。

得到树后用DFS携带路径位，可确定所有码字。若显式写出总长度L的所有位串，还要O(L)输出成本，总时间严格写O(n log n+L)；课堂O(n log n)通常指构造紧凑码树。极不均匀频率下L可大于n log n，不能无条件忽略输出。

Problem 4：更高频字母不能有更长最优码

题解

若fᵢ>fⱼ但dᵢ>dⱼ，交换两片叶子的字母标签，新旧代价差为 $(f_i-f_j)(d_j-d_i)<0$，与原树最优矛盾。所以频率严格下降时码长必须非递减。

具体解析

交换标签不改变树形，仍是合法前缀码；只改变哪个频率承担哪个深度。总代价中其他字母贡献完全抵消，只需比较两个字母。

自取频率0.6、0.1，码长分别3、1，原贡献1.9，交换后0.9，减少1。若频率相等，差为0，不能推出严格的长度约束；若频率较高，结论也只是码长“不更长”，不保证一定更短。

Problem 5：等频且字母数为二次幂的最短码

题解

n=2^h、n≥2时，所有码字都恰长h，最短码也是log₂n位。n=1若要求非空，答案单独为1。

具体解析

所有原叶子权重相同。第一轮层级中，每次取两个原叶子，新节点权重翻倍，大于所有未合并原叶子，所以先把全部叶子两两配完；节点数量仍是二次幂、权重再次完全相同。重复这一过程h次，所有原叶子都经历恰好h次合并。

例如n=8，权重都1：先4次合并得四个2，再2次合并得两个4，最后合并得8。每个字母从叶到根走3条边，所以最短与最长都为3。只由Q2平均上界不能单独推出此结论，等频及二次幂确保了每层完整配对。

来源与证据

Sp05 p.1；Q1合并树及2.86结果已独立计算核对。单字母与码字输出成本的例外为本文补充。