rANS的有限整数状态与逆序归一化

把非负整数按模 $M$ 的余数分成周期。每个周期给符号 $s$ 连续 $f_s$ 个槽。商 $\lfloor x/f_s\rfloor$ 选择周期，余数 $xmod{f}_s$ 选择该符号槽内的位置；$c_s$ 把槽平移到整周期中的正确位置。译码先辨认槽所属的符号，再把周期和槽内位置拼回去。

整数映射为何真的可逆 ​

写 $x=q{f}_s+t$，其中 $0\le t<f_s$。因为 $0\le c_s+t<M$，编码结果 $y=qM+c_s+t$ 除以 $M$ 的商恰是 $q$，余数恰是 $c_s+t$。不重叠的累计区间唯一恢复 $s$，再算 $q{f}_s+(c_s+t)-c_s=x$。反过来，任意 $y\ge 0$ 的商余都落在某个符号区间，因此也是某个 $(s,x)$ 的像。这证明的是整数双向对应，不是概率近似。

有限窗口为何仍能逐步逆转 ​

令 $k=L/M$。由上面的商余结构，

证明两端时使用 $L=kM$、$bL=bkM$，以及余数 $c_s+(umod{f}_s)$ 严格小于 $M$。编码开始 $x\ge L\ge k{f}_s$；若 $x\ge bk{f}_s$，除以 $b$ 后仍至少为 $k{f}_s$。故反复除法最终进入所需原像区间，映射后必回到 $[L,bL)$。

接着证明译码补位不会多取或少取。每次提取都是 $v=bq+d$，所以补入同一 $d$ 可精确恢复 $v$。由于提取前始终有 $v<bL$，提取后 $q<L$；因而只要尚未还原全部本步骤提取的位数，恢复到的仍是低于 $L$ 的中间商，译码必须继续。全部恢复后回到编码前的 $x\ge L$，译码立即停止，不会取走上一编码步骤留下的位数。编码压栈的最后一项先恢复，所以必须倒转位数输出顺序。

把这个单步逆关系按消息长度归纳，译码依次撤销最后编码的 $s_0$、再撤销 $s_1$，最终得到原顺序和初态。这同时证明逆序处理源串及LIFO位数顺序；只证明 $C_s$ 的整数逆式还不够。

取 $A:2,B:1,C:1$，$M=4$，$c=(0,2,3)$，$b=L=16$。A的阈值128，B、C的阈值64。对非回文 ABCABAA，编码实际顺序是 A A B A C B A：

压栈顺序是 [0,3]，文件读取顺序是 [3,0]，最终状态为76。译码状态依次是

最终既回到16又恰好消费两项。使用回文测试会掩盖源顺序写反，这就是这里不用回文的原因。

完整RAN1文件 ​

本页应用压缩流封装理路压缩流封装与完整成本Compressed stream framing · 压缩文件的终止与填充把模型、有效位、EOF、guard和字节填充写成可检查文件语法，核算短文件的实际总长及拒绝路径。接口，另定义教学格式RAN1，所有多字节整数大端。固定头20字节依次为：magic RAN1 4字节；${\log }_{2}b=4$ 1字节；${\log }_{2}M=2$ 1字节；$L=16$ 2字节；表项数 $m$ 2字节；原长 $n$ 4字节；编码最终状态2字节；有效nibble数 $d$ 4字节。只接受这些固定参数。随后 $m$ 条“符号1字节、频数1字节”，符号严格递增、$1\le m\le 4$、频数为正且总和4。最后恰有 $\lceil d/2\rceil$ 字节payload，高nibble先读；若 $d$ 为奇数，最后低nibble必须是零填充。

本例27字节为

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

其中 00 4c 是最终状态76，30 提供位数3、0。总成本216bit = 固定头160 + 模型48 + 位数8。状态已经包含在固定头，不能漏计也不能再加一次。本文件比七字节原文更大；这里没有声称本小块取得熵界压缩率。

空串仍传模型，$n=0,x=16,d=0$，没有payload。AAAAA 在同一三符号模型下有一个有效nibble0和一个填充nibble0；有效数1不可省略。若仅有符号Z、频数4，则任意重复次数都不改变状态或产生位数，但不同 $n$ 的文件仍不同。删除字节、额外尾随字节、非零填充、缺位数、非法初始译码状态和不匹配的终态都被检查器拒绝。结构合法不等于内容未篡改，另一份合法文件仍可能代表另一消息。

真实成本及机器范围 ​

对 $m$ 项表先建累计量需 $O(m)$；若用长度 $M$ 的逆查表，另需 $O(M)$ 时间和空间，随后每个符号查询为常数。若改用累计边界二分则为 $O(\log m)$，不能同时宣称零表空间与常数查找。记总提取位数为 $d$，固定字长算术下编码及译码核心为 $O(n+d+m+M)$；每符号提取次数至多 $\lceil {\log }_{b}M\rceil$，因为最小允许归一化状态为 $L/M$。

逆序读取通常需要整个输入块 $O(n)$ 缓存，或可反向访问的已有存储；累积位数再倒序还需 $O(d)$。教学检查器保存逐步轨迹并在验证成功后返回完整输出，另占 $O(n+d)$，不能冒充常数空间、无延迟的前向流式编码。分块可限制峰值和等待，但每块重复支付头、模型或模型标识、最终状态和边界。

状态 $x<bL$ 并不使全部中间量自动适合相同位宽。阈值 $b(L/M)f_s$ 可能等于 $bL$，例如 $f_s=M$；当 $bL=2^w$ 时，$w$ 位寄存器不能存这个哨兵。实现可用更宽整数计算阈值。归一化后商乘积及加法结果严格小于 $bL$；译码原像亦小于 $bL$，且补位时 $x<L$ 保证 $bx+d\le bL-1$。先证明这些界，再选类型。

迁移到 $b=256,M=4096,L=2^{23}$ 时，窗口上界为 $2^{31}$；阈值上界同为 $2^{31}$，可用64位中间量、32位状态安全实现。检查器的通用核心实际跑这个参数；它额外限制字节字母表、2至256的二次幂基数、$M\le 4096$ 及 $bL\le 2^{32}$，这是实现预算，不是上述数学证明的必要条件。RAN1解析器仍只接受其固定小参数，不能仅修改表头就称为新格式。文件长度计算与计数器也须检查溢出，并在分配前按调用者的输出/nibble预算拒绝超限，接续有界解压理路解压输出与工作预算Bounded decompression · Decompression resource limits在不可信长度触发分配之前验证输出、表、字典和工作上限，以重叠复制说明压缩长度与解码成本的差异。的既有契约。

整数算术编码理路整数算术编码与延迟位Finite-precision arithmetic coding · Integer arithmetic coding · Arithmetic coder renormalization以闭整数区间实现E1/E2/E3重归一化，精确规定频数上界、初始填位、underflow延迟位与终止。以区间和延迟bit按前向顺序处理消息；本页用单一状态、编码前提取及逆序栈，两者的归一化证明与尾部协议不同。前向自适应模型理路压缩模型与自适应频数Adaptive frequency model · Adaptive arithmetic coding model把概率预测与bit输出分离，以编码后更新和同步缩放保持模型一致，复算短串预测表及失步反例。不能直接随着逆序源串更新：若需要前向历史模型，应先保存对应各位置的表或可重建信息，再逆序编码，译码按前向历史还原相同表，另计缓存和预处理成本。本页实际实现静态模型，没有伪称实现这项扩展。

终点实验提供文件读回、参数迁移及拒绝路径；标准库检查器将有限枚举与上面的普遍证明分开。