熵编码与文件压缩：区别、常见方法与局部连续性的作用

熵编码是“怎样用更少的比特表示一串符号”，文件压缩是“怎样把整个文件变得更小”。 前者通常是后者的最后一环，而不是与后者平级的概念。

先看最容易混淆的结论：

一条典型压缩链路可以写成：

1
2
3
4
5
6
7

原始数据
  → 重排 / 分块 / 预测 / 字典匹配 / 变换
  → 可选的量化（有损）
  → 产生符号：字面量、长度、距离、残差、系数……
  → 概率建模
  → 熵编码
  → 文件头、码表、索引、校验和与容器封装

其中每一层解决的问题不同：

因此，文件压缩关心端到端结果，熵编码只关心给定符号及其概率后如何接近理论码长。

从“信息量”到“熵”

如果一个符号出现的概率为 $p(x)$，它携带的信息量定义为：

$$ I(x)=-\log_2 p(x) $$

越常见的符号越“不意外”，需要的比特越少；越罕见的符号越意外，需要的比特越多。例如：

信源的平均信息量就是熵：

$$ H(X)=-\sum_x p(x)\log_2p(x) $$

假设四个符号的概率分别是 $0.5、0.25、0.125、0.125$，那么：

$$ H(X)=0.5\times1+0.25\times2+0.125\times3+0.125\times3=1.75\ \text{bit/符号} $$

这意味着：如果符号确实服从这个分布，足够长的序列平均很难低于 1.75 bit/符号。熵编码的目标，就是让实际平均码长尽量靠近这个值。

但编码器通常拿不到真实分布 $p$，只能使用模型估计出的 $q$。这时理想平均码长对应交叉熵：

$$ H(p,q)=H(p)+D_{KL}(p\Vert q) $$

$D_{KL}$ 是模型失配带来的额外代价。这个公式揭示了压缩工程里极重要的一点：

换一个更强的熵编码器，收益可能只有几个百分点；让概率模型更懂数据，收益往往更大。

例如，一个编码器如果不知道“q 后面很可能是 u”，就只能按字母 u 的全局频率编码；加入上下文后，它可以使用 $P(u\mid q)$，条件分布更偏斜，码长也更短。

常见熵编码方法

Huffman Coding：给高频符号更短的前缀码

Huffman 编码反复合并概率最小的两个节点，最终得到一棵二叉树。左、右边分别记作 0、1，从根到叶子的路径就是符号码字。

以前面的概率为例，可以得到：

没有任何码字是另一个码字的前缀，所以解码器可以从左到右唯一解析。这个例子的平均码长恰好等于 1.75 bit/符号。

Huffman 的优点是结构清楚、查表解码快、实现成熟；局限是每个符号的码长只能是整数个 bit。当某符号概率是 0.9 时，理想码长只有约 0.152 bit，但普通二元 Huffman 仍至少要给它 1 bit。对单符号二元前缀码，平均码长满足 $H\le L&lt H+1$；把多个符号组成一块再编码可以摊薄这部分整数化损失，但码表也会迅速变大。

Huffman 常见于 DEFLATE、PNG、基线 JPEG、Brotli 和 Zstandard 的部分符号流中。1952 年的 Huffman 原始论文 给出了最小冗余前缀码的构造方法。

Arithmetic Coding：把整个序列缩进一个概率区间

算术编码不急着给每个符号分配独立码字，而是维护一个区间 $[L,H)$：

1. 初始区间是 $[0,1)$；
2. 按当前概率把区间切成若干段；
3. 读到哪个符号，就选择它对应的子区间；
4. 对后续符号重复细分；
5. 最后选一个落在最终区间内的二进制小数作为编码结果。

如果序列概率为 $P(x_1,x_2,\ldots,x_n)$，理想码长接近：

$$ -\log_2 P(x_1,x_2,\ldots,x_n) $$

因为它对整段序列分配比特，码长不必在每个符号边界上取整数，所以通常比逐符号 Huffman 更接近熵极限。实际实现需要处理有限精度、区间缩放、进位和终止标记；专利历史也曾影响它在部分格式中的普及。

算术编码可以配合静态模型，也可以边编码边更新概率。真正决定效果的是“区间编码器 + 概率模型”的组合，而不是单独的区间操作。

Range Coding：算术编码的工程化整数实现

Range Coding 通常被视为算术编码的一类实现。它不直接维护无限精度小数，而是使用固定宽度整数表示 low 与 range，区间过小时就输出高位并重新归一化。

两者在思想上几乎相同：

所以不应把 Range Coding 理解成与算术编码毫无关系的另一套理论；它更像同一思想的一种机器友好表达。LZMA 系列就会把 LZ 产生的符号交给 Range Coder。

ANS：用一个整数状态吸收和释放符号

ANS（Asymmetric Numeral Systems，非对称数字系统）维护一个整数状态。编码符号时，状态根据符号概率跳到新的状态，并在状态过大时输出低位；解码则根据当前状态恢复符号并回到前一个状态。

常见变体包括：

ANS 能像算术编码一样利用细粒度概率，又可以通过状态机和查表获得很高吞吐，因此现代压缩格式经常使用它。Jarek Duda 的 ANS 论文 系统讨论了它在压缩率与速度之间的定位。

ANS 也有自己的工程复杂度：频率必须归一化到有限状态数，表需要随码流保存或约定，典型编码与解码方向相反，多路交织时还要谨慎管理状态。因此“ANS 一定优于一切”并不成立，实际选择仍取决于数据规模、延迟、内存、硬件和实现质量。

Golomb / Rice：专门善待小整数残差

Golomb 编码适合近似几何分布的非负整数。给定参数 $m$，把整数 $n$ 写成：

$$ n=qm+r $$

商 $q$ 使用一元码，余数 $r$ 使用截断二进制码。Rice 编码是 $m=2^k$ 的特例，因此商、余数可用移位和掩码快速得到。

它特别适合“绝大部分残差接近 0，少数残差较大”的数据。带符号残差通常先映射成非负数，例如：

1

0 → 0, -1 → 1, +1 → 2, -2 → 3, +2 → 4, ...

FLAC 会先做线性预测，再用 Rice 类编码保存预测残差。这里真正制造可压缩性的主要是预测，Rice 负责把已经偏向小整数的残差高效写成比特。

Context + Binary Arithmetic：以 CABAC 为代表的组合系统

CABAC 不是单一“神奇码表”，而是三部分的组合：

1. 二值化：把多值语法元素拆成二进制决策；
2. 上下文建模：根据邻近块、已编码语法等选择概率状态；
3. 二进制算术编码：依据该概率输出比特流。

它再次说明：实际系统往往把“模型”和“熵编码核心”紧密组合。讨论压缩率时，只说用了算术编码却不说概率如何得到，信息是不完整的。

把这些方法放在一起看：

“静态还是自适应”是另一条独立维度。Huffman、Arithmetic、Range、ANS 都可以在不同程度上配静态频率表、分块更新或上下文模型，不能简单地把某一种编码器等同于某一种建模方式。

常见文件压缩方法

熵编码只压缩“符号概率不均匀”这一类冗余。完整文件压缩还会利用连续重复、重复子串、相邻相关、频域能量集中和人类感知不敏感等性质。

RLE：把连续重复写成“值 + 次数”

1

AAAAAAAABBBCC  →  (A,8)(B,3)(C,2)

RLE（Run-Length Encoding）对掩码、空白区域、扫描线和量化后大量为零的系数非常有效，但对 ABABABAB 无能为力，因为相同符号没有连续出现；对噪声数据还可能因计数信息而膨胀。

RLE 不是狭义熵编码。它先把数据改写成“符号 + 游程长度”，之后仍可对符号和长度再做 Huffman、ANS 或 Rice 编码。

LZ77 / LZ78 / LZW：用引用代替重复内容

Lempel-Ziv 家族利用重复字符串：

• LZ77 在滑动窗口中向后查找匹配，用 <距离, 长度> 代替重复片段；
• LZ78 显式构建短语字典，用字典索引表示新短语；
• LZW 在 LZ78 思路上让编解码器同步扩展字典，码流主要保存索引。

例如：

1
2

the_cat_and_the_cat
            └─────┘  可以引用前面出现过的 "the_cat"

LZ 方法利用的是重复子串，不要求相邻数值接近。ABCDEFGABCDEFG 数值并不平滑，但第二个 ABCDEFG 仍可以被一次回引用压缩。

DEFLATE 规范 RFC 1951 明确规定每个块结合 LZ77 与 Huffman：LZ77 把输入变成字面量、长度和距离，Huffman 再编码这些符号。这正是“去重复 + 熵编码”的经典分工。

BWT + MTF：先把相似上下文聚到一起

BWT（Burrows-Wheeler Transform）是一种可逆重排。它不会直接缩短数据，却会让拥有相似后缀上下文的字符聚集，使输出更容易出现长游程。典型链路是：

1

BWT → Move-to-Front → RLE → Huffman

bzip2 就采用这一类设计。BWT 的意义不是“字符本身发生了变化”，而是重新组织顺序，创造更强的局部性，让后续 MTF、RLE 和熵编码更有效。

Delta 与预测编码：不存原值，存“没猜中的部分”

对时间戳、传感器、音频、像素等连续信号，相邻值常常接近。Delta Coding 保存：

$$ d_i=x_i-x_{i-1} $$

更一般的预测编码会先计算预测值 $\hat{x}_i$，再保存残差：

$$ e_i=x_i-\hat{x}_i $$

只要预测准确，残差就会大量集中在 0 附近。PNG 为每条扫描线提供 None、Sub、Up、Average、Paeth 五类可逆过滤器，目的就是在 DEFLATE 前把像素字节转换成更适合压缩的残差；PNG 规范 也明确把过滤称为压缩前的准备步骤。

变换编码：把相关性搬到少数系数上

DCT、小波、MDCT 等变换会把空间域或时间域信号转到频率域。自然图像的相邻像素通常接近，经过 DCT 后，能量常集中在少数低频系数，其余高频系数较小。

变换本身可以完全可逆，也不必减小数据量；它的价值是改变表示方式。后续如果：

• 无损保存所有系数，只是重新建模，仍属于无损压缩；
• 对系数进行舍入、截断或分档，就进入有损压缩。

量化：真正“丢信息”的步骤

量化把一段取值映射到同一个代表值。例如 JPEG 中：

1

DCT 系数  3, -2, 1, 0  ──较粗量化──>  0, 0, 0, 0

大量小系数变成 0 后，游程编码和熵编码都更有效，但原值无法精确恢复。因此：

JPEG 常见的失真主要来自色度抽样与量化，不来自 Huffman。Huffman 只是无损地编码量化后的符号。

原始 JPEG 标准同时定义过 Huffman 与算术熵编码；ITU 对 JPEG-1 的说明 指出，基线流程要求 Huffman，而其他流程也可使用算术编码。

专用模型：懂数据结构，通常比“通吃”压得更好

通用压缩器只看到字节；专用压缩器知道数据的含义：

• FLAC 知道输入是音频采样，可做声道去相关、线性预测和 Rice 残差编码；
• PNG 知道二维像素邻域，可按扫描线选择预测过滤器；
• JPEG 知道图像的颜色与频率结构，可做颜色变换、DCT 和量化；
• 视频编码器知道帧间运动，可用运动补偿生成小残差；
• 列式数据库知道一列具有同一类型，可选择 Delta、RLE、字典或位打包。

代价是适用范围变窄、格式更复杂。没有一种方法在所有文件上都最优。

常见格式究竟组合了什么

Zstandard 是很好的现代例子：RFC 8878 描述了它如何分别编码字面量与匹配序列，并使用 Huffman 与 FSE 两类熵编码。这说明一个格式内部甚至可以为不同符号流选择不同编码器。

为什么局部连续性更有利于压缩

“局部连续性好”通常表示相邻样本相同、相近，或能由邻域可靠预测。它真正带来的不是某种神秘加成，而是更低的条件不确定性：

$$ H(X_i\mid X_{i-1},X_{i-2},\ldots) < H(X_i) $$

知道附近数据后，下一个值更容易猜。预测器把这部分“已经能猜到的信息”剥离，只留下更集中的残差，熵编码器才有机会用更少的比特表示它。

看两段包含完全相同数字的序列：

1
2

连续排列：100, 101, 102, 103, 104, 105, 106, 107
打乱排列：100, 107, 101, 106, 102, 105, 103, 104

它们的数值集合和出现次数完全一样，所以不考虑上下文的零阶经验熵都等于：

$$ H_0=\log_2 8=3\ \text{bit/符号} $$

如果只按全局频率做静态 Huffman，两个序列的编码长度也一样，因为编码器根本不看顺序。

做一阶差分后却完全不同：

1
2

连续排列的差分：+1, +1, +1, +1, +1, +1, +1
打乱排列的差分：+7, -6, +5, -4, +3, -2, +1

第一组残差几乎只有一个符号，第二组残差仍很分散。对大数据而言，前者可以用 RLE、Rice、Huffman、ANS 等极低成本编码；后者需要描述更多种残差。

所以更准确的因果链是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

局部连续 / 局部相关
        ↓
邻域更能预测当前值
        ↓
差值或预测残差集中在 0 附近
        ↓
出现大量小值、零值和重复游程
        ↓
概率分布更偏斜，条件熵更低
        ↓
熵编码得到更短的平均码长

这里必须强调一个边界：

局部连续性通常不是直接帮助“无上下文熵编码器”，而是帮助预测器、变换、RLE、LZ 或上下文模型产生更容易熵编码的符号。

不同类型的“局部性”会喂饱不同算法：

为什么二维图像尤其依赖扫描顺序

图像是二维的，但最终文件是线性字节流。若按合理的扫描顺序保存，左右像素在流中相邻，上下像素也容易通过上一行缓冲区访问；如果把所有像素随机打乱，颜色直方图不变，空间结构却消失了。

PNG 的 Sub、Up、Average、Paeth 过滤器正是在利用左、上、左上邻域。平滑天空中相邻像素原值可能是 180, 181, 180, 182，过滤后变成 180, 1, -1, 2；后面的小残差明显更集中。PNG 规范的设计说明指出，过滤能显著减小真彩色和灰度图像的压缩体积，原因就在这里。

局部连续性不是越强越万能

还要注意几个反例：

• ABCDEFGABCDEFG 不平滑，却有重复子串，LZ 会很喜欢；
• 平滑递增序列的原始字节直方图可能很均匀，必须先做 Delta 或使用上下文才能获益；
• 白噪声、加密数据和已经压缩过的数据通常缺少可利用结构，再压一次往往只增加文件头；
• 局部相关范围超过字典窗口时，LZ77 可能看不到远处重复；
• 为了制造局部性而排序记录，可能破坏原有顺序语义，还必须额外保存恢复顺序的信息；
• 小文件即使数据可压缩，码表、文件头和校验和也可能抵消收益。

怎样在工程中改善可压缩性

如果可以控制数据布局，通常先改善模型和局部性，再考虑更换熵编码器：

实际优化时可以按下面的顺序排查：

1. 先确认可逆性要求：是否允许量化或丢失精度；
2. 识别冗余类型：连续游程、重复子串、数值相关还是感知冗余；
3. 选择合适表示：预测、Delta、字典、变换、重排或分块；
4. 再选择概率模型和熵编码器：Huffman、Range、ANS、Rice 等；
5. 把元数据算进总成本：码表、字典、索引、块头和校验和都占空间；
6. 用真实数据衡量：同时测压缩率、压缩速度、解压速度、内存和随机访问。

只盯压缩率容易做出错误选择。日志传输可能优先低延迟，软件包分发可能优先解压速度，冷归档可以接受慢压缩，数据库则可能更看重按块随机访问和直接在压缩数据上执行查询。

最后总结

可以用三句话记住全文：

1. 熵编码是概率到比特的映射，文件压缩是从原始文件到可恢复码流的完整系统。
2. RLE、LZ、预测、Delta、BWT、变换和量化负责暴露或制造偏斜分布，Huffman、Arithmetic、Range、ANS、Rice 负责把这种偏斜变成更短的比特流。
3. 局部连续性降低的是“给定邻域后的不确定性”；只有通过预测、差分、上下文或重排利用它，才会真正转化为压缩收益。

下一次看到“某格式使用 Huffman，所以它的压缩原理就是 Huffman”时，可以追问四件事：它先对数据做了什么变换？产生了哪些符号？概率由谁估计？文件里还保存了哪些元数据？把这四层分开，绝大多数压缩格式都会清楚很多。

参考资料

• D. A. Huffman, A Method for the Construction of Minimum-Redundancy Codes
• Jarek Duda, Asymmetric Numeral Systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding
• IETF, RFC 1951: DEFLATE Compressed Data Format Specification
• IETF, RFC 7932: Brotli Compressed Data Format
• IETF, RFC 8878: Zstandard Compression
• W3C, PNG Specification: Filter Algorithms
• ITU-T, JPEG-1 entropy coders overview