算术编码的区间与可译性

每一步都在当前范围内按预测概率分地。常见符号获得大块土地，区间缩得较少；罕见符号只分到窄条，需要更多bit才能指明。重要的是双方使用同一张表，而不是这张表必须完全准确地描述真实来源。

区间越来越窄后，许多bit位置可以共同决定整段消息。例如某个符号的概率为 $3/4$，理想信息量约0.415bit。机器不会真的输出“0.415个bit”；它把这次选择和后来选择放进同一个区间，最后一起支付整数bit成本。

EOF使一段完整消息不再是另一完整消息的前缀。若省略它又没传原长，数0可以不断落入最左子区间，译码器分不清A、AA还是更多A。一个范围能标识已有前缀，并不自动告诉接收者何时停下。

固定表 $A:1/2,B:1/3,EOF:1/6$，按A、B、EOF排序。对 ABABA EOF，有理数状态依次为：

• 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$

选择bit前缀 0100110111，即整数311的10位表示；它对应 $[311/1024,312/1024)$，完整包含于终区间。译码时取左端 $z=311/1024$。在初始区间内它落在A；缩到A后又落在B；依次定位得到ABABA，最后落在EOF。用分数而非打印出来的小数判断端点，可避免把右开端点误收入前一个区间。

这里最短可容纳的二进制小区间确为10位：9位网格中，第一个左端不小于 $131/432$ 的点是 $156/512$，下一网格点 $157/512$ 已大于 $11/36$。10位可以选 $311/1024$，其下一点仍在界内。只说“宽度约需9bit”还不足以决定一个合法对齐前缀。

若把B概率错误设为零，遇B时区间宽度变零，算法无法编码。若两端符号顺序不同，即使概率数值相同，也会恢复不同文本。若只是用普通浮点数不断相乘，区间端点最终可能舍入成同一个数；这不是允许的终止策略。

理想区间法给每条消息的码长界 $k<-{\log }_{2}P+2$，这里的 $P$ 已包含所选模型和结束事件。对真实分布取期望后，要区分模型预测损失与码字舍入开销；传输模型、文件头和字节对齐还在这条理想式之外。

直接用精确有理数实现时，分子分母的位数随输入增长，不能把一步分数乘法当作永远恒定的机器工作。整数算术编码理路整数算术编码与延迟位Finite-precision arithmetic coding · Integer arithmetic coding · Arithmetic coder renormalization以闭整数区间实现E1/E2/E3重归一化，精确规定频数上界、初始填位、underflow延迟位与终止。用有限范围、重归一化和延迟bit保持可译性；它的整数舍入会改变区间，因此不应逐消息宣称其bit数严格等于本页理想码长。本例两种实现恰好都产生 0100110111，不代表所有输入都如此。

预测可以来自固定频数，也可由同步更新的频数模型理路压缩模型与自适应频数Adaptive frequency model · Adaptive arithmetic coding model把概率预测与bit输出分离，以编码后更新和同步缩放保持模型一致，复算短串预测表及失步反例。产生。编码器负责把区间变成bit，模型负责告诉它下一步怎么分区；这层分工允许同一编码器搭配不同预测策略。