GPT无损压缩小问答（3）：算术编码

GPT+算术编码是对数据的无损压缩。什么是算术编码？它是怎么工作的？

算术编码：GPT压缩的“比特转换器”

算术编码 (Arithmetic Coding) 是经典的无损压缩算法。GPT作为“世界模型”为这个算法提供了前所未有的、超精准的语言数据的“概率地图”。

核心作用：把概率分布变成最短的比特流

GPT内部的输出是什么？
- 当输入一个序列 token1, token2, ... token_{i-1} 时，LLM 输出的是 下一个 token token_i 在整个词汇表上的概率分布 P(token_i | context)，称为 logits。
- 例如：输入 “人工智能是”，LLM 可能输出 P(“未来”)=0.6, P(“趋势”)=0.3, P(“什么”)=0.05, ... P(“香蕉”)=0.0000001。
算术编码器如何工作？
- 想象一条0到1的数轴： 初始区间是 [0, 1)。
- 按概率切分区间： 根据 P(token_i) 将当前区间划分成若干子区间，每个子区间对应一个可能的 token。
  - 接上例：“未来” -> [0, 0.6)， “趋势” -> [0.6, 0.9)， “什么” -> [0.9, 0.95)， ... “香蕉” -> [0.9999999, 1)。
- 选中真实token的区间： 如果实际的下一个 token 是 “未来”，则新的当前区间变为 [0, 0.6)。
- 迭代： 用这个新区间 [0, 0.6) 作为起点，输入下一个 token token_{i+1} 到GPT获得新的概率分布，再次切分这个新区间。如此反复直到序列结束。
- 输出一个“代表点”： 最终得到一个非常小的区间 [low, high)。选择一个该区间内的二进制小数（比如 (low + high)/2），只保留其小数点后的有效比特位。这个比特串就是压缩结果。区间越小，所需的比特数越少 (-log2(区间长度))。

这里，算术编码中区间和比特输出的转换关系容易让人困惑，这确实是理解无损压缩最烧脑的部分。需要理解“代表点”的生成逻辑。看上去有一个矛盾：区间是连续的，怎么能离散化，用有限比特精确代表？这需要从信息论和计算机表示两个层面拆解。需要彻底打通“概率→区间→比特”的转换链条，想明白为何最终输出的是有限比特而非无限小数。“区间长度对应概率”不难理解，当前瓶颈在于如何把连续区间离散化成比特流。需要重点讲清楚两点：一是-log2(概率)为何等于比特长度（香农极限），二是如何用二进制分数逼近实数而不损失信息。

最终区间：概率的结晶

假设经过对整段文本的逐词编码，算术编码器得到最终区间：

[low, high) = [0.3654321, 0.3654343)

区间长度 = high - low = 0.0000022
这长度就是整个文本出现的概率值！
若每个词概率为 P1, P2, ..., Pn，则长度 = P1 × P2 × ... × Pn

我们可以这样比喻：将整个[0,1)区间看作一个序列数据的“宇宙”，每个可能的序列都对应这个宇宙中的一个子区间。序列出现的概率越大，对应的子区间就越长：长度等于概率。编码过程就是逐步缩小范围，最后定位到代表输入序列的那个子区间。一个非常简单的演示例子：

假设符号集：A（概率0.6），B（概率0.4）
要编码的序列："AB"

步骤：

1. 初始区间[0,1)

2. 编码第一个符号'A'：将[0,1)划分为 [0,0.6) 和 [0.6,1) 两个子区间。选择'A'对应的区间[0,0.6)。

3. 编码第二个符号'B'：将当前区间[0,0.6)按相同比例划分：A占60%：[0,0.36)，B占40%：[0.36,0.6)。选择'B'对应的区间[0.36,0.6)。最终区间为[0.36,0.6)，区间长度=0.24，等于序列"AB"的概率：P(A)*P(B)=0.6*0.4=0.24。

最终区间内的任何数都可以作为代表点。通常取最终区间[0.36,0.6)的中点（0.48）可能更靠近中间，但实际中我们取最短的二进制小数，比特串011（代表数值0.375）。

解码过程：

解码器已知概率模型，初始区间[0,1)。它接收到比特串011。

第一步：将[0,1)划分为[0,0.6)和[0.6,1)，0.375落在[0,0.6)内，所以第一个符号为'A'。

第二步：将当前区间[0,0.6)按比例划分：A:[0,0.36)，B:[0.36,0.6)。数值0.375在[0.36,0.6)内，所以第二个符号是'B'。

因此，解码正确。

最终区间的概念可以总结为：

- 它是整个序列在[0,1)区间内的“身份证”，其长度等于序列的概率。
- 区间的位置和长度由序列中每个符号的概率逐步决定。
- 编码输出的是这个区间内的一个代表点的二进制表示（取足够位数以唯一确定这个区间）。

通过这种方式，算术编码实现了近乎最优的无损压缩（每个符号的编码长度接近其信息熵）。

直观比喻：GPS坐标压缩

原始文本 → 一栋精确的别墅 (目标区间 = 别墅占地)

比特串 0101110111010111001 → 别墅的 邮政编码 + 门牌号 (19位编码)

邮政编码区域 > 别墅面积 → 邮编一定能覆盖别墅

门牌号指向别墅内的一个点 (代表点)

解压 → 快递员用邮编找到区域，用门牌号送货上门
(只要地址在别墅内，就能正确无误送达)

无损的魔法如何完成？

步骤	数学动作	信息意义
区间生成	`[low,high) = ∏ P(word)`	文本的概率指纹
比特计算	`k = ceil(-log₂(high-low))`	指纹的最短身份证位数
代表点	选区间内一个数，转`k`位二进制	生成身份证号 (`压缩比特流`)
解压	用身份证号反向追踪概率划分	凭身份证找回完整指纹 (`无损还原`)

最终输出的是概率空间的唯一坐标值，而非数据本身——这正是算术编码以逼近香农极限的方式实现无损压缩的魔力！

为什么这是无损的？

解压时，算术编码器反向操作：

- - 从同一个初始区间 [0,1) 和同一个初始模型状态开始。
  - 读入压缩后的比特串，将其视为一个二进制小数 C。
  - 用 GPT 预测第一个 token 的概率分布，切分区间。
  - 看 C 落在哪个 token 的子区间里，那个 token 就是解压出的第一个 token。
  - 用选中的子区间作为新范围，继续用 LLM 预测下一个 token 的概率分布，切分，看 C 落在哪里... 直到序列结束。

关键： 压缩和解压使用完全相同的LLM和完全相同的概率预测流程。只要 C 在最终压缩区间内，就能一步步唯一确定当初编码时的每个 token 选择。输入序列和输出序列比特级一致。

立委关于大模型与AI的博客汇总