本文解析算术编码中累积频率数组的内存布局设计及其在编解码过程中的索引逻辑，重点说明为何 cum_freq 数组需声明为 258 元素、如何安全映射 ascii 符号到频率索引，以及解码循环中 symbol 自增的本质是二分式线性搜索。
本文解析算术编码中累积频率数组的内存布局设计及其在编解码过程中的索引逻辑，重点说明为何 cum_freq 数组需声明为 258 元素、如何安全映射 ascii 符号到频率索引，以及解码循环中 symbol 自增的本质是二分式线性搜索。
在经典算术编码实现（如 Witten 等 1987 年 ACM 论文所描述）中，cum_freq（累积频率数组）并非直接按 ASCII 值索引原始字符，而是采用符号序号（symbol index）而非字符码值（character code）作为下标。这意味着：你不能写 cum_freq['U' - 1]（即 cum_freq[84]），而应先将字符映射到其在当前概率模型中的离散序号（0-based 或 1-based）。
例如，若你的输入字母表仅含 47 个有效字符（如 A–Z、a–z、0–9、空格及标点），则需预先构建一个符号映射表（symbol table）：
- char_to_idx['U'] = 20; // 'U' 是第 21 个有效符号（索引 20）
- idx_to_char[20] = 'U';
此时，编码公式中 cum_freq[symbol-1] 的 symbol 指的是该映射后的序号（1-based），而非 ASCII 值。因此正确用法是：
int symbolIdx = charToIndexMap.get(currentChar); // 返回 1-based 序号，如 'U' → 21 high = low + (range * cum_freq[symbolIdx - 1]) / cum_freq[0] - 1;
关于数组大小声明为 cum_freq[No_of_symbols + 1]（即 256 + 1 + 1 = 258），其设计意图有三：
- 兼容单字节字符集（0–255）：No_of_charts = 256 覆盖全部 unsigned char；
- 预留哨兵位（sentinel）：cum_freq[0] 存储总频次（即 cum_freq[No_of_symbols]），而 cum_freq[No_of_symbols + 1] 通常设为 0，用于边界判断；
- 规避 off-by-one 错误：C 语言中 cum_freq[i] 表示“前 i 个符号的累积频次”，故需 size = n+1 才能表达 n 个符号的完整前缀和（含初始 0）。
解码端的循环 for (symbol = 1; cum_freq[symbol] > cum; symbol++); 并非简单自增，而是执行线性查找：在已排序的累积频率数组中，定位满足 cum_freq[symbol-1] ≤ cum < cum_freq[symbol] 的唯一符号索引。此处 cum 是当前归一化区间内待解码的数值（如 value = (code - low + 1) * cum_freq[0] / range）。该循环等价于：
symbol = 1;
while (cum_freq[symbol] <= cum) {
symbol++;
}
// 此时 symbol 即为所求 1-based 符号序号⚠️ 注意事项：
- 该线性搜索在符号集较大时效率较低；实际工程中建议替换为二分查找（Arrays.binarySearch in Java）或使用累积分布函数（CDF）的预计算结构；
- cum_freq[0] 必须严格等于总频次（即 cum_freq[No_of_symbols]），否则归一化计算（如 (range * cum_freq[symbol-1]) / cum_freq[0]）将失效；
- Java 实现中需警惕整数除法截断误差，推荐使用 Math.floorDiv() 或转为 long 运算后再缩放；
- 若采用动态模型（adaptive arithmetic coding），每次编码后必须同步更新 cum_freq 并重排序——此时线性查找仍适用，但二分需配合 Fenwick 树或线段树优化。
综上，cum_freq 的 258 元素设计是历史兼容性与算法鲁棒性的折中；而符号索引的核心原则始终是：操作对象是概率模型中的离散符号序号，而非原始字节值。理解这一抽象层，是正确实现跨语言算术编码器的关键前提。
