[信息论与编码理论专题-39]：算术编码不是给每个符号分配一个“码字”，而是把整个消息压缩成一个“小数”——这个小数越精确，信息量越大。

一、对比哈夫曼编码：为什么需要算术编码？

先看大家熟悉的哈夫曼编码：

• 每个字符单独编码，比如：
  A → 0，B → 10，C → 11
• 编码长度必须是整数位（1位、2位……）
• 问题：如果某个字符概率是 0.9（比如英文中空格很常见），理论上它只需要不到 1 位就能表示（香农熵 ≈ 0.47 bit），但哈夫曼最少也得用 1 位，浪费了！

✅算术编码的突破：
不再限制每个符号必须用整数位，而是把整条消息映射到一个0 到 1 之间的实数区间，用这个区间的任意一个数（比如 0.3527）来代表整条消息！

二、通俗例子：用“猜数字”理解算术编码

想象你在玩一个猜数字游戏：

我心里想一个 0 到 1 之间的数，你要通过我的提示不断缩小范围，最后猜中它。

现在，我们用这个思路来“编码”一条消息，比如："AB"

假设我们知道每个字母出现的概率：

• A：80%（0.8）
• B：20%（0.2）

第一步：划分初始区间 [0, 1)

• 把 [0, 1) 按概率切分：
  • A 占前 80% → [0, 0.8)
  • B 占后 20% → [0.8, 1)

10 ────────┬─────────────── 1 2 │ 3 A(0.8) B(0.2)

第二步：处理第一个字符 'A'

• 因为第一个字符是 A，所以新范围缩小到 [0, 0.8)

第三步：在 [0, 0.8) 内，再按概率细分

• 在这个小区间里，继续按 A:80%、B:20% 划分：
  • A 的子区间：0 + 0.8 × 0.8 = 0.64 → [0, 0.64)
  • B 的子区间：0.64 到 0.8 → [0.64, 0.8)

10 ────────┬─────────────── 0.8 2 │ 3 A(0.64) B(0.16)

第四步：处理第二个字符 'B'

• 所以最终区间是[0.64, 0.8)

第五步：选一个数代表整个消息

• 只要选这个区间里的任意一个数，比如0.7，就可以代表 "AB"！
• 解码时，从 0.7 出发，反向推回去：
  • 0.7 在 [0, 0.8) → 第一个是 A；
  • 在 A 的区间里，0.7 落在 B 的子区间→ 第二个是 B；
  • 得到 "AB" ✅

三、为什么更高效？

• 哈夫曼编码 "AB" 可能需要：A=0（1位），B=1（1位）→ 共2 位
• 算术编码用一个小数（如 0.7）表示，实际存储时只需足够精度的二进制小数，比如：
  • 0.7 的二进制 ≈ 0.101100110011...
  • 只需 约 1.32 位（理论极限 = -log₂(0.8×0.2) ≈ 2.64 bits / 2 chars = 1.32 bpc）

✅ 算术编码可以逼近香农熵的理论极限，比哈夫曼更省空间！

四、关键特点总结

表格

五、现实中的应用

虽然算术编码更优，但因涉及浮点运算和专利问题，早期用得少。如今广泛用于：

• JPEG 图像压缩（可选算术编码，但多用哈夫曼）
• H.264/HEVC 视频编码（CABAC：基于上下文的自适应算术编码）
• 数据压缩工具（如 bzip2 的部分变种）

✅ 最后一句话记住它：

算术编码就像把一整句话“折叠”进 0 到 1 之间的一个小缝隙里，缝隙越小，信息越密集；只要记住缝隙里的任意一个点，就能还原整句话。

字符串的长度决定了浮点区间计算的次数，决定了嵌套的子区间的个数。

字符的个数决定了最外层区间的个数。

第一个字符决定了数值所在的第一个区间位置。