把编码看成带权树
设 个不同符号的权重 均非负。我们希望为符号指定比特串,使常用符号得到较短的串,同时让每段编码消息都能从左到右唯一解码。
定义 5.1.1
(前缀码与加权长度)
二元前缀码为每个符号指定有限比特串,任何码字都不是另一码字的前缀。它的二元 trie 以叶节点表示各符号,符号 的叶深 就是其码字长度。该编码(或其树 )的加权长度为
我们要在二元前缀码中最小化此和。若权重是概率,它是每符号的期望比特数;若是出现次数,它是总加权长度。问题假设符号权重已给定,并未计入传送码本的成本。此处排除单一符号的约定:应用须另外指定是否允许空码字。
为何最小的两个权重可以是兄弟
定义 5.1.2
(满二叉树)
若二叉树的每个内部节点都恰有两个子节点,就称为满二叉树。
任何前缀码树都可化为满二叉树。若某内部节点只有一个子节点,绕过该节点;其后代深度都减一,因权重非负,成本不会增加。重复后得到相同叶节点的满二叉树。对固定 ,满二叉树形状及符号配置只有有限种,因此存在最优满二叉树。有 个叶的满二叉树有 个内部节点。
引理 5.1.3
(两个最小权重可作最深的兄弟)
设 为两个符号,且对其余每个符号 都有 。则存在某棵最优满二叉树,使 成为位于最大深度的兄弟叶。
证明
(交换标签)
取一棵最优满二叉树。若较轻的叶比较重的叶浅,交换两者标签使成本改变 ,因此不会增加成本。
最深的叶有一个同为叶的兄弟:因为树是满的,兄弟存在;若它是内部节点,就会有更深的后代。设 为最大深度 的一对兄弟叶。交换 与 处符号的标签。由于 权重最小而 已最深,成本不增加。接着交换 与 处符号;此时 在 以外的符号中权重最小,成本同样不增加。两次交换后 是深度 的兄弟,而成本仍是最小,所以此树最优。
引理 5.1.4
(收缩一对兄弟叶)
设 为满二叉树,其中叶 为兄弟;删去它们,并把它们的父节点视为权重 的新叶 ,得到 。则 。反过来,缩减权重下任何以 为叶的树 都可展开成这样的 。
证明
(只差一层深度)
设父节点深度为 。在 中 的深度为 ,贡献 ;在 中 贡献 。其他叶在两棵树中的深度相同。相减即得等式。把任何树 的叶 展开为标记 的两个子节点,就是逆运算。
定理 5.1.5
(霍夫曼合并法则最优)
反复合并当前两个最小权重的项目,以权重为其和的一项取代,直至只剩一项。如此建成的树在所有二元前缀码中使 最小,不论以何种固定规则打破平手。
证明
(对符号数作归纳)
时,唯一的满二叉树有两个深度为 的叶,合并步骤恰好建出它。
设 ,并设 是第一次合并所合并的两项;因为合并取的是两个最小权重,它们满足第一个引理的假设。令 为该过程对缩减权重(以 取代 )所建的树;由归纳假设, 对缩减问题最优,成本为 。该过程对原权重所建的树 就是展开 后的 ,故由第二个引理 。
由第一个引理,某棵最优树 以 为兄弟。收缩后得到缩减权重的树 ,故 ,且
由于 最优, 也是最优。
证明透视
为何安全的第一步已经足够
证明的两半用到不同的假设。交换部分只用到一次权重非负,就是绕过单子节点而不增加成本,从而化为满二叉树;满性保证最深叶必有同为叶的兄弟。交换本身只用到权重的次序: 与 使乘积 不为正。收缩部分对权重不作任何假设,它只是关于深度的等式。
关键一步是把“选择”与“求解”分开。交换引理说明贪心选择,即把两个最小权重放在最底部,是安全的:某棵最优树包含这个选择。收缩等式再说明其余部分是少一个符号的同一问题,成本只相差固定的 ,所以优化其余部分就是优化缩减问题。
论证由两叶的基础情形出发,对 归纳收尾。平手不费分毫,因为第一个引理对任何一对最小权重成立,而不只对某一对。论证会失效之处是第一个引理:合并不是最小的两项,会破坏 ,下面的合并次序例子正要付出代价。
从各符号的单叶树开始,反复合并最小两个权重便构造这样的树。最后一次合并得到一个根;其左右边可以任意次序标为 和 。每个符号在其叶节点解码,故没有码字是另一码字的前缀。
概念视角组合
成本是内部节点的权重之和
深度为 的叶恰有 个真祖先,全是内部节点。把每片叶的权重对它的每个祖先各计一次,得到 ,对所有内部节点 求和,其中 是 之下所有叶的权重总和。每次合并产生一个内部节点,其权重就是合并后的权重,所以成本等于所有合并权重之和。收缩一对兄弟叶恰好移除一个权重为 的内部节点,这就是收缩恒等式。
例题
例题 5.1.6
(合并过程的跟踪)
令 的权重为 。贪心法先把 合并成 ;此时最小的两项是 ,合并成 ;然后 合并成 。一组所得码为
其加权长度为 。等价地,每次合并对总和增加其合并权重,得到 。注意 是根的权重,不是成本。
反例模式
并非每个合并次序都最优
先合并 和 得 ,再把原来的 与这个 合并得 ,最后把权重为 的原符号 与 合并。合并权重之和为 ,所得前缀码合法,但成本是 而非 。直接计算: 深度为 , 深度为 , 深度为 ,成本为 。合法前缀树本身不足以证明最优性:每次合并都必须取两个最小权重。
例题 5.1.7
(平手会给出不同的最优树)
设权重为 。第一次合并把两个 合并成权重 ,余下三个权重为 的项。若合并两个原来权重为 的符号得 ,再把 与 合并,合并权重为 ,每个符号深度均为 :。若改为把新项与一个权重为 的符号合并得 ,再与另一个符号合并,合并权重同样是 ,但深度变为 :。两棵树都最优,码字长度却不同。
例题 5.1.8
(最小的例子,含零权重)
设 ,权重为 和 。只有一次合并,权重为 ,码字为 和 ,加权长度为 。零权重的符号仍然有码字,成本与其深度无关。这就是归纳的基础情形。
算法成本与范围
命题 5.1.9
(时间与空间)
使用最小优先队列,为 个符号建树需 次插入,以及 轮(每轮取出两项并插入一项)。在权重比较及加法为常数时间下,需 时间及 个存储节点与队列项。
证明
(计算队列操作次数)
初始有 次插入,而 次合并各作两次取出及一次插入,所以队列操作合计 次。在堆上每次花 ,总计 。树有 个叶及 个内部节点,存储量为 。
输出全部码字还需与输出总长度成比例的时间,该长度可以超过 。有限精度溢出、码本元数据及无限数据流编码是另行处理的实现问题。
常见错误
常见错误
(把根的权重当作成本)
根的权重是全部符号的权重总和,在上面的跟踪中是 。成本是所有内部节点权重之和,这里是 ,等价于各叶的权重乘深度之和。
常见错误
(总是把下一个最小符号接上去)
合并出来的节点与符号同在队列中竞争。反复把最小的未用符号接到不断增长的子树上,形成梳状树,并不是霍夫曼(Huffman) 法则。对四个权重均为 的符号,梳状树的深度为 ,成本是 ;先把符号两两合并,深度为 ,成本是 。
权重非负用于化为满二叉树,下面的例子说明这项假设不能随便放弃。
反例模式
负权会破坏合并法则
取权重 ,它们不符合非负的假设。合并法则把 与 合并成 ,再把 与 合并成 ,成本为 。直接计算:未合并的 在深度 ,其余在深度 ,得 。但前缀码 以 、、 合法,成本为 ,更小。权重为负时,深的叶可以有利,绕过单子节点也不再安全。修正后的陈述就是上面所证的:权重必须非负。
习题与解答
快速检查
(0 和 01 能同时是前缀码的码字吗?)
逐个字符比较这两个串。
解答 · 答案
不能;0 是 01 的前缀。
快速检查
(合并权重 及 的叶时,以什么权重取代?该次合并对加权长度贡献多少?)
使用收缩等式。
解答 · 答案
父节点权重为 ,该次合并对加权长度贡献 。
快速检查
(若两个权重相等,最优码的比特串必定唯一吗?)
想想交换某节点的两个子节点。
解答 · 答案
不必。平手及交换左右子节点可得到不同的最优码,而加权成本仍最优。
快速检查
(有些权重为零时,为什么仍可绕过单子节点?)
比较缩短前后的成本。
解答 · 答案
权重全部非负,缩短后代的码字不会增加总和;有零权重时成本可以不变。