给编码器一个硬预算：有限状态与最大码长 ​

这次完成两种不同的受限编码任务：一是把编码状态始终放在有限整数窗口里，并生成能独立读回的文件；二是限制每个符号的最大码长，仍获得最小加权长度。前者的预算是寄存器状态，后者的预算是码树深度，二者不共享同一条最优性结论。

下载标准库检查器、七字节原文、完整RAN1文件和实际运行轨迹。原文恰为 ABCABAA，没有换行。用Python 3.10或更新版本运行：

python foundations-bounded-coders-checker.py
python -O foundations-bounded-coders-checker.py

脚本不联网、不用第三方压缩库；检查通过显式异常实现，不依赖可被 -O 移除的assert。默认只读并向标准输出写JSON；只有显式传 --write 目录 才生成输入、RAN1和轨迹文件。

先固定两条接口 ​

状态路线从源编码理路信源码Source code以码字表示信源符号或符号块，并区分单射、串联唯一可译与前缀结构。进入rANS理路rANS的有限整数状态与逆序归一化rANS · Range asymmetric numeral coding · 范围非对称数系编码从商余互逆证明rANS，把逆序编码、有限窗口、位数栈与显式长度封装成可严格读回的文件。，最后沿用完整封装理路压缩流封装与完整成本Compressed stream framing · 压缩文件的终止与填充把模型、有效位、EOF、guard和字节填充写成可检查文件语法，核算短文件的实际总长及拒绝路径。与解压预算理路解压输出与工作预算Bounded decompression · Decompression resource limits在不可信长度触发分配之前验证输出、表、字典和工作上限，以重叠复制说明压缩长度与解码成本的差异。的检查责任。码长路线从Huffman理路Huffman 编码Huffman coding反复合并最低概率符号构造期望码长最小前缀码的算法。与Kraft条件理路Kraft–McMillan 不等式Kraft–McMillan inequality刻画给定码长集合存在前缀码或唯一可译码的必要充分不等式。进入package-merge理路最大码长约束下的package-mergeLength-limited prefix code · Length-limited Huffman coding · Package-merge · 限长前缀码将最大码长的最优前缀码归约为二进制硬币选择，以配对归并和nodeset闭合证明最优长度并保留符号身份。，再把长度交回规范码理路规范Huffman码与码长表Canonical Huffman code · 规范赫夫曼码从带符号的码长表唯一重建码字，以整数空槽检查拒绝过订长度，并逐位解出含EOF的短流。。

原来的ABABA压缩流实验仍定义HUF1、ARC1、EOF、guard及其确切文件。RAN1是另一份教学格式；本页不改旧文件，也不让规范化步骤承担“寻找最优长度”的工作。

任务一：不用原文或外部码表读回RAN1 ​

先遮住原文，只读文件：

52 41 4e 31 04 02 00 10 00 03 00 00 00 07 00 4c 00 00 00 02
41 02 42 01 43 01 30

20字节固定头依次给magic、基数指数4、总量指数2、下界16、表项数3、原长7、最终状态76和有效nibble数2。三项表是A2、B1、C1，累计起点0、2、3。最后 30 按高nibble先读，得到3、0。编码器压栈时恰好是相反的0、3。

从 $x=76$ 开始，计算余数 $r=xmod4$，按照 [0,2),[2,3),[3,4) 找符号。每行先取符号，再应用整数逆式，低于16才补一个nibble：

完成七次后检查状态16、两项nibble恰好耗尽，才返回完整输出。不要在中途状态偶然等于16时停，也不要把物理字节末尾当作原文末尾。

把三个下载文件和检查器放在同一目录，实际执行独立读取：

from pathlib import Path
import runpy
c = runpy.run_path('foundations-bounded-coders-checker.py')
raw = Path('foundations-abcabaa.txt').read_bytes()
file = Path('foundations-abcabaa.ran1').read_bytes()
restored, trace = c['ran1_decode'](file)
c['equal'](restored, raw, 'independent file readback')
c['equal'](c['ran1_encode'](raw)[0], file, 'byte-for-byte regeneration')
print(restored, len(file), trace['state'], trace['digits'])
# b'ABCABAA' 27 76 [3, 0]

这里只把文件传给解码器，模型、原长与状态均由文件解析。随后才拿原文核对，不是把已知原文传进解码算法。

先预测失败，再改字节 ​

• 删掉最后一个字节：物理长度不足，尚未解码就拒绝
• 加一个零字节：精确帧长不符，不能当成合法额外填充
• 最终状态改成15或256：不在 [16,256)，拒绝
• 原长7改为6或8：终态/剩余位数或补位失败，不能忽略不匹配
• A频数改成0、B符号改成A、频数总和改成5：建模型时拒绝
• 对 AAAAA 生成有效nibble数1的文件，再把末尾低nibble改成1：对齐填充非法

本例有两个有效nibble，没有填充nibble，所以必须另造奇数案例才测得到padding检查。完整成本是20字节头 + 6字节模型 + 1字节payload = 27字节，原文7字节。把payload的8bit单独称为整份编码大小，会把必须保留的最终状态也藏掉。

空文件仍有头和模型，只是 $n=0,x=16,d=0$。单符号Z4模型更有辨别力：Z、ZZ与空串的状态和payload相同，只有原长不同，证明显式 $n$ 在此不能用“状态下降到16”代替。

任务二：从包的孩子恢复六个码长 ​

权重A至F是 1,1,2,3,5,8，上限3。先运行实际算法：

weights = [1,1,2,3,5,8]
lengths, certificate = c['package_merge'](weights, 3, trace=True)
print(lengths, certificate['cost'])
codes = c['canonical'](lengths)
print({chr(65+i): codes[i] for i in range(len(weights))})
# [3, 3, 3, 3, 2, 2] 47
# {'A': '100', 'B': '101', 'C': '110', 'D': '111', 'E': '00', 'F': '01'}

第一层指深度1，不是最先处理的层。先处理深度3的六个宽度1/8物品，配出主成本2、5、13；和深度2的新物品归并后有九项，主成本 1,1,2,2,3,5,5,8,13。下一次配成2、4、8、13，最重的余项13不进入下一层。深度1归并后的十项全部选中，代价和47、宽度和5。

不要把每个包当成一个新符号。回溯子节点后得到十六个原始物品：A至D各有层1、2、3，E和F各有层1、2。于是各符号物品数就是 3,3,3,3,2,2。检查证书须同时检查：没有重复的 (符号,层)；每个符号的层从1连续开始；长度上限；整数Kraft等式；包代价和等于加权长度。

普通Huffman输出 5,5,4,3,2,1，成本45，违反上限。直接截成 3,3,3,3,2,1 的Kraft和为5/4，规范码构造也必须拒绝。这个反例回答了为什么需要新的优化步骤。

将A至F分别重复1、1、2、3、5、8次，构成20符号消息。按上述规范码串联恰47bit；检查器另沿码字边界恢复全部20个符号。这里47是正文长度，尚未加表与帧尾，不能与RAN1的216bit完整成本直接比较。

独立oracle枚举 $3^6$ 个长度向量，以 $\sum _i{2}^{3-{\ell }_i}\le 8$ 判断可行；留下22个，唯一最优长度为上述结果。package-merge函数不调用oracle。普遍最优性仍依靠配对交换、二进制余量引理、nodeset向浅层闭合及Kraft构造。

结构迁移一：改变码长上限，而不剪树 ​

请先预测：六符号的L=2为何不可能？L变大最优值能否上升？然后运行：

for limit in [2,3,4,5]:
    try:
        ls, cert = c['package_merge'](weights, limit)
        print(limit, ls, cert['cost'])
    except ValueError as e:
        print(limit, str(e))

结果是：

L=4共有三种最优长度向量，不同确定tie-break可以给另一个46的答案。正确性要求保留各符号身份且达到同一最优值，不要求所有实现输出同一棵树。等权1、1、1另有三种最优向量；零权重、空符号表和L=0在本接口明确拒绝，唯一符号按正码长1处理。

将上限改到15也不会自动改变旧HUF1编码器。真正接入它时，输入集合必须包含专用EOF，输出长度仍绑定原符号编号，随后使用原规范化、bit序、有效位和EOF验证；不能只替换一列数字便跳过其余契约。

结构迁移二：换成字节基数并分块 ​

用 $b=256,M=4096,L=2^{23}$，把频数改为A2048、B1024、C1024。概率比例相同，但归一化边界和最终状态不同，旧nibble文件不能直接复用：

model = c['Model'](((65,2048),(66,1024),(67,1024)), 256, 1 << 23)
x, digits, _ = c['rans_encode'](b'ABCABAA', model)
back, _ = c['rans_decode'](x, digits, 7, model)
c['equal'](back, b'ABCABAA', 'byte-base migration')
print(x, digits)
# 33558604 [0]

窗口上界 $bL=2^{31}$。状态及最后加法结果都小于此值；阈值可能等于它，建议以64位中间量计算。补位前 $x<L$，所以 $256x+d\le 2^{31}-1$。检查器通用核心验证这些参数并做短串往返；RAN1固定字段的L只有2字节且只允许16，所以本迁移结果不冒充一份可由RAN1解析的新文件。

再把原文切成 ABCA 和 BAA 两块，各自从16开始，以同一三符号表独立生成RAN1：

files = [c['ran1_encode'](part)[0] for part in [b'ABCA', b'BAA']]
restored = b''.join(c['ran1_decode'](f)[0] for f in files)
c['equal'](restored, b'ABCABAA', 'separately framed blocks')
print([len(f) for f in files], sum(map(len, files)))
# [27, 27] 54
c['reject'](lambda: c['ran1_decode'](b''.join(files)), 'unframed concatenation')

两个独立文件共54字节：固定头40、模型12、payload2，比单块27字节多27字节。检查器实际执行逐块回读、拼接结果与直接拼帧的拒绝。每块最多缓存块长而不必整文件逆序；代价是重复元数据及每块终态，并增加你选择块边界的责任。当前解析器只接受一个完整帧，直接把两个文件拼接传入应拒绝；调用者必须另有合法块边界，并分别调用解码函数。

不能让逆序编码器直接沿逆序符号运行旧的前向自适应更新理路压缩模型与自适应频数Adaptive frequency model · Adaptive arithmetic coding model把概率预测与bit输出分离，以编码后更新和同步缩放保持模型一致，复算短串预测表及失步反例。。要使用原来的前向历史模型，先在前向遍历时得到各位置的预测状态，再逆序调用相应状态编码；译码按前向历史重建同一序列。相关模型缓存、重建及分块策略另计，本检查器没有实现该自适应扩展。

验证覆盖、资源边界与结束条件 ​

当前检查器实际运行3280个长度0至7的三符号串完整RAN1往返、240个状态的独立枚举单步逆式、48个rANS拒绝用例、524个迁移模型短串往返；package-merge对486个小正整数权重实例，与独立Kraft oracle比较最优值和长度成员资格。还检查256个最大32位等权重符号、L=32、包成本64位上界、单符号和同权重边界。JSON由计算得到，不把注释中的预期当作执行记录。

解析器先验证预算非负、固定头、声明原长/有效nibble上限、物理字节数，再建表、展开位数和输出。默认最多输出一百万字节、八百万位数；调用者可设更紧上限。固定M=4时每符号至多一次提取/补位，因此限制n与d也限制主要循环次数；通用核心的次数上界随 $\lceil {\log }_{b}M\rceil$ 变化。教学轨迹保存逐步记录，实际内存包括输出、位数及记录，不能只报寄存器是常数大小。

有限枚举检验实现与独立规则一致；对任意合法输入的保证来自两页的数学证明。严格结构检查没有认证作用，也没有实现tANS、DEFLATE互操作、论文的线性空间package-merge，或无缓冲的前向自适应rANS。完成标志是能从文件恢复原文、从所选原始物品恢复可行最优长度，并解释两种预算改变时哪条证明和接口需要重做。