压缩模型与自适应频数

模型像共同记账。编码端已经看见下一字节，但译码端还没看见；所以不能先用这个未知字节修改概率，再让接收者猜该用哪张表。正确顺序是两边先用已知历史完成同一步，然后一起记入刚恢复的符号。

频数缩放既限制整数大小，也使较早的观察逐渐失去重量。向上取整让低频符号仍有一个位置；若直接向下取整，EOF或尚未出现的字母可能变为零，后续第一次出现就无法表达。

这是一种简单预测器，不知道A后面是否更容易出现B。若想用前一个字节作为上下文，可以为每个上下文维护一张表，但需要另外规定初始状态、未见上下文、内存上限和切换规则；bit编码算法不必因此更换。

取字母表A、B、EOF，初始 $(1,1,1)$，$w=8,T=7$。编码 ABABA 前各步使用的表为：

• 第1个A前：$(1,1,1)$；处理后 $(2,1,1)$
• 第2个B前：$(2,1,1)$；处理后 $(2,2,1)$
• 第3个A前：$(2,2,1)$；处理后 $(3,2,1)$
• 第4个B前：$(3,2,1)$；加一成 $(3,3,1)$，总量7，缩为 $(2,2,1)$
• 第5个A前：$(2,2,1)$；处理后 $(3,2,1)$
• EOF用 $(3,2,1)$，不更新

按前页的同一个整数coder，得到11位 00101111101，然后再加guard及填充。固定经验表 $(3,2,1)$ 的例子是10位。自适应不要求事先知道这个文件的最终计数，但学习初期和频数缩放都有代价，不能承诺对每个短文件都更短。

一个一开始就能看见的失步反例：初始三项均为1，编码器错误地先把A加到2，便把首个A分到 $[0,127]$；译码器仍按三等份解码，A只占 $[0,84]$。值100在编码端表示A，却在译码端表示B。两边采用同一种算术公式也救不了不同的模型状态。

空正文直接用初始表编码EOF。字母表若含256种字节及EOF，$m=257$，8位精度的最大总量63根本装不下；必须增加精度，例如 $w=16$，再选择大于257且不超过16383的阈值。不能仅提高阈值而保持8位coder。

同步不变量 ​

归纳假设处理前两边的表与前缀相同。整数coder据相同表恢复同一个符号，随后确定性的更新和缩放给出相同新表。因此从相同初态开始，两边每一步都同步。证明真正需要的是更新是共同历史的确定函数；没有要求预测等于真实分布。

固定表需要在文件头传频数，或者另行规定双方预先拥有同一模型。自适应表省去最终计数，但不能免费省去字母表和更新规则；新符号问题若使用escape，还必须给escape概率与原始字节的编码方式。本页采用固定字母表，不暗中加入escape机制。教学ARC1文件只封装静态表；自适应实验通过检查器函数显式传入初态和阈值，不伪装成ARC1的另一种隐含解码模式。

简单数组每次构造累计表和寻找符号花 $O(m)$，每次缩放也花 $O(m)$；对 $n$ 个字符是 $O(nm)$ 级别的模型工作，另加coder和输出成本。树状累计和结构可以改变查询与更新成本，但缩放策略也须重新计费。这里的复算检查器还保存每步完整频数作为证据，所以记录空间会达到 $O(nm)$；这不是流式算术编码器本身必须占用的空间。

若把coder换为逆序编码的rANS理路rANS的有限整数状态与逆序归一化rANS · Range asymmetric numeral coding · 范围非对称数系编码从商余互逆证明rANS，把逆序编码、有限窗口、位数栈与显式长度封装成可严格读回的文件。，不能把本页的更新直接沿逆序正文执行：那会得到不同的历史表。前向模型需要先记录各位置的预测状态或足以重建它们的信息，逆序编码时使用对应表，译码再按前向历史同步；缓存与重建另计。本页的静态ARC1和前向自适应算术实验仍维持原接口。