本文解析算术编码中累积频率数组（cum_freq）的内存布局设计及其索引机制，重点说明为何用 ascii 值直接索引是错误的、数组为何定义为 258 元素，以及解码循环中 symbol 自增的真实语义。
本文解析算术编码中累积频率数组（cum_freq）的内存布局设计及其索引机制，重点说明为何用 ascii 值直接索引是错误的、数组为何定义为 258 元素，以及解码循环中 symbol 自增的真实语义。
在实现算术编码（Arithmetic Coding）时，累积频率数组 cum_freq[] 并非按原始字符的 ASCII 码值直接索引——这是初学者常见的关键误解。例如，字符 'U' 的 ASCII 值为 85，但代码中绝不会访问 cum_freq[84]；相反，cum_freq 是一个符号序号（symbol index）映射数组，其下标对应的是预定义符号表中的位置（0 到 N−1），而非字符的 ASCII 编码。
根据经典文献《Arithmetic coding for data compression》（Witten et al., CACM 1987）及配套 C 实现（如 model.h），该数组的声明通常如下：
#define No_of_chars 256 #define No_of_symbols (No_of_chars + 1) // 预留 EOF 符号（常为第 257 个） int cum_freq[No_of_symbols + 1]; // 实际分配 258 个元素：索引 0..257
这里 No_of_symbols + 1 = 258 的设计，本质是采用“哨兵+前缀和”惯用法：
- cum_freq[0] 存储总频次（即 cum_freq[N]，N 为有效符号数）；
- cum_freq[i]（i ≥ 1）表示前 i 个符号的累积频次（含第 i 个）；
- 最后一个元素 cum_freq[No_of_symbols]（即 cum_freq[257]）常设为 0，作为查找边界哨兵。
因此，编码公式：
high = low + (range * cum_freq[symbol - 1]) / cum_freq[0] - 1;
中的 symbol 并非 ASCII 值，而是当前符号在有序符号表中的秩（rank），取值范围为 1 到 No_of_symbols（即 1–257）。例如，若符号表按频次排序后 'U' 排在第 12 位，则 symbol = 12，此时访问 cum_freq[11] 才合法。
同理，解码端的循环：
for (symbol = 1; cum_freq[symbol] > cum; symbol++);
并非简单“递增 symbol”，而是一个二分查找的线性替代实现：它从 symbol = 1 开始遍历，寻找第一个满足 cum_freq[symbol] ≤ cum 的位置（注意条件为 >，故退出时 cum_freq[symbol] ≤ cum 成立）。由于 cum_freq[] 单调非增（按符号顺序累积），该循环等价于定位当前累积值 cum 所属的符号区间——即解出原始 symbol 的秩。
⚠️ 注意事项：
- 绝对不要将字符 ASCII 值直接用作 cum_freq 下标；
- 符号必须预先映射到紧凑整数索引（如通过 char → int 查找表）；
- cum_freq[0] 是总频次，cum_freq[i]（i≥1）是前 i 个符号的累计频次，数组长度需冗余 +1 以支持安全边界判断；
- 该循环在现代实现中应替换为二分查找（Arrays.binarySearch 或自定义），以避免 O(N) 时间开销。
综上，算术编码的正确实现依赖于清晰的符号抽象层：字符 → 符号索引 → 累积频次 → 区间缩放。忽视这一映射层级，是导致索引越界与逻辑错误的根本原因。
