最大码长约束下的package-merge

普通Huffman算法理路Huffman 编码Huffman coding反复合并最低概率符号构造期望码长最小前缀码的算法。可以不断把最轻项推向更深层；但存在最大深度后，最深层的位置变成有限资源。package-merge在每个允许深度上放置一份“再增加一层码长的费用”。是否给某符号增加一层，不能独立决定：物品宽度必须合成同一个总数。

配对归并为什么优化硬币问题 ​

更一般地，设物品宽度均为2的整数次幂，目标宽度为 $X$，最小现有宽度为 $a$。所有更大宽度都是 $2a$ 的倍数。如果 $X/a$ 为奇数，合法选择必须含奇数个宽度 $a$ 的项，至少一个；交换同宽物品可让某个最优解包含其中最轻项，先取它并将目标减 $a$。如果目标为 $2a$ 的倍数，则必须选偶数个最细项。

固定要选的数目 $2k$ 后，同宽交换使所选项可取为最轻的前 $2k$ 个，即从最轻开始的 $k$ 对。于是相邻两项可以绑定成“同进同出”的包，在下一宽度层继续优化；最重的奇数余项不可能进入这种最轻偶数前缀。包的权重保持排序，因为相邻对的两项都不重于下一对的对应项。归纳到更大宽度，配对和归并都不改变最优值，最后回溯展开包即可。

本问题 $X=n-1$ 是整数。宽度小于 $1/2$ 时，$X$ 总是该宽度的偶数倍，所以各层只需配对；到 $1/2$ 时选择恰好 $2n-2$ 项即可。不必运行穷举或动态规划来替代配对算法。

为什么所选物品真的给出合法码树 ​

第一步是从树到物品。正权重最优前缀树不含单孩子内部节点，否则收缩该边会减少成本且不会破坏上限。因此可以选满二叉树，Kraft和等于1。若叶 $i$ 深度为 ${\ell }_i$，选它的 $(i,1),\dots ,(i,{\ell }_i)$，则

因此硬币最优值不大于最优树成本。但这还没有证明反向转换，需要排除一个符号“选了深层却漏了浅层”的非法集合。

二进制余量引理。 若一组二进制宽度物品的总宽为 $k{2}^{-h}+r$，$k$ 为非负整数，$0<r<2^{-h}$，则有子集宽度恰为 $r$。按物品数归纳：最小宽度 $a$ 必小于 $2^{-h}$，否则总宽没有这个余量；$r$ 也是 $a$ 的整数倍，故 $a\le r$。若 $a=r$ 取此项；否则删掉此项，对余量 $r-a$ 应用归纳，再把它放回。

现在若最小代价nodeset $A$ 包含 $(i,j)$、$j>1$，却不含 $(i,j-1)$，将前者换成后者得到 $A^{\prime }$，成本不变，宽度从整数 $n-1$ 增为 $n-1+2^{-j}$。对基准宽度 $2^{-(j-1)}$ 应用余量引理，能从 $A^{\prime }$ 删掉总宽恰为 $2^{-j}$ 的非空子集，重新得到宽 $n-1$，而正权重保证成本严格降低，矛盾。故每个符号的所选层连续地从1开始。

令 ${\ell }_i$ 为所选层数，包括可能的0。于是同一几何级数公式给出 $\sum _i{2}^{-{\ell }_i}=1$。若有 ${\ell }_i=0$，它本身贡献1，其余 $n-1$ 个有限长度各贡献正数，与等式矛盾。因此全部 $1\le {\ell }_i\le L$。由Kraft充分性理路Kraft–McMillan 不等式Kraft–McMillan inequality刻画给定码长集合存在前缀码或唯一可译码的必要充分不等式。存在相同长度的前缀树；其成本等于硬币最优值，所以也等于限长树的最优值。该证明甚至不需所有原权重互异；微扰只是确定一个可复现的最优答案。最后用规范码长表理路规范Huffman码与码长表Canonical Huffman code · 规范赫夫曼码从带符号的码长表唯一重建码字，以整数空槽检查拒绝过订长度，并逐位解出含EOF的短流。恢复具体码字，不重新优化长度。

权重按符号A至F为 $(1,1,2,3,5,8)$，令 $L=3$。只列主权重，实际仍保留符号和层身份：

• 层3原始表：1,1,2,3,5,8；配成 2,5,13
• 层2将这些包与六个原始项归并：1,1,2,2,3,5,5,8,13；再配成 2,4,8,13，剩余13丢弃
• 层1归并：1,1,2,2,3,4,5,8,8,13；恰取全部10项，总宽 $10/2=5=n-1$，代价47

回溯选中层1、2的全部六个符号，以及层3的A、B、C、D。所以长度是 $(3,3,3,3,2,2)$，成本

Kraft和 $4/8+2/4=1$。规范化得到 A=100,B=101,C=110,D=111,E=00,F=01。每个符号出现 $w_i$ 次的20符号消息正文恰47bit；传表和终止仍须另计。

普通Huffman的一组最优长度是 $(5,5,4,3,2,1)$，成本45，却超过限制。把过长项直接截成3得到 $(3,3,3,3,2,1)$，Kraft和 $4/8+1/4+1/2=5/4$，连可译长度都不是。优化不是逐项裁剪。

独立穷举每个 ${\ell }_i\in \{1,2,3\}$ 并检查整数Kraft条件，共有22个可行长度向量；47的最优向量唯一。这是核对实现的独立oracle，不是正文算法，也不是最优性的普遍证明。两个等权符号交换码字仍可产生不同树，“长度向量唯一”不表示所有标边方式唯一。

$L=2$ 时六符号不可能；$L=4$ 时本确定规则输出 $(4,4,3,2,2,2)$，成本46，共有3个最优长度向量；$L=5$ 恢复成本45。增加上限只扩大可行集，所以最优值不增，不能声称每次一定严格降低。等权 $(1,1,1)$、$L=3$ 有三种最优长度向量，本实现确定输出 $(2,2,1)$，成本5。

复杂度应包含排序、包树和输出 ​

初始排序 $O(n\log n)$，每层原始项是同一排序的复制。列表长度递推 $a_{j-1}=n+\lfloor a_j/2\rfloor <2n$，所以每层配对及双指针归并 $O(n)$，共 $O(nL)$。所存原始项和包节点为 $O(nL)$；回溯只访问所选包树，每个原始物品唯一、每个节点至多一个父包，总访问 $O(nL)$。故本版本时间 $O(n\log n+nL)$、空间 $O(nL)$，不把论文另外的线性空间重算技术算作已经实现。

重建长度数组另需 $O(n)$；规范码的整数表在符号顺序已知时用稳定码长桶构造，需 $O(n+L)$，检查器也采用此方法，若写出每条完整bit串还要 $\mathrm{\Theta }(\sum _i{\ell }_i)$，最坏 $O(nL)$。若权重是大整数，比较与加法还须计位复杂度。检查器限制 $n\le 256,L\le 32,1\le w_i\le 2^{32}-1$，任一包的主成本小于 $nL{2}^{32}\le 2^{45}$，秩和至多 $n^{2}L\le 2^{21}$，64位无符号整数足够存这些量；所有宽度以整数 $2^{L-j}$ 比较，需可容纳 $2^{32}$，不能只用32位值。

长度上限约束的是最深叶及相应译码路径；它不直接最小化建表内存、整份文件大小或缓存延迟。若频数由当前文件得到，码长表仍应传给接收者。原有HUF1编码器超过15仍明确拒绝；只有显式把其“选长度”步骤换成这里的优化器并保留EOF、符号身份及整个格式检查，才算完成限长编码扩展。本单元不暗改已有HUF1文件或默认实现。

终点实验把限制从3改成2、4、5，回溯全部符号，再核对规范码。检查器对486个小权重实例比较真实package-merge与独立Kraft穷举，并保留所选nodeset；有限测试不是对任意输入的证明。