动机
前缀码消除了拼接二进制描述时的歧义,但它本身并不能选择经济的长度。让常见符号获得较短的描述听起来合理;然而要证明某棵特定的贪心树是最优的,仅靠这种直觉是不够的。我们将找出某个最优解必定包含的一对兄弟节点,把它们收缩,然后求解规模更小的问题。
由此得到的算法就是 Huffman 编码。对于给定的有限概率分布,其输出在所有二元前缀码中使平均长度最小。这一陈述并不使最大长度最小,不保证树是唯一的,也没有计入学习并传输该分布的代价。我们还要区分无损信源压缩与信道错误的纠正。
单符号描述的长度是整数,因此其平均长度可能明显高于熵。对已知大小的分块编码会改变被编码的分布,并减小每个原始符号的超出量。该论证将证明码率结论,并揭示分块字母表的指数规模,而不是把一个巨大的存在性码本当作高效的通用压缩器。
定义
定义 3.2.1
(前缀码、字典树与平均长度)
设符号 的概率 且和为一。二元前缀码给每个符号指派有限比特串 ,使其中任何一个都不是另一个的前缀。记 ,。其字典树(trie)是以边承载比特、符号串为叶子的有根树。若 ,允许空串,其长度为零;此时解析需要符号个数或其他成帧信息。
定义 3.2.2
(满二叉树与节点权重)
对 ,满二叉树的每个内部节点恰有两个子节点,叶子承载符号。叶子的深度等于码长。节点的权重是其下所有叶子概率之和。交换符号会改变加权代价,但不改变前缀性质。
熵为 。前一章关于前缀码的内容证明了 Kraft 不等式及其逆命题:整数长度存在二元前缀实现,当且仅当 。我们使用的是这一已证明的构造,而不是假定的编码定理。下文所有算法中的权重比较都是精确的;按比特复杂度实现时,采用以二进制表示的正有理概率。
定理/命题
定理 3.2.3
(Huffman 合并规则是最优的)
反复将两个当前权重最小的节点合并为一个父节点,其权重为二者之和。从符号概率出发,最终得到单一的根。兄弟边可按任意顺序标记为零和一。所得编码在给定正概率的所有二元前缀码中使 最小。出现并列时可任意处理。
定理 3.2.4
(熵界与精确的等号条件)
设最优平均长度为 ,则
等号 成立,当且仅当每个 都是 的形式,其中 为非负整数。对于单符号信源,最优值与熵均为零。
定理 3.2.5
(独立分块逼近熵)
对于具有该分布的独立同分布信源,对全部 个长度为 的分块做 Huffman 编码,其期望分块长度 满足
在分块边界已知的情况下,可由分块码字精确恢复信源。该定理并不断言构造在分块长度上是高效的,也不处理使用相同乘积概率的任意相依信源。
证明思路或证明
把优化问题化归为有限满树
证明
(化为有限多棵满树)
从任意一棵容纳有限个符号的前缀字典树出发。删去不含任何符号的分支。若某个内部节点只有一个子节点,则收缩这条边。其所有后代码字缩短一位,且仍保持前缀无关;由于它们的总概率为正,平均长度严格减小。重复这一过程,得到恰有 个叶子的满树。
有 个叶子的满树有 个内部节点:把边数一方面记为内部节点数的两倍,另一方面记为节点总数减一,即可得出。因此其最深叶子的深度至多为 。这样的树形与符号指派只有有限多种。最优解在其中存在,并且任何非满的字典树都不能优于它。这一有限化归避免了不加证明地假定实数加权长度的下确界可以取到。
把两个概率最小的符号放在最深的兄弟对上
证明
(贪心选择与最优子结构)
取一个最深的叶子。它的兄弟必定也是叶子:若兄弟是内部节点,则它会有更深的后代。设 是两个概率最小的符号。存在某棵最优满树,可以把它们放在这对兄弟位置上。
事实上,若 当前的深度为 ,而符号 占据了所选的深度 位置,则交换二者使代价改变 。由于原树是最优的,交换后仍然最优。接着把 换到另一个最深兄弟位置;同一不等式依然适用,且不会移动 。出现并列时改变量为零,不造成任何困难。
把这两个兄弟叶子收缩为一个概率为 的单一符号。代价恰好减少 ,因为这两个符号各少一位,而其他所有长度保持不变。收缩后的树必须对合并后的分布是最优的。否则,用更便宜的合并树替换它,再把两个子节点展开,就会改进原来的最优解。
反过来,取任一最优的合并树,把其合并叶子展开为原来的两个子节点。其代价等于合并后的最优值加上 ,这与刚才确定的原问题最优值相同。因此贪心的第一次合并是安全的。对符号个数用归纳法即可证明完整的算法,以单符号的空树为基础情形。
证明透视
交换与收缩各自证明了什么
证明有两个步骤,分别回答不同的问题。交换步骤只用到 与 ;它说明的是某个最优树(而不是每个最优树)把两个概率最小的符号放在最深的兄弟位置上,而相等的情形使代价变化为零而非负数。最深兄弟对的存在用到满树性质,这由先前的化简提供:在非满的字典树中,最深的叶可能是唯一的子节点。
收缩步骤是最优子结构起作用的地方。合并兄弟叶使代价恰好减少 ,这个量与树的其余部分无关;正是这个常数平移,使最优性能够在原问题与合并后的问题之间双向传递。对 归纳即完成论证;之后的合并作用于子树权重而非原来的概率,所以交换步骤必须对每个较小的问题重新应用。
交换与收缩这一对论证,正是贪心规则安全的原因;缺少它的看似合理的贪心规则可能失败。
反例模式
自上而下的均衡划分并非最优
断言:把排好序的符号分成总概率尽量相等的两组,再递归进行,可得最优前缀码。对概率 ,最均衡的第一次划分是 对 ,总和分别为 与 。把第二组分为 对 ,得长度 ,以及
Huffman 依次合并 、、 与 ,合并权重之和为 ;其长度为 。因此均衡划分不是最优的。修正后的命题就是定理:自下而上合并两个权重最小的节点是最优的。
用合并权重给平均长度作证书
证明
(合并权重与实现代价)
所有内部节点的权重之和等于 。每个叶子的概率对其每个内部祖先各计一次,而这些祖先的个数就是它的深度。在 Huffman 构造中,内部节点的权重恰好就是各次合并所产生的权重。因此把合并权重相加,就得到一个无需列出每个码字的独立代价证书。
最小优先队列可在每次合并的对数时间内选出两个最小权重并插入它们的和,总计 次权重比较与 个树节点。这里统计的是精确的操作次数,而不是把任意精度比较的代价当作零。对于有理概率,取各输入分母的乘积作为公分母 。其二进制长度至多为各输入长度之和。所有节点的分子都是不超过 的非负整数,因此算术与比较的比特代价关于输入规模是多项式的。
写出全部显式比特串本身就可能需要二次的总输出长度:共有 个叶子,每个深度至多为 。用树来表示可避免把这一输出代价算入堆比较的次数。此处没有包含概率估计或码本传输的代价。
用 Kraft 不等式与散度确定最优值的位置
证明
(Kraft 不等式与散度)
对任意前缀码,令 ,并令 。这些 构成一个正分布。由先前已证明的散度非负性,得到
因此 。要使全程取等号,需要 且 。反之,如果各概率具有这种幂的形式,则 Kraft 逆命题给出相应的前缀长度,其平均恰为熵。于是 Huffman 最优性迫使其平均长度也是同一个值。
对于上界,使用 Shannon 长度 。它们的 Kraft 和至多为 ,且每个长度都严格小于 。因此具有这些长度的前缀码,其平均长度严格小于 。Huffman 最优解不会更差。这一界比较的是平均长度;它并不表示 Huffman 使用的正是这些取整后的长度。
把符号字母表换成已知大小的分块
证明
(独立块的熵)
对于独立分块 ,其概率为 。展开对数并对所有分块求和,得到 :每个坐标的贡献是一份 ,因为其余各坐标的概率之和为一。把刚证明的单字母表界应用到这个分块分布上,再除以 。
这一构造在分块层面是精确且前缀无关的。解码器沿分块码树行走直至叶子,输出该叶子的 个符号,然后回到根。不完整的最后一块需要填充并记录原始长度,或采用另行规定的约定。对有限文件而言,这些成帧代价并非悄悄地为零。此外,可能的分块列表有 个,因此直接做 Huffman 构造通常关于 是指数级的,尽管其超出码率趋于零。
例题详解
例题 3.2.6
(由三次合并读出最优值)
对于概率 ,先将 与 合并为 ,再将两个 节点合并为 ,最后把 与 合并为一。合并权重之和为 。一种编码是按概率从大到小依次为 ,其加权长度同样给出 。熵约为 ,故间隙为正且小于一。贪心证明确立了最优性;仅仅观察到常见符号有较短码字并不能做到这一点。
例题 3.2.7
(二进制幂分布的等号及其整数约束)
对于概率 ,编码 的平均长度为 ,恰好等于熵。相比之下,三个等概率符号的最优长度为一、二、二,平均为 ,而熵是 。没有任何三个整数码长能使这些概率取到等号,因为 不是 的倒数幂。并列的符号中,任何一个都可以得到较短的码字。
例题 3.2.8
(两符号分块改进了码率)
对于概率为 的二元信源,逐符号的前缀编码每个符号花费一比特。两符号分块的概率为 。其 Huffman 合并权重为 ,所以分块代价是 ,即每个原始符号 。这更接近熵(约 ),但仍高于它。这一收益利用了四叶分块字母表与独立性;它并非来自改变已经最优的两叶单符号树。
常见错误
即使在最优码之中,树本身也不是唯一确定的。
反例模式
最优平均长度未必决定树形
对于概率 ,并列情形下的 Huffman 合并可以得到四个深度为二的叶子,也可以得到深度为一、二、三、三的树,其中概率为 的符号位于深度一。两者的平均长度都是二。因此,最优平均长度并不固定最大长度,也不决定唯一的树。限制码长的编码问题增加了另一种约束,需要另行分析。
常见错误
(零概率符号会改变问题)
正概率是一条明确的假设。如果仍然要求零概率符号拥有不同的前缀描述,它就可能影响分配给正概率符号的长度。例如,概率为一和零时,若两个标签都必须可被解码,则仍需要两个非空码字;删去不可能出现的符号则允许空字,平均长度为零。在去掉零项之前,应先说明被编码的是哪个字母表。
常见错误
(前缀码不能纠错)
前缀无关也不是纠错。翻转一个传输比特可能选中另一条分支,并扰乱后续的符号边界。信源模型下的熵最优性不提供任何距离保证、认证,也不能防止此类更改。
练习
快速检查
(对于概率 ,求 Huffman 合并权重与最优平均长度。)
把相等的权重两两合并。
解答
把四个八分之一两两合并,得到两个四分之一,再将它们合并为二分之一,最后把两个二分之一合并。内部权重为 ,和为二。概率为二分之一的符号长度为一,每个八分之一的符号长度为三,平均长度同样为二。这些长度就是各概率的以二为底对数的相反数,所以熵的等号确认了这个值。
快速检查
(为什么把最不可能的符号放在最深处,只能证明第一次合并是合理的,而不能自动证明后面每一步贪心?)
想一想第一次合并后较小的问题必须满足什么。
解答
交换步骤确立了存在一棵含有所选兄弟对的最优原树。只有收缩论证才证明,它剩余的树对合并后的分布是最优的,并且任何最优的合并解都可以展开回去。随后用归纳法使之后所有的合并合理化,这些合并的权重是子树之和,而不是原始概率。
快速检查
(说明满树的最大深度如何能达到 ,以及这对写出全部码字意味着什么。)
数一数从根到叶的路径上的内部节点。
解答
满树有 个内部节点,从根到叶的路径不可能使用比全部内部节点更多的节点。梳状的满树可以达到深度 。因此,即使树只有线性多个节点,把 个显式字符串的长度加起来也可能是二次的;优先队列的比较次数界并不包含整个输出。
快速检查
(对于分块长度 , 至少为多大才能使已证明的超出码率小于每符号 比特?还剩下什么计算上的限制?)
使用超额界 。
解答
严格的界是超出量小于 ,所以 就已经使超出量严格小于 。分块字母表有 个可能的条目,这会使直接构造与存储不切实际。超出量很小的定理并不是实际的复杂度保证。
快速检查
(某个相依二元信源在一个初始的公平比特之后,在零与一之间确定性地交替。为什么乘积分布的分块证明不适用?)
比较块的联合分布与其边缘分布的乘积。
解答
每个坐标的边缘分布都是公平的,但长度为 的分块只有两个可能的交替字,每个的概率为二分之一。其联合熵为一比特,而不是 比特。把联合概率换成乘积、把熵换成求和的独立性步骤在此不成立。对实际的分块分布编码是另一个定义明确的问题。