规范Huffman码与码长表

想象按字典序摆放二叉树的叶。先分配较浅的叶，它的整棵后代就不能再用。进入下一层时，每个剩余空位分裂成两个位置，所以空位数先乘二，再扣掉本层叶数。上面的 $r_b$ 是树空间的整数账本，不依赖浮点数近似求和。

首码递推也来自同一动作：长度 $b-1$ 的连续码用完后，紧接着的位置是 $N_{b-1}+c_{b-1}$；进入深一层相当于在末尾补零，因此乘二。已占用的浅层子树都落在这条前沿左侧，新码不会落进它们。归纳得到码字互异且没有前缀冲突。

这一证明是Kraft可行性理路Kraft–McMillan 不等式Kraft–McMillan inequality刻画给定码长集合存在前缀码或唯一可译码的必要充分不等式。的具体构造。展开递推可得 $r_B=2^B(1-\sum _s{2}^{-\ell (s)})$。本页把存在性转成“收到一张表后怎样恢复完全相同的bit映射”，而Huffman旧页继续承担最优性的交换证明。

给五字节 ABABA 加专用结束符EOF，EOF不是正文字符，它的编号为256。字节A、B分别编号65、66，顺序固定为 $65<66<256$。出现计数为 $(3,2,1)$；合并1和2得到3，再合并两项3，获得长度 $(1,2,2)$。

于是 $c_1=1,c_2=2$；首码 $N_1=0,N_2=(0+1)2=2$。结果是 A→0，B→10，EOF→11。发送 A B A B A EOF，有效位为 0|10|0|10|0|11 = 010010011。读者从根开始逐位走，分别在第1、3、4、6、7、9位输出A、B、A、B、A、EOF；末两位是结束符，不能当成正文。

收到长度 $(1,1,1)$ 时，第一层 $r_1=2-3=-1$，建树之前拒绝。长度 $(2,2)$ 则给 00,01，合法但不完整；输入以 1 开始会走进未用区域，应报告非法码流，不能补出一个默认符号。表里两条记录使用相同符号编号也必须拒绝，即使长度的Kraft和不大于一。

空文件仍要结束。本单元规定仅有EOF时给它长度1、码字 0，不采用零长度码。只有一个正文符号A的文件实际有A和EOF两个符号，所以码字为 0,1，可恢复重复次数。本教学文件的码长上限是15；普通Huffman建树若超过15，编码器明确拒绝，不能剪掉高位，也不能宣称自己实现了长度受限Huffman优化。

双方只交换“符号、长度”即可恢复码字，不需要交换每条根到叶路径。若符号表有 $m$ 项，已按符号顺序给出，计数、首码和整数码表的构造需 $O(m+B)$ 次整数操作；若另外输出全部码字字符串，还要支付 $\mathrm{\Theta }(\sum _s\ell (s))$ 位的写出成本。排序未给定的表则另计 $O(m\log m)$。

规范码经常用于真实压缩格式，但位序属于封装协议。RFC1951的DEFLATE把数据元素放到字节的低位起始位置，Huffman码字自身又按高位先出；本单元的教学文件统一按每字节高位先出，二者不能直接混读。完整表头、结束和填充规则见压缩流封装理路压缩流封装与完整成本Compressed stream framing · 压缩文件的终止与填充把模型、有效位、EOF、guard和字节填充写成可检查文件语法，核算短文件的实际总长及拒绝路径。；检查器还用独立枚举空闲叶的方法检查340张小码长表。

需要保证最大码长时，可以先用package-merge理路最大码长约束下的package-mergeLength-limited prefix code · Length-limited Huffman coding · Package-merge · 限长前缀码将最大码长的最优前缀码归约为二进制硬币选择，以配对归并和nodeset闭合证明最优长度并保留符号身份。得到保留符号身份的最优限长表，再应用本页同一首码递推。它补足的是选长度的优化步骤；这里已有的正码长、Kraft空槽、符号顺序和物理位序检查不变。既有HUF1编码器仍按其原规则在普通Huffman长度超过15时拒绝，并未隐式切换优化器。