每个符号选择当前区间的一部分
概念模型从[0,1)开始,按模型概率把当前区间分成各符号对应的部分。读入一个符号后,选择它的子区间,再在其中重复同样的划分。概率越高的符号保留的相对区间越宽,新增的信息成本通常也越小。
最终可用区间内的一个值标识消息,但解码器还必须知道何时停止。否则同一个数可能兼容不同长度的消息;原论文使用双方约定的结束符。概率模型、符号次序与停止规则共同构成编码约定。
参考:[1]
有限精度实现需要同步重标度
若直接让区间无限缩小,固定字长无法容纳越来越精细的端点。实际编码器维护整数范围,在已能确定输出比特时发送它们,并把剩余区间重新放大;中间区间造成的待定比特,也必须按明确规则稍后处理。
解码器使用相同整数运算和重标度,逐步读取比特来确定落在哪个符号区间。舍入、乘法溢出、累计频率上限与更新时机若不一致,就可能失去同步。把示意实数公式直接写成普通浮点循环,不等于得到可靠格式。
参考:[1]
模型与编码分开,收益也要分开计算
算术编码可以配固定模型,也能配按已处理符号更新的自适应模型,前提是解码端能得到同样分布。编码本身不发现单词或上下文规律,而是把模型给出的概率转成表示;模型很差时,结果仍可能膨胀。
相比逐符号前缀码,它没有每个符号必须占整数比特的同一限制,但短消息仍有终止和有限精度等开销。评价不能只说“比Huffman更好”,而应说明数据、模型、总大小、速度与实现资源,不能把特定实验中的优势写成所有用途的保证。