把ABABA变成两个可独立解码的文件 ​

这个实验的终点是两份真正的字节文件。你应能从头读出它们的模型和长度信息，逐符号恢复同一个原文，最后解释为什么只有五字节的输入反而变成了25或30字节。另用一个LZ77回指写出七个字节，亲眼看见“刚写出的内容成为下一步的来源”。

下载原始五字节ABABA、完整HUF1文件、完整ARC1文件和Python标准库检查器。三个数据文件都由检查器中的编码函数实际生成；原文没有换行。脚本不访问网络，不调用压缩库，使用Python 3.10或更新版本即可运行：

python foundations-compression-stream-checker.py
python -O foundations-compression-stream-checker.py

两种运行均输出从状态算出的JSON轨迹与测试结果，失败会抛出异常；检查不依赖可被 -O 移除的assert。输出中的 emitted_delta 是这一步新发出的位，emitted_bits 是累计位数，依次串联增量可恢复全过程；flush后的完整有效码另列在 bits。

1. 先选阅读入口，再固定协议 ​

只想先做Huffman部分，可从信源码理路信源码Source code以码字表示信源符号或符号块，并区分单射、串联唯一可译与前缀结构。、前缀码理路前缀码Prefix-free code码字互不为前缀并保留单射源标签的编码；正码长时可即时译码。、Huffman编码理路Huffman 编码Huffman coding反复合并最低概率符号构造期望码长最小前缀码的算法。到规范码长表理路规范Huffman码与码长表Canonical Huffman code · 规范赫夫曼码从带符号的码长表唯一重建码字，以整数空槽检查拒绝过订长度，并逐位解出含EOF的短流。。算术分支接理想区间理路算术编码的区间与可译性Arithmetic coding · 算术区间编码按条件概率嵌套半开区间，从整个二进制小区间包含关系构造可译码字，给出ABABA的有理数轨迹。与整数状态理路整数算术编码与延迟位Finite-precision arithmetic coding · Integer arithmetic coding · Arithmetic coder renormalization以闭整数区间实现E1/E2/E3重归一化，精确规定频数上界、初始填位、underflow延迟位与终止。；自适应模型理路压缩模型与自适应频数Adaptive frequency model · Adaptive arithmetic coding model把概率预测与bit输出分离，以编码后更新和同步缩放保持模型一致，复算短串预测表及失步反例。是完成静态文件后的扩展。最后统一检查完整封装理路压缩流封装与完整成本Compressed stream framing · 压缩文件的终止与填充把模型、有效位、EOF、guard和字节填充写成可检查文件语法，核算短文件的实际总长及拒绝路径。和资源预算理路解压输出与工作预算Bounded decompression · Decompression resource limits在不可信长度触发分配之前验证输出、表、字典和工作上限，以重叠复制说明压缩长度与解码成本的差异。。

本实验的文件是自定义教学格式，不是DEFLATE。多字节整数字段均大端；payload每字节最高位先读。正文符号0至255，EOF为256；码表、频数表按符号编号升序。原文字节 41 42 41 42 41 对应A、B、A、B、A。两份文件都声明原长5，并恰好解出五字节后遇EOF。

HUF1固定头14字节：magic4、表项数2、原长4、有效位数4；每表项3字节：symbol2、length1。ARC1固定头15字节：magic4、精度1、表项数2、原长4、有效位数4；每项4字节：symbol2、frequency2。HUF1长度限1至15，唯一符号表只能是EOF长度1；ARC1精度只接受8或16，总频数不超过 $2^{w-2}-1$。默认8位仅适合这里的小表，完整256字节字母表需用16位例子。普通Huffman树超过15时拒绝，不实施长度受限最优建树。

2. 从码长表生成HUF1，再反向逐位读取 ​

先把EOF计一次，频数为A3、B2、EOF1。Huffman合并1与2，再把所得3和A的3合并，长度是A1、B2、EOF2。规范首码递推给 A=0，B=10，EOF=11。

请先自己写出 0 | 10 | 0 | 10 | 0 | 11，再比对生成结果 010010011。有效码只有9位，装成字节要补7个零，所以payload为 49 80。

完整25字节十六进制是：

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

前四字节是HUF1，不属于码长表。第一个表项 00 41 01 表示编号65、长度1；EOF项 01 00 02 中的 01 00 是大端整数256。读有效位时，在第1、3、4、6、7位分别得到A、B、A、B、A，第9位到EOF。后面的7个零不得继续解为七个A。

现在改表做三个检查：长度 (1,1,1) 过订，必须在建表阶段拒绝；长度 (2,2) 虽不满，但可构成 00,01；重复符号编号即使不超Kraft容量也非法。空文件的唯一EOF必须码长1；单一正文字符仍需正文和EOF两叶，不能把重复次数藏在空码字里。

3. 算术流要连同E3和flush一起执行 ​

固定频数A3、B2、EOF1，总量6。先用精确分数重复区间分割，得到：

A    [0, 1/2)
B    [1/4, 5/12)
A    [1/4, 1/3)
B    [7/24, 23/72)
A    [7/24, 11/36)
EOF  [131/432, 11/36)

终区间宽 $1/432$。二进制前缀 0100110111 的整个小区间为 $[311/1024,312/1024)$，落在其中。请核对两个端点，而不只检查左端数字。

再换8位整数实现，初态闭区间 [0,255]，四分点64、半点128。下表的“新增位”只计本符号归一化时实际发出的位：

第四步没有输出，不是丢掉了一位，而是把它延期。第五步发0时，同时兑现相反的1。EOF处理完累计输出 010011；flush先将u从2加到3，因L=8<64，追加0与三个1，形成完整10位 0100110111。

文件再加8个零guard、6个字节填充零，payload为 4d c0 00。完整30字节文件是：

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

译码先取8位 01001101，V=77。每个符号缩区间前的 (L,H,V) 依次是 (0,255,77)、(0,255,155)、(0,169,55)、(0,169,110)、(42,153,92)、(84,195,184)。用 $\lfloor ((V-L+1)6-1)/(H-L+1)\rfloor$ 找累计频数范围，逐项恢复A、B、A、B、A、EOF；共读取13位，后三位来自显式guard。

为什么8个guard足够？每次归一化贡献一个“已输出或待兑现”的位，若总轮数为r，flush后有效码长r+2；译码读到EOF至多需要w+r位，因此最多额外使用w−2位。这里保留w位零，让物理末尾可严格检查。删除文件的末字节后应该失败，不能把缺失字节自动视为无限零。

4. 让文件解码只依赖它自己 ​

把下载的三个数据文件和检查器放到同一目录，可运行下面这段独立读取，不向解码函数额外传码表或频数：

from pathlib import Path
import runpy
c = runpy.run_path('foundations-compression-stream-checker.py')
source = Path('foundations-ababa.txt').read_bytes()
h = Path('foundations-ababa.huf1').read_bytes()
a = Path('foundations-ababa.arc1').read_bytes()
c['equal'](c['huf_decode'](h)[0], source, 'HUF1 file decode')
c['equal'](c['arc_decode'](a)[0], source, 'ARC1 file decode')
c['equal'](c['huf_encode'](source)[0], h, 'regenerated HUF1')
c['equal'](c['arc_encode'](source)[0], a, 'regenerated ARC1')
print(len(source), len(h), len(a))  # 5 25 30

检查器还有两种不同的逆向路径：Huffman参考实现枚举每种长度的空闲叶并沿树解码；算术参考实现直接枚举所有整数子区间，找出包含V的一项，不使用scaled反算公式。分别比较它们与主解码器，能发现某些共享正向公式掩盖的错误，但仍不是对任意长度输入的形式证明。

5. 把“压了多少”分成完整账本 ​

五字节原文是40bit，HUF1是200bit，ARC1是240bit：本例都变大。

ABABA正文经验分布的熵约0.970951bit/字节，乘5约4.85475bit；这不含文件模型描述，也不含本例额外的EOF。算术实际采用A1/2、B1/3、EOF1/6，对包含EOF的整串给出 $-{\log }_2(1/432)\approx 8.754888$ bit理想信息量。三种数回答的是不同问题，不能拿4.85直接当作本文件可传输大小。

无噪声编码定理理路无噪声编码定理Source coding theorem · Noiseless coding theorem独立同分布信源的无损压缩平均码率可以逼近但不能低于其熵。的平均或渐近量词保留在旧页。一个完整无损编码器不可能把全部n位串都缩短：长度小于n的bit串总共只有 $2^n-1$ 个，而输入有 $2^n$ 个，单射必失败。某些文件省得多，必然容许另一些不省或变长。

迁移题：多长的全A文件才开始省空间？ ​

令正文为 $n\ge 1$ 个A，仍使用同一HUF1格式。请先不运行脚本，推出完整文件长度，并找第一次严格短于原文的 $n$。

答案：表中只有A和EOF，两者码长都为1，所以有效位数 $n+1$，固定头加表为 $14+2\cdot 3=20$ 字节，总长 $20+\lceil (n+1)/8\rceil$。$n=22$ 时输出23字节，仍变大；$n=23,24$ 时分别输出23、24字节，刚好相等；$n=25$ 时仍只输出24字节，首次严格节省。随着n增加一，输出长度至多增加一，故“原长减压缩长”不会下降；结合之前的区间可排除更早的严格节省。检查器实际重算 $n=1,\dots ,64$，不是硬编码这条答案。

6. 模型同步、LZ回指与最后一道预算门 ​

自适应扩展从A、B、EOF各1次开始，阈值7，先编码再更新，总量达到7时每项向上折半。ABABA前使用的表为 (1,1,1),(2,1,1),(2,2,1),(3,2,1),(2,2,1)；EOF使用 (3,2,1)。输出11位 00101111101。这段实验显式传入初态与阈值，不能用静态ARC1解码器猜测自适应模式。

随后用LZ77理路LZ77滑动窗口与重叠回指LZ77 · LZ77 sliding-window decoding用字面量和长度距离描述已输出历史，逐字节执行重叠复制，并区分匹配解析、token编码与解码成本。解析九字节ABABABABA：Lit(A), Lit(B), Match(7,2)。先写A、B，再依次从位置0、1、2、3、4、5、6复制到2、3、4、5、6、7、8。第三次复制所读的A是第一次复制刚写出的，重叠是合法语义。用复制前的历史快照AB无法一次取出七字节。

再用LZ78理路LZ78短语字典与同步重建LZ78 · LZ78 dictionary coding用旧短语编号加新字节创建字典项，规定末尾残余短语与结束token，证明编号有向无环且解码同步。处理ABABA，得到 (0,A),(0,B),(1,B),(1,END)。最后一个旧短语A必须保留；对ABABABA则是 (0,A),(0,B),(1,B),(3,A),(0,END)。END是本教学token类型，原始论文的定长块边界采用另一约定。

按每token1步、每输出字节1步，LZ77上述三token应付12步。将输出预算设为8，匹配开始前剩6字节，应先拒绝长度7；将匹配长度改成 ${10}^{30}$ 也应在分配或循环前拒绝。空token输入仍须先验证预算：负数、非整数不能绕过入口检查。LZ78初态就有一条空字典记录，字典预算至少为1。

检查覆盖与自行变更 ​

作者检查器实际覆盖511个长度0至8的二元串：两种完整文件往返、独立逆解、LZ77与LZ78恢复；340张小码长表对照Kraft条件与枚举叶；255个短自适应串及2000符号的反复缩放；另有全256字节字母表、零字节/FF、长单字母与非法输入。负测包含逐字节截断、尾随数据、过订/重复/缺EOF码表、非零guard/padding、频数超界、无效回指、巨量长度、字典和输出预算。JSON给出实际计数。

建议先改一个字节，再改频数表和阈值，观察是哪层不变量变化。有限穷举支持实现复算；对任意合法输入的结论来自规范码构造、整数区间、同步模型和向前写入归纳。压缩格式检查也不保证内容未被篡改：合法文件仍可能被替换成另一份合法文件。

BWT理路Burrows–Wheeler 变换Burrows-Wheeler transform · BWT对带唯一终止符文本的循环移位排序，并取最后一列形成可逆排列。和FM-index理路FM-indexFM-index · Full-text minute-space index在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。保留原来的可逆变换与压缩索引接口。BWT本身不减小字符数，FM-index还承担查询与采样成本；它们不是本实验中缺失的“另一份完整bitstream”。可靠信道、零错误通信和多终端压缩是不同的后续路线，本单元不取代那些定理。