从存在界到具体构造
上一个熵单元构造了期望长度比熵多不足一比特的前缀码。这是有用保证,但未必是给定信源的最短期望长度。Huffman 构造反复合并概率最小的两个符号或组,解决这个有限优化问题。我们会证明为什么局部选择能出现在全局最优解中,而不只把一个短例子当成证明。
设信源有 个必须编码的不同符号,概率 且 。这些概率描述单个符号;最小化下面的单符号目标不需要连续符号相互独立。只有当规格不要求为零概率符号提供码字时,才可省略它。
定义 6.1.1
(二元前缀码、码树与期望长度)
符号 的二元前缀码为每个 指定长度为 的有限二元字 ,并且任何码字都不是另一个不同码字的前缀。其期望长度为
若同一组符号没有任何二元前缀码的期望长度更小,则称该码对 最优。码树是有根二叉树,通往左子节点的边标 ,通往右子节点的边标 ;前缀码对应以码字为叶的树,而 就是 所在叶的深度。若每个内部节点都恰有两个子节点,则称该树为满树。
期望长度还可以用另一种方式从树上读出,而这种读法恰好描述 Huffman 算法。
概念视角组合
期望长度是内部节点权重之和
给码树的每个内部节点 指定权重 ,即 以下各叶的概率总和。则
的叶在深度 ,恰有 个真祖先,而且全是内部节点,所以 在右边恰被计算 次。Huffman 算法每次合并产生一个内部节点,其权重就是合并所得的权重,因此 Huffman 树的期望长度等于 次合并权重之和。把权重 的一对兄弟叶缩成父节点,恰好去掉一个权重为 的内部节点,其余内部节点的权重不变。
树与贪心规则
以码树表示有限前缀码。若 且概率全为正,最优树不会有只有一个子节点的内部节点:删除它并把其子树上移一条边,会严格减少加权长度。单符号时,空字长度为零;接收方必须另知符号数量,因为空比特流本身没有提供数量。
Huffman 算法从各符号的概率叶开始。只要剩下多于一棵树,就选目前权重最小的两棵,作为新父节点的子树,父节点权重为两者之和。最后为每对子边标上 和 ;由根到叶的字便构成前缀码。权重相等时可任意打破平局;不同选择可以得到不同的最优码。
为什么贪心合并安全?
最优性的证明分两个引理。第一个引理把两个概率最小的符号放到第一次合并所放的位置;第二个引理说明合并它们后,问题化为符号更少的问题,而不损失最优性。
引理 6.1.2
(两个最小概率符号可作最深兄弟)
设 且 。存在一个最优前缀码,其码树为满树,并且两个概率最小的符号标在深度最大的一对兄弟叶上。
证明
(先证存在,再作交换)
存在性。若内部节点 只有一个子节点,删除 ,并把其子树接到 原来的位置。 以下每片叶都上升一层,所以 严格减少,而各叶仍构成前缀码。因此每个前缀码都被某棵满树超过或持平。有 片叶的满二叉树有 个内部节点,所以带 片标签叶的满树只有有限多棵;其中有一棵 在这些树中使 最小,因而在所有前缀码中最优。
最深兄弟。设 为 的最大叶深度, 为深度 的叶。由于 , 不是根;由于 是满树, 有兄弟 。若 是内部节点, 以下的叶深度会大于 。故 是深度 的叶。
交换。设 为 上标签的概率,并假设 以外某片叶上的符号 满足 ;不妨设最大值在 取得。交换 所在叶与 的标签。由于 ,期望长度的改变为
所以树仍是最优的满树。每次交换都使 严格减少,而标签方式只有有限多种,所以经有限次交换后不再有这样的 。此时 上两个标签的概率都不大于其余任何概率:它们是两个最小概率 ,平局也包括在内。
第二个引理比较原问题与把两个最小符号当作一个符号所得的问题。
引理 6.1.3
(缩合最小概率的一对符号)
设 , 是两个概率最小的符号,概率 ;令 为把 换成一个概率为 的新符号 所得、有 个符号的问题。以 记最优期望长度。则
并且若 对 最优,则给叶 加上标签为 的两个子节点所得的树对 最优。
证明
(展开得一个不等式,缩合得另一个)
展开。设 是 的任一棵树, 在深度 。给 加上子节点 ,得到 的一棵树,其期望长度为 。因此 。
缩合。由上一引理,存在 的最优树 ,其中 是深度 的兄弟叶。把它们换成其父节点,即深度 、标签为 的叶,得到 的一棵树,期望长度为 。因此 。
两个不等式合起来给出 。若 对 最优,其展开的期望长度为 ,所以它对 最优。
有了两个引理,定理便可对符号数归纳得出。
定理 6.1.4
(合并最小两项的最优性)
对概率全为正的有限信源,此规则产生的树在所有二元前缀码中使期望长度最小。 时,树只有根,码字为空字。
证明
(对符号数归纳)
时,任何字的长度都至少为零,所以空字最优,而 Huffman 算法只返回根。
设 ,并假设定理对 个符号成立。第一次合并把概率最小的两片叶 (概率 )合在一起。此后算法把合并所得的树当作权重 的单一项,所以其余 次合并恰好是 Huffman 算法在 上的一次运行,平局选择也相同。该运行给出 的树 ,而 的最终树就是把 的叶 展开成 。 有 个正概率且总和为一,故由归纳假设 最优,再由缩合引理,其展开对 最优。两个引理对两个最小概率的任何选择都成立,所以证明不依赖特定的平局规则。∎
证明透视
各个条件在归纳中的位置
有限性只用了一次:保证使 最小的满树存在;没有它,交换步骤便没有可以修改的最优解。正概率使删除单子节点成为严格改进,所以每棵最优树都是满树;后面的步骤其实只需要“某棵最优树是满树”,而这在权重可为零时仍然成立,因为删除单子节点从不增加 。
不明显的一步是交换。它并没有说每棵最优树都以 为最深兄弟,而是修改某一棵最优树直到如此。正是这一棵树提供缩合不等式 ,而任意树的展开提供相反的不等式。单凭其中一个方向,都不能证明 Huffman 树最优。
归纳之所以能闭合,是因为缩合后的问题仍是概率全为正且总和为一的信源,只是少了一个符号;而且 Huffman 在 上第一次合并之后的运行,正是 Huffman 在 上的运行。若某规则不能化为同一规则在较小问题上的运行,例如下面反例中的自顶向下分割,这个论证就帮不上忙。
证明讨论的是树本身;构造树的代价则取决于存放当前各树的数据结构。
命题 6.1.5
(用二叉堆实现的运行时间)
假设权重的比较与加法为单位代价。若用按权重排序的二叉堆优先队列存放当前各树,Huffman 算法对 个符号在建堆后进行 次合并及 次堆操作,总时间为 。
证明
(统计堆操作)
用自底向上的堆化建立 片叶的堆需时 。每次合并使树的数目减一,所以恰有 次合并。每次合并用两次取最小值及一次插入,由于堆内元素从不多于 个,每次操作需时 ,而建立父节点需时 。总计为 。最后遍历 个节点,可在 时间求出所有深度;若要逐一写出每个码字,则需 次比特操作,对极度偏斜的信源可达 的量级。
精确有理数权重及其编码可能需要另作比特复杂度分析。每次重新排序或扫描当前各树的直接实现可有不同操作次数。
四个符号的例子
例题 6.1.6
(概率各不相同的四个符号)
令 的概率为 。先合并 得 ;此时最小的两项是这个组与 ,都重 ,合并得 ;最后与 合并。一组标记是
长度为 ,因此每符号期望长度 比特。合并权重给出同一数值:。熵约为 比特。相反,将各 分别向上取整,得到长度 ,期望长度 。两种方法都产生前缀码;熵构造的近最优界并没有说它的具体长度必定最小。
译码器沿边走到叶便输出符号并回到根。例如 可解析为 ,即 。这假设码树已知、比特流完整而有效;传送码树、消息分帧和处理比特损坏是额外代价或问题。
第二个例子说明平局能改变什么、不能改变什么。
例题 6.1.7
(改变长度分布的平局)
令 的概率为 。第一次合并是确定的: 合成 。此时有三棵树都重 ,即 、 和 。
若把 与 合并,权重变为 ;再把 与 合并得 ,最后根把它与 连接。长度为 ,。
若改为把 与 合并,权重变为 ;再把 与 合并得 ,最后根把它与 连接。长度为 ,。
两次运行都合规,由定理两者都最优,期望长度也相同,但长度的多重集不同:一个最长码字有四比特,另一个只有三比特。单是交换左右边的标签,已能改变码字而不改变任何长度。最优性指期望长度,不代表比特分配唯一,也不代表长度分布唯一。
最后一个例子涵盖与熵比较时的两个极端。
例题 6.1.8
(二进分布信源与偏斜的双符号信源)
对 ,各次合并权重为 、 和 ,所以 比特,长度为 。此时每个 ,所以 恰好等于熵 比特。
对 及 ,唯一的合并给出长度 ,所以 比特,而
Huffman 码仍然最优:两个必须编码的符号,任何前缀码的两个长度都至少为一。将近一比特的差距,是逐个符号以整数比特长度编码的代价,并非贪心规则失效。
常见错误
一个看似合理的替代做法,是由根向下而非由叶向上建树。
反例模式
平衡的自顶向下分割并非最优
断言:把符号按概率排序,将列表分成两段相连、总概率尽量相等的部分,两部分的首比特分别为 和 ,再递归处理;所得的码最优。取 的概率为 。顶层分割是 ,总和为 与 ;其他分割的差分别为 和 。接着 分成 ,差为 ,另一种分割的差为 。长度为 ,。Huffman 依次合并 、、,最后 ,得到长度 及 。自顶向下规则背后没有交换与缩合的论证;有最优性保证的是自底向上合并两个最小权重。
另外两个错误,涉及合并规则如何应用,以及它的最优性承诺了什么。
常见错误
(把每个新组都与下一个符号连接)
四符号例子中,合并所得的组恰好每次都与下一个符号合并,但这不是规则。合并后的权重要放回候选之中。对四个概率均为 的符号,链状连接给出长度 及 ;Huffman 则分别合并两对,给出长度 及 。
常见错误
(平均最优不等于每条消息最短)
Huffman 码最小化的是每符号的期望长度。个别消息可以比用另一个码时更长:用四符号码, 需要 比特,而固定两比特码只需 比特。平均而言 Huffman 码仍然更短,每符号 比特对 比特。
练习
快速检查
(对概率 执行合并,求期望长度。)
解答 · 答案
先合并两个 ,再与 合并。长度为 , 比特;由于信源是二进分布,这正好等于熵。
快速检查
(为什么单符号信源在空字惯例下期望长度为零?译码另需什么信息?)
解答 · 答案
唯一的叶是根,故码字长度为零。接收方需要另行指定符号数;单靠空比特流无法得知数量。
快速检查
(用上面的四符号码译码 。)
解答 · 答案
解析为 ,得到 。
快速检查
(若概率 的两个符号被放在深度 ,交换标签后期望长度改变多少?)
解答 · 答案
新长度减旧长度是 。把较小权重移得更深不会增加目标值。
延伸阅读
MIT OpenCourseWare:Huffman Codes 与 CMU:Introduction to Data Compression 讨论最优前缀编码。