动机
二元前缀码为每个符号指派一个比特串,使得没有任何码字是另一个码字的前缀。常用符号应获得较短的码字,但前缀条件限制了哪些长度可以同时出现。霍夫曼(Huffman)算法反复合并两个最小权重,再从所得的二叉树中读出码字。
贪心选择并不能仅凭“小权重似乎适合放在较深的叶子上”就得到证明。证明必须说明:存在某棵全局最优树,使两个最小权重成为最深层的兄弟叶子;并且收缩这对兄弟之后,剩下的较小问题仍然是最优的。
定义
定义 2.7.1
(前缀码与霍夫曼算法)
设有 个符号,其非负权重为 。二元前缀码为各符号指派互不相同的有限二进制串,使得没有任何码字是另一个码字的前缀。其代价为 ,其中 是符号 的码字长度。一个码对应于一棵二叉树的带标号叶子:左、右边分别标为零和一,叶子的从根到叶的边标号即为其码字。
当 时,霍夫曼算法反复取出两个最小权重的节点,建立其父节点(权重等于二者之和),并将其重新放回。当只剩一个节点时,将每个内部节点的两条子边分别标为零和一。当 时,本单元允许空码字,代价为零。若通信格式要求码字非空,或并不另行知道符号个数,则属于另一种约定。
定理
定理 2.7.2
(贪心兄弟性质)
当 时,存在某棵代价最小的二元前缀码树,使两个最小权重是位于最大深度的兄弟叶子。
定理 2.7.3
(霍夫曼最优性)
对于非负权重,在所述约定下,霍夫曼构造给出代价最小的二元前缀码。对 ,使用带索引的最小堆可在 时间和 空间内构造码树;若要显式写出全部码字,则额外需要与码字总长度成正比的时间。
证明思路或证明
证明
(交换与收缩)
码树可以在不增加代价的前提下化为满树,即每个内部节点都有两个孩子:收缩一个只有一个孩子的内部节点,并缩短其下方的码字。由于权重非负,缩短码字不会增加加权代价。在具有 个带标号叶子的满树中存在最小者,因为这样的树形与标号方式只有有限多种。
在满树中,最大深度的叶子的兄弟也是叶子;否则该兄弟会有更深的后代。若较轻的权重占据的叶子比较重的权重所占的更浅,则交换两者不会增加代价。事实上,对权重 与深度 ,把 放到深度 、把 放到深度 后,代价的变化为 。反复交换可使两个最小权重在某棵最优树中位于最深的兄弟对。
设这两个权重为 。把它们的兄弟叶子收缩成一个权重为 的叶子。其他所有深度不变,而原来的两个叶子都比收缩后的叶子低一层。因此原来的代价等于收缩后树的代价加上 。若收缩后的树对于较小的权重多重集并非最优,则将其换成代价更低的树,再把合并出的叶子展开为两个孩子,就会与原树的最优性矛盾。反之,展开一棵较小的最优树,代价恰好增加 。对 作归纳即证明:霍夫曼的最小权重合并序列是最优的,包括出现并列与零权重的情形。
二元最小堆存放当前的权重。 次合并中,每次进行两次取最小值操作和一次插入,每个操作耗时 ;插入初始权重至多耗时 。该树有 个叶子和 个内部节点,故存储量为 。边的标号可在之后再指派。
证明透视
交换与收缩扮演不同的角色
交换说明贪心选出的那一对可以同时出现在某棵最优树中。收缩说明该最优树的其余部分解决的是一个较小的实例。归纳需要这两步缺一不可。
非负性只在第一步使用:缩短只有一个孩子的内部节点时,代价不可上升。交换不等式 只用到权重的大小次序,而收缩恒等式对任何权重都精确成立。任何一对兄弟叶子都满足收缩恒等式;交换论证保证的是,位于最深兄弟位置的两个最小权重会同时出现在某棵最优树中。
例题详解
例题 2.7.4
(四个权重)
对权重 ,先合并 ,再合并 ,最后合并 。所得码长可以是 ,代价为 。各次合并的权重之和同样是 。
例题 2.7.5
(并列可以改变编码)
当四个正权重全部相等时,最先被选中的两个符号可以是任意一对。不同的并列选择和左右标号会产生不同的码字,但每个霍夫曼结果都具有相同的最优加权代价。
例题 2.7.6
(零权重)
对权重 ,先合并 与其中一个单位权重,再把所得结果与另一个单位权重合并。两个正权重的深度分别为二和一,所以代价为三。零权重的符号仍然被分配到一个互不相同的前缀码叶子。
常见错误
反例模式
负权重使最小值消失
断言:霍夫曼构造对任意实数权重都最优。取两个符号,权重为 与 。霍夫曼算法使两个码字长度都是一,代价为 。但若权重 的符号取码字 0,权重 的符号取由 个一组成的码字,这是合法的前缀码,代价为 。当 增大时代价没有下界,所以不存在最小代价的码。可见非负性是必要的:它使收缩只有一个孩子的内部节点是安全的,并使代价有下界。
常见错误
(独立地选取短码字)
字符串 0 与 01 不能同时作为前缀码的码字,因为 0 是 01 的前缀。若逐个挑选看似最短的可用字符串,而不检查整棵树,就可能得到无效的码。应从同一棵二叉树的叶子读出码字,这样任何码字都不会是另一个的前缀。
常见错误
(以为每棵最优树都使用被合并的那一对)
证明所找到的是包含合适贪心兄弟对的一棵最优树;它并没有说当权重并列时,每棵最优树都必须使用完全相同的那一对。
单个符号时采用空码字的约定必须明确说明,因为某些实际格式要求码字非空。
前缀码与树
二元码字描述从根出发的一条路径。若一个码字是另一个码字的前缀,则其路径会终止于另一个码字所在叶子的祖先。因此前缀码树的所有码字都位于叶子。反过来,在任何二叉树中,通向不同叶子的路径不可能互为前缀,所以给两条子边标上不同的比特即得到前缀码。
含有只有一个孩子的内部节点的树可以缩短:移除该节点,把其孩子直接接到其父节点上;若该节点是根,则把孩子移为根。该子树中所有叶子的路径各少一个比特,前缀自由性仍然成立。在权重非负时,这不会增加代价。若该节点下方所有权重都为零,代价可能保持不变;证明只需要存在一棵满的最优树,而不要求每棵最优树都是满的。
具有 个叶子的满二叉树有 个内部节点。一种证明是数边:每个内部节点有两个孩子,共 条边;而含 个节点的有限树有 条边。故 。这种有限性使得我们可以合理地选取一棵最优的满带标号树,即使定义中并未限定码字长度的上界。
例题 2.7.7
(更长的合并序列)
对权重 ,霍夫曼先合并 ,再合并 ,最后合并 。加权代价为 。一棵树的深度为 ,代价为 。两种计算相符。
含并列情形的交换论证
固定一棵最优满树和一对最深的兄弟。若两个最小权重之一尚未在该对中,就把它与占据这些最深叶子之一的权重交换。较小的权重移到不小于原来的深度,较大的权重则移到原来的深度。证明中的代数计算表明这不会增加代价。对另一个最小权重重复同样的操作,同时要保证第一个权重仍然留在最深的兄弟叶子上。
所得的树的代价不超过一棵最优树的代价,因此它也是最优的。若某些权重或深度相等,交换可能使代价保持不变。这已经足够:定理断言的是存在包含所选这一对的最优树,而不是所有最优树都含有这一对。正是这种存在性的表述,使得贪心算法在出现并列时可以任意选取两个最小权重。
收缩之后,合并得到的权重代表该叶子之下的总权重。位于它之上的每一个额外层级,对原来的两个叶子各计算一次,因而贡献它们的和。展开该叶子会使两个原符号各加深一层,并使代价恰好增加 。这个恒等式与收缩后的叶子在较小的树中处于何处无关。
为什么合并权重之和等于代价
概念视角结构
代价等于内部节点权重之和
每次合并产生一个内部节点,其权重是其子树中所有原叶子权重之和。把整棵霍夫曼树的这些内部节点权重相加。权重为 的叶子对其每个祖先所对应的内部节点权重恰好贡献一次,而祖先的个数等于其深度 。因此合并权重之和等于 。
这一恒等式提供了计算已构造的树的代价的独立方法。它本身并不能证明最优性:不同的合并序列同样有各自的内部权重之和。交换与收缩的证明才说明了,为什么每一步都选取两个最小权重,能在所有有效的码树中使该和最小。
左右边具体被指派的比特不会改变码字长度或代价。但它们会影响实际的码本,所以编码器与解码器必须使用同一棵带标号的树,或约定好的规范表示。这里的数学优化问题只涉及加权长度;传输码本、消息分帧以及处理被破坏的数据流是另外的问题。
输出与复杂度
堆的分析在 的堆操作时间内构造出具有 个节点的树。若要求的输出是每个叶子的显式比特串,则写出这些字符串所需时间与 成正比。满二叉树的深度可以高度不均,因此输出长度可能超过 。若把仅仅堆的时间界当作打印所有码字的时间,就忽略了输出的规模。
证明假设所给权重可以被精确比较和相加。若权重是有二进制编码的有理数,实现必须正确表示并比较和;对于任意表示方式,单纯统计堆操作次数本身并不是完整的比特复杂度分析。负权重被排除在外:缩短负权重的码字可能增加目标值,所以满树化约不能用同样的论证得出。
当 时,在这一数学约定下,空字是唯一的叶子路径,代价为零。对于单符号字母表它是前缀自由的,但一串空码字在没有外部分帧的情况下无法表明发送了多少个符号。若某种格式要求每个符号一个比特,则其受约束的最优解不同。这是建模上的选择,而不是隐藏在贪心证明中的例外。
检验给定的码
检验一个给定的码时,首先确认所列出的码字中没有任何一个是另一个的前缀。然后根据给定的权重和码字长度计算加权长度。对于由霍夫曼算法产生的树,合并权重之和是一个有用的算术交叉检验。代价低的有效前缀码不一定是最优的;最优性来自贪心兄弟与收缩定理,或者来自单独的下界证书。
若权重表示概率,它们的和可以为一,但归一化对优化并非必要:将每个权重乘以同一个正常数,会使每个码的代价同比例缩放,不会改变哪个码是最优的。零权重是允许的,算法仍会为列出的每个符号构造码字。证明把权重当作非负的代价,不假设任何随机模型。
对概率而言,最优平均长度与熵相差不到一个比特。
自然的下一个问题
前缀码最接近熵有多近?
对概率而言,最优平均长度与熵相差不到一个比特。
若权重是概率 ,最优二进制前缀码的平均长度 满足 ,其中 。上文的权重 对应概率 ,于是 ,下界恰好取到。对概率 ,则 而 ,可见差距可以接近一个比特。
总结
存在满的最优树,可把两个最小权重放在最深的兄弟叶子上。收缩这一对会缩小问题,并使代价改变它们的和。重复这种安全的合并,即得到最优的前缀码树。
练习
快速检查
(两个符号的权重为 和 ,其霍夫曼代价是多少?)
解答 · 答案
两个码字的长度均为一,所以代价为 。
快速检查
(为什么在有限满树中,最深叶子的兄弟不可能是内部节点?)
解答 · 答案
若兄弟是内部节点,它就会有比所选最大深度叶子更深的后代叶子。
快速检查
(合并权重 与 所产生的父节点被指派什么权重?)
解答 · 答案
父节点的权重为 。
快速检查
(为什么证明允许出现并列?)
解答 · 答案
交换与收缩论证使用的是非严格不等式,所以在相等的最小权重之间任意选择,都可以在某棵最优树中使用。