压缩流封装与完整成本

形式陈述

一个可解码文件需要比“这是Huffman编码”更多的信息。信源码只规定消息怎样对应码字；文件还须确定字节序、位序、符号表、原文长度或结束事件、有效bit数和尾部规则。本页定义两个小型教学格式HUF1和ARC1，让字节串唯一地决定一次解码操作。它们不是DEFLATE、gzip或其他现成标准。

所有多字节整数均为无符号大端；正文是任意字节0至255，另设EOF编号256。所有payload按字节最高位先读。码表或频数记录必须按符号编号严格递增，拒绝重复。只接受一个完整文件，不接受拼接文件或无声明的尾随数据。

HUF1顺序为：4字节ASCII HUF1；2字节表项数 $m$ ；4字节原文字节数 $n$ ；4字节有效码位数 $b$ ；随后 $m$ 项，每项2字节符号编号与1字节码长；最后 $\lceil b/8\rceil$ 字节payload。表项数在1至257，码长在1至15，表内必须有EOF，唯一符号表只接受EOF长度1；按规范规则恢复码字。有效位的最后一个码字必须是EOF，之前恰好解出 $n$ 个字节，字节末尾的 $(-b)\bmod8$ 个填充位全零。

ARC1顺序为：4字节ASCII ARC1；1字节精度 $w\in\{8,16\}$ ；2字节表项数 $m$ ；4字节 $n$ ；4字节算术有效位数 $b$ ；每项为2字节符号与2字节正频数；最后 $\lceil(b+w)/8\rceil$ 字节payload。总频数不超过 $2^{w-2}-1$ 。有效码由规定的整数编码与flush生成，其后显式附上 $w$ 个零guard，最后再填零到整字节。

ARC1解码先完成 $w$ 位初始填入，再逐符号解到EOF；核对输出长 $n$ ，且重编码所得有效位必须逐位等于文件声明的 $b$ 位。物理payload长度、guard和padding均须恰好正确。这里多存 $n$ 和 $b$ 是为了把长度与终止都做成显式检查，优化文件头不是本教学格式的目标。

直觉

EOF回答“正文到哪里结束”，有效位数回答“哪些位是码、哪些只是装箱补位”，原长回答“解码是否产出了预期数量的字节”。算术guard又有另一职责：给有限寄存器提供最后几次移入所需的确定尾位。它们有部分冗余，却不能在计算成本时消失。

实际协议也可以选择其他组合，例如只靠块长停止，或者用其他终止与隐式补位约定。关键不是全都要有，而是编码与解码必须选中同一份完整规则。模糊的“最后补几个零就行”无法确定截断输入究竟应成功还是失败。

例子与边界

原文为十六进制 41 42 41 42 41，即五字节ABABA，共40bit。

HUF1的表项是 (65,1),(66,2),(256,2)，有效码 010010011 共9位，其中正文7位、EOF2位。完整文件为：

48 55 46 31 | 00 03 | 00 00 00 05 | 00 00 00 09 | 00 41 01 | 00 42 02 | 01 00 02 | 49 80

竖线仅为讲解分组，不是实际字节。固定头14字节、码长表9字节、payload2字节：共25字节，成本是 $112+72+7+2+7=200$ bit。最后7bit是零填充。只报“ABABA压成7bit”漏掉了剩下193bit。

ARC1用 $w=8$ 、频数 (65,3),(66,2),(256,1)，有效码 0100110111，完整文件为：

41 52 43 31 | 08 | 00 03 | 00 00 00 05 | 00 00 00 0a | 00 41 00 03 | 00 42 00 02 | 01 00 00 01 | 4d c0 00

固定头15字节、频数表12字节、payload3字节，共30字节，成本 $120+96+10+8+6=240$ bit。最后8位guard和6位字节填充分开计费。有效码已包含EOF和flush，但算术编码跨符号共享bit，不应为每个正文符号强行分一个整数bit账单。

把末字节删除，物理长度立即不足，应拒绝。把padding改成1，也应拒绝。Huffman有效位中EOF提前出现，不能简单忽略后面的码；缺EOF也不能把刚好到字节边界当作成功。ARC1修改有效位数后即使碰巧解出同一文本，规定的重编码一致性检查也会拒绝非规范终止。

推论与应用

完整大小可写成“容器固定头 + 模型描述 + 有效码 + 寄存器guard + 对齐”。固定HUF1、ARC1的精确总字节数分别为

14+3m+\lceil b/8\rceil,\qquad15+4m+\lceil(b+w)/8\rceil.

若双方预先共享码表，模型成本可能由其他消息摊销，但必须说明该信息从何而来。不能一边由当前文件统计频数，一边在报压缩率时默认接收者已经免费知道它。空文件同样要传头、EOF和尾部；熵为零不意味着本格式生成零字节文件。

格式解析应先验证总表项数、原长和有效位上限，再进入建表及位串展开。固定上限 $m\le257$ 可避免被伪造的表长度拖进巨量循环；精确物理长度可区分合法填充与断流。进一步的输出容量和解码工作预算见有界解压。

这类结构验证能检测一些损坏，但不是校验和、认证或加密。两份合法压缩文件可以具有相同长度；攻击者能把一份替换为另一份。若需要完整性，外层必须另行规定合适的校验或认证机制。

参考资料

L. Peter Deutsch，RFC1951，§3.1.1、§§3.2.3–3.2.7：实际格式中位序、块结束、动态表和长度距离各自是规范的一部分；HUF1/ARC1不采用其完整语法
I. H. Witten、R. M. Neal、J. G. Cleary，Arithmetic Coding for Data Compression，1987，Figure3：EOF、终止与位I/O；本页显式guard和严格帧长为教学封装约定

形式陈述 ​

反向链接

形式陈述