6.2 Huffman 编码与 heap 应用

动机

固定长度编码给每个符号分配相同数量的 bit，做法简单，却没有利用数据中的频率差异。如果 a 占一个文件的近一半，而 f 只是偶尔出现，让它们使用一样长的 codeword 就会浪费空间。Huffman coding 把 binary tree 和 min-priority queue 结合起来，使高频符号拥有较短路径，低频符号承担较长路径。

分析时必须区分三个问题。第一，构造：怎样通过反复合并当前频率最小的两棵 subtree 得到整棵树。第二，可解码性：可变长度 codeword 直接相连而没有分隔符，为什么仍能逐个还原。第三，成本：在给定频率模型下，最终数据到底使用多少 bit。只画出一棵看起来合理的树而不检查这三个方面，答案并不完整。

Heap 的同一模式还可以合并 k 个已排序 linked list。下一个输出必定是各 list 当前 head 中的最小值；min-heap 只保存这些候选项，因此不必每输出一次就重新扫描全部 k 个 heads。两个应用的共同思想，都是维护一个较小、只包含当前可选最小元素的 frontier。

定义

每轮合并两个 minimum

先为每个符号建立一个以频率为 key 的 leaf，再把所有 leaves 放入 min-heap。每轮执行两次 deleteMin，把这两棵 tree 接在一个新 internal node 下面；新 node 的权重是两者之和，然后将它 insert 回 heap。每次 merge 都使 heap item 数减一，因此 m 个 leaves 恰好进行 m - 1 次 merges。

HUFFMAN(symbols with positive weights)
    H = a min-heap containing one leaf per symbol
    while size(H) > 1
        x = deleteMin(H)
        y = deleteMin(H)
        z = a new internal node with weight x.weight + y.weight
        z.left = x
        z.right = y
        insert(H, z)
    return deleteMin(H)

把较轻的 x 放在左边可以让 trace 容易复现，但交换任何 internal node 的左右 children 仍然有效，只会改变 bit string，不会改变 codeword length 或存储成本。遇到相同权重时，不同 heap tie-breaking 也可能生成不同但同样合法的树，所以 Huffman code table 不一定唯一。

整个过程维持一个 forest invariant：heap 中每个 item 都是一棵 subtree 的 root；这些 subtrees 的 leaves 互不重叠，合起来恰好覆盖整个 alphabet。Merge 用两个部分的 union 取代它们，并把下方所有 leaf weights 之和写在新 root 上，因此 invariant 保持不变。最后只剩一个 root 时，每个原符号恰好出现一次。

如果输入长度为 N，扫描并统计 frequencies 需要 O(N)。由 m 个 leaves bottom-up 建 heap 是 O(m)；之后 m-1 轮各做两次 deleteMin 和一次 insert，每项最多 O(log m)，建树成本为 O(m log m)。遍历最终 tree 并记录所有 codes 是 O(m)，完整 preprocessing 因此为 O(N + m log m)；若题目已经给出 frequency table，就没有 O(N) 扫描。Encoding 对每个输入符号执行一次 code-table lookup，另花费与实际输出 bit 数成比例的时间；decoding 则对读入的 bit 数是线性的。

当 alphabet 只有一个符号时，merge loop 会留下单一 leaf 和空路径。实际格式通常约定给这个符号 code 0，使重复出现仍有明确表示。本节六符号例题不需要这个 edge-case 约定。

定理 / 命题

这些命题足以支持下面的 decoding 和数值核算。该构造确实是 Huffman greedy algorithm，但要证明它在所有 binary prefix trees 中使 weighted length 最小，需要完整的 exchange argument；这超出了本节仓库课程材料支持的范围。下面不会把构造过程误当成已经完成的 optimality proof。

证明思路

第一个命题可以用反证法说明。假设某 leaf code 是另一个 leaf code 的 prefix，沿较短 code 从 root 走完时已经到达第一个 leaf，却还需要沿更多 edges 才能到达第二个符号。Leaf 没有 child，所以不可能。这也说明 source symbols 必须放在 leaves，而不能放在 internal nodes。

解码时从 root 开始逐 bit 行走。第一次到达 leaf 就强制确定了第一个符号：若更早停止，就需要 internal node 表示 code；若继续前进，该 leaf code 就会成为更长 code 的 prefix。输出该符号并回到 root，对剩余 codewords 重复即可。若 bit stream 结束时停在 internal node，它是截断或无效数据，而不是第二种合法解码。

对 merge-sum identity，设权重为 p 和 q 的两个 roots 接到一个新 parent 下方。两个 subtrees 中每个 leaf 的 depth 都增加一，所以 weighted length 增量恰好为 p+q，也就是新 internal node 的权重。从 depth 全为零的独立 leaves 开始，将所有轮次的增量相加，就得到最终 weighted external path length。因此 code-length sum 和 merge-weight sum 应当一致，可用于发现算术或 tree trace 错误。

对于 k-way merge，invariant 是 heap 恰好保存每个非空 list 的第一个未输出 element。由于每个 list 已排序，该 head 不大于同一 list 的所有其余元素；因此 heap minimum 就是全体剩余元素的 global minimum。删除它，并把同一 list 的 successor 放回 heap，就恢复了 invariant。

例题详解

                           (100)
                         0 /   \ 1
                       a:45    (55)
                              0 /  \ 1
                              (25)  (30)
                             0/ \1  0/ \1
                          c:12 b:13 (14) d:16
                                    0/ \1
                                  f:5 e:9

MERGE_K_SORTED_LISTS(lists)
    H = empty min-heap
    for each nonempty list i
        insert(H, (lists[i].head.value, i, lists[i].head))
    output = empty list
    while H is not empty
        (value, i, node) = deleteMin(H)
        successor = node.next
        append value to output
        if successor exists
            insert(H, (successor.value, i, successor))
    return output

常见错误

• 合并两个最大 weights，或者一直使用旧的原始 frequency 顺序。每一轮都必须从当前 heap 选择两个 minima，包括刚刚 insert 的 internal nodes。
• 从 leaf 向 root 反向读取 code。Code 是 root-to-leaf path，反转之后并非同一个 bit string。
• 把 source symbol 放在 internal node。它的 code 可能成为 descendant code 的 prefix，从而破坏无分隔符解码。
• 声称频率较高的符号一定拥有严格更短的 code。Tie 和 tree shape 可以让多个符号码长相同；准确长度由最终 tree 决定。
• 只数 codewords 而不计算 weighted length；还要注意 224,000 bits 只是 payload，没有包含 tree/header overhead。
• 认为六个 symbols 可以用两个 fixed bits。2^2=4 只能区分四种值，六个 symbols 必须使用三个 bits。
• 把 k 个 lists 的所有 elements 都放入 merge heap。只有每个非空 list 的 current head 合格，heap size 应当不超过 k。

总结

Huffman construction 使用 min-heap 反复合并两个 minimum-weight roots。原符号全部位于 leaves，因此 root-to-leaf codes 是 prefix-free，连续 codewords 可以唯一解码。六符号例题的 merges 是 5+9=14、12+13=25、14+16=30、25+30=55、45+55=100；码长为 1,3,3,3,4,4，100,000-character payload 准确使用 224,000 bits。相对于指定的 8-bit ASCII 节省 576,000 bits，相对于最短三-bit fixed code 节省 76,000 bits。

Heap 也可以合并 k 个 sorted lists。每个非空 list 只提供一个 current head，使 n 次输出都能以 O(log k) 取得 global minimum，总时间 O(n log k)，额外空间 O(k)。

练习

1. 从 weights 5,9,12,13,16,45 开始，列出每次 Huffman merge，以及 insert 后 heap 中剩余的 weights。
2. 使用完整构造中的 code table 解码 11011100111，并标出 leaf boundaries。
3. 分别用 weighted code lengths 和 merge-sum identity 重新计算六符号 payload；再给出相对于 8-bit ASCII 和六符号最短 fixed-length code 的节省量。
4. 判断 {0,01,11} 是否 prefix-free，并解释其 decoding 后果。
5. 写出合并 k 个 sorted linked lists 的 heap 方法，说明 invariant、以总长度 n 表示的时间复杂度和 auxiliary space。

答案与解答