徐术挺-漫思录

22-压缩与编码

27分钟阅读

22 压缩与编码：熵、字典、列式存储

开篇提问

先给你一个能测出直觉的问题：

有一段文本，内容是 “AAAAAAAAAAAAAAAAAAAA”（20 个 A）。理论上最少用多少空间能存下它？

  • 按 ASCII 存：20 字节
  • 但这段文本其实”没有信息”——它只有一个字符，重复 20 次

真正的信息量，可能只需要几个字节，甚至更少。

先别急着往下看。你自己先估一下：这 20 个 A，到底”值”多少信息？你可以把它压到多少？为什么不能再小了？

那么问题来了：“信息量”到底怎么衡量？为什么有些数据能压到 1/10，有些数据压完反而更大？压缩的极限在哪里？

这三个问题的答案，来自香农（Claude Shannon）在 1948 年创立的信息论。而理解了它，你就理解了所有压缩技术的原理，也理解了为什么”数据建模”（比如列式存储）有时比”通用压缩算法”更有效。

这一章有一个贯穿始终的反直觉：最高级的压缩，往往不是”用更好的算法压数据”，而是”先把数据组织成更容易压的形式”。 这句话你现在可能没感觉，读完列式存储那一节，你会回来点头。

子主题一：压缩的极限——信息熵

压缩的理论基础是信息熵（Entropy），香农提出的概念：

一段数据的熵，衡量的是它的”不确定性”或”意外程度”。

直觉理解：

  • 如果一段数据高度可预测（20 个 A、全是 0 的位图），它的熵很低 → 可高度压缩
  • 如果一段数据完全随机（加密数据、高质量随机噪声），它的熵最高 → 几乎无法压缩

香农的熵公式（概念上）：

H = -Σ p(i) × log₂ p(i)

其中 p(i) 是符号 i 出现的概率。

几个关键结论

结论一：熵是压缩的下界。 任何无损压缩算法，都不可能把数据压到低于它的熵。这是数学上的硬限制，不是技术问题。

结论二：越”不均匀”的数据，熵越低，越可压缩。

  • 一段英文文本：字母 E 出现频率约 12%，Z 约 0.07%——分布极不均匀，熵远低于理论最大值，所以能压到 1/2 甚至更多
  • 随机字节流：每个字节等概率出现——熵达到最大，压不动

结论三：重复越多、模式越明显，熵越低。 这就是为什么日志、文本、代码这类数据压缩率高，而已经压缩过的文件（MP3、JPEG、ZIP）再压缩几乎没效果——它们已经被压到接近熵了。

一个帮助你理解”熵”的类比：天气预报

“信息量 = 意外程度”这个定义，用天气预报来理解最直观：

  • 一条消息说”明天太阳照常升起”——你早就知道，这条消息的信息量几乎为零（熵极低，可高度压缩）。
  • 一条消息说”明天北京下暴雪”——在六月，这极度意外，信息量巨大（熵高，压不动）。

“重复的、可预测的”内容，本质上是”你已经知道的东西”，它不携带新信息，所以能压。 而”随机的、意外的”内容，每一比特都是你没法猜的新东西，所以压不动。

这就是为什么 20 个 A 能压到几个字节：因为”AAAAAAAAAAAAAAAAAAAA”这条消息，真正携带的信息只有”是 A，重复 20 次”——其余全是冗余。

子主题二：无损压缩的两大流派

理解了熵，无损压缩的两大流派就非常自然了。

流派一：熵编码（Entropy Coding）—— 用短码表示高频符号

核心思想：出现频率高的符号，用更短的编码；频率低的，用长编码。

最经典的例子：霍夫曼编码（Huffman Coding）

  • 统计每个符号的频率
  • 频率高的分配短码，频率低的分长码
  • 用一棵二叉树构造”前缀码”（任何一个码都不是另一个码的前缀，保证解码唯一）

举例：文本里 A 出现 60%、B 出现 30%、C 出现 10%

  • 传统编码：每个符号 2 bit（A=00, B=01, C=10）
  • 霍夫曼：A=0（1 bit）、B=10（2 bit）、C=11（2 bit）
  • 平均长度：0.6×1 + 0.3×2 + 0.1×2 = 1.4 bit
  • 压缩到原来的 70%

算术编码（Arithmetic Coding）：比霍夫曼更接近熵极限——它把整条消息编码成一个小数，而不是逐符号编码。理论上可以无限逼近熵。

流派二：字典编码（Dictionary Coding）—— 用短标记替换重复串

核心思想：找出重复出现的字符串，用一个短的引用替换它。

最经典：LZ 系列算法（LZ77 / LZ78 / LZW）

  • LZ77：维护一个”滑动窗口”，如果当前要输出的内容在前面出现过，就输出一个 (距离, 长度) 的引用，而不是重复输出内容
  • 举例："abcabcabc" → 输出 abc + 引用 (回退3字节, 重复6字节)

LZ 系列是”通用压缩”的主力——gzip、zlib、PNG、ZIP 都基于它（通常 LZ77 + 霍夫曼编码组合使用）。

为什么 LZ 这么有效？ 因为真实数据里，重复无处不在：

  • 文本里重复的单词和短语
  • 代码里重复的标识符和模式
  • JSON 里重复的字段名（每条记录都有相同的 key）

两大流派的分工

这里有个值得你记住的洞察：熵编码和字典编码解决的是两种不同的”冗余”。

  • 熵编码解决的是”符号分布不均”的冗余——有些符号比别的符号更常见。
  • 字典编码解决的是”重复模式”的冗余——有些字符串组合反复出现。

真实数据里这两种冗余同时存在，所以现代压缩算法（DEFLATE 等）几乎都是两者组合：先用 LZ 抓重复串，再对结果做霍夫曼编码。

子主题三：有损压缩——丢弃”感知不到”的信息

无损压缩的极限是熵，而熵有时会很高（比如图像、音频、视频的原始数据熵极高）。这时候怎么办？

有损压缩的思路：丢弃人类感知不到（或不重要）的信息，换取远高于熵极限的压缩率。

为什么这能行？

因为”数据量”和”信息量”不是一回事：

  • 一张 1920×1080 的照片，原始数据约 6MB
  • 但人眼能感知的信息，远少于 6MB——相邻像素高度相似、高频细节人眼不敏感、某些颜色差异感知不到

有损压缩的经典手法

JPEG（图像）：

  1. 色彩空间转换（RGB → YCbCr），把亮度（人眼敏感）和色度（不敏感）分开
  2. 色度下采样（把色度信息减半，人眼几乎察觉不到）
  3. 分块 DCT 变换，把图像转到频域
  4. 量化（关键的有损步骤）：丢弃高频分量（人眼对高频细节不敏感）
  5. 熵编码

MP3 / AAC（音频）：

  • 利用心理声学模型：人耳有”掩蔽效应”——一个响亮的声音会掩盖掉同时出现的微弱声音
  • 于是：被掩蔽的声音干脆不编码，人耳听不出来

H.264 / H.265（视频）：

  • 帧内压缩（类似 JPEG 压缩单帧）+ 帧间压缩（运动补偿：只存”这一帧相对上一帧变了什么”）
  • 视频的压缩率能到 100:1 甚至更高，绝大部分来自帧间压缩

有损压缩的核心哲学，值得你记住

不要问”怎么存下所有数据”，要问”接收者真正需要哪些信息”。

这个思路远超压缩领域——它是”需求定义”（第 25 章）的一个绝佳范例：通过重新定义”什么是必要的”，把不可能变成可能。

有损压缩教给你一件极重要的事：优化的第一性目标，永远是”接收者”，不是”数据本身”。 无损压缩问的是”怎么忠实存下所有比特”，有损压缩问的是”接收者（人眼、人耳）到底能感知到什么”。后者跳出了”数据”的框，站到了”数据的使用者”这一边——而这一步跨越，往往带来数量级的收益。

这个”以接收者为中心”的思维，在工程里遍地都是：API 设计（用户需要什么，不是系统有什么）、缓存设计（什么值得缓存，不是全缓存）、报表设计（老板要看什么结论，不是把所有数据都列出来）。

子主题四：列式存储——用”数据布局”换压缩率

讲完通用压缩，我们讲一个在数据系统里更高效、但常被误解的思路：列式存储（Columnar Storage）。

先看行式存储（传统数据库）：

Row1: {id:1, name:"张三", age:28, city:"北京"}
Row2: {id:2, name:"李四", age:35, city:"上海"}
Row3: {id:3, name:"王五", age:28, city:"北京"}

存储在磁盘上是：1,张三,28,北京 | 2,李四,35,上海 | 3,王五,28,北京

列式存储把它转 90 度，按列存：

id列:   1, 2, 3
name列: 张三, 李四, 王五
age列:  28, 35, 28
city列: 北京, 上海, 北京

为什么列式存储压缩率高得多？

原因一：同一列的数据类型相同、语义相近，重复度极高。

city 列只有”北京、上海”两个值；age 列很多重复。而压缩算法的效率高度依赖”局部重复”——同列放一起，重复自然聚集。

原因二：可以用专门为列设计的编码（这是关键）

游程编码（Run-Length Encoding, RLE）

  • 把连续重复的值编码成 (值, 重复次数)
  • 28,28,28,28,28 → (28, 5)
  • 适合：重复值多、且排过序的列（比如按时间排序后的状态列）

字典编码（Dictionary Encoding）

  • 把列里的不同值建成字典，存的时候只存字典索引
  • 北京, 上海, 北京, 北京, 上海 → 字典 {北京:0, 上海:1} + 数据 0,1,0,0,1
  • 适合：低基数列（取值种类少），压缩率极高
  • 这是列式存储最常用的编码之一

位图编码（Bitmap Encoding）

  • 对每个不同取值，建一个位图
  • 适合极低基数列，且支持快速的位运算查询

差分编码（Delta Encoding）

  • 存”和前一个值的差”而不是值本身
  • 1000, 1001, 1002, 1003 → 1000, +1, +1, +1
  • 适合：有序、递增的数据（时间戳、自增 ID）——差值很小，可用极少位数表示

Frame of Reference

  • 存”相对某个基准值的偏移”
  • 类似差分，但用块内最小值作基准

这些专用编码的威力： 一个排好序的、低基数的列，用字典编码 + 游程编码，压到原始的 1/10 甚至 1/100 都很常见——远超通用压缩算法（gzip）能达到的效果。

这里藏着一个极其重要的洞察

请注意列式存储的”顺序”：

它不是”先拿数据，再找更好的算法去压它”，而是”先改变数据的排列方式，让数据变得容易压，再用简单的算法压”。

这是两种完全不同的思路：

  • 通用压缩的思路：数据已经是”一锅炒饭”（各种类型混在一起），我找一个足够强的算法，尽量把它压实。
  • 列式存储的思路：我先把炒饭里的米、菜、肉分拣出来（按列分开放），再分别压——每一堆都是同质的，用最简单的算法就能压到极低。

最高级的压缩，不是”用更好的算法压同样的数据”，而是”先把数据组织成更容易压缩的形式”。 这个洞察，是本章最重要的一个结论，也是它在全书里和”数据布局影响性能”（第 24 章）、“通用 vs 专用”（第 4 章）相呼应的原因。

子主题五：列式存储的另一个大礼——只读需要的列

列式存储的好处不只是压缩，还有一个对分析查询至关重要的优势：

分析查询通常只关心少数几列。

比如：“统计各城市的平均年龄”——只需要 city 和 age 两列，不需要 id 和 name。

  • 行式存储：必须把整行读出来（因为行是连续的），读了 4 列只为用 2 列——读放大
  • 列式存储：只读 city 列和 age 列，其他列根本不碰

这个”只读需要的列”的能力，让分析查询快一个数量级。

再加上：

  • 向量化执行（一次处理一批值，充分利用 CPU 缓存和 SIMD 指令）
  • 列数据同类型、紧凑存放 → 缓存友好

这就是为什么 OLAP 数据库（ClickHouse、Doris、Vertica、Redshift）全部采用列式存储，而 OLTP 数据库（MySQL、PostgreSQL）依然是行式的。

行式 vs 列式的本质

行式 vs 列式的选择，本质是一个”访问模式”的问题（呼应第 4 章”通用 vs 专用”）：

  • OLTP：一次操作读写整行（点查、更新）→ 行式更优
  • OLAP：一次查询扫描大量行的少数几列（聚合分析）→ 列式更优

这就是经典的”HTAP 难题”——想同时做好 OLTP 和 OLAP 很难，因为存储格式本身就是矛盾的。

这里值得你记住一个更高层的规律：存储格式没有”绝对最优”，只有”对某种访问模式最优”。 行式和列式之争，本质是”你的查询是’按行’还是’按列‘“之争。一旦你的访问模式变了，最优的存储格式就跟着变。这和全书反复强调的”看约束、看数据分布，不背教条”是同一件事。

演进脉络

把压缩的演进从头串一遍，主线非常清晰。

  • 1948：香农创立信息论，提出熵的概念，给出压缩的理论下界。这是”信息”第一次被量化——在此之前，“信息量”是个模糊的概念。
  • 1952：霍夫曼编码发表。有趣的是，霍夫曼是在研究生课程作业里发明它的（老师 Fano 出的题），用”构造最优前缀码”的贪心算法证明了最优性。
  • 1977-78：Lempel 和 Ziv 提出 LZ77/LZ78，奠定通用无损压缩的基础。LZ 的意义在于：它不需要预先知道数据的统计分布，就能自适应地发现重复——这让通用压缩成为可能。
  • 1980s-90s：有损压缩大发展（JPEG 1992、MP3 1993、MPEG），多媒体时代开启。关键跃迁是”从数据到接收者”——开始问”人眼/人耳需要什么”，而不是”数据有多少”。
  • 2000s：列式存储在数据仓库领域兴起（Vertica、C-Store 论文）；Google 的 Dremel/BigQuery 论文推动列式在大数据领域普及。关键跃迁是”从算法到布局”——发现改变数据排列比改进算法更有效。
  • 2010s 至今：Parquet、ORC 成为列式存储的事实标准格式；Arrow 定义了内存中的列式格式；向量化执行引擎（ClickHouse）把列式的性能推到新高度；学习型压缩（用模型预测数据）开始探索。

主线：压缩的演进，是从”通用算法压一切”（gzip）走向”针对数据特征专门设计”（列式编码、有损压缩），再走向”用数据布局本身来压缩”（列式存储）。

三个里程碑式的”认知跃迁”

这条主线里有三次值得单独复盘的认知跃迁（都是第 28 章”突破口”的好素材）：

  1. 香农（1948）：把”信息量”从模糊概念变成可计算的”熵”。这是”定义问题”的威力——在此之前，没人能回答”信息到底有多少”。
  2. 有损压缩（1980-90s）：把优化目标从”数据”换成”接收者”。这是”重新定义’什么必要‘“的威力——问”人眼需要什么”而不是”数据有多少”。
  3. 列式存储（2000s）：把优化目标从”算法”换成”布局”。这是”改变问题结构”的威力——先分拣再压缩，而不是硬压炒饭。

你发现没有，这三次跃迁，没有一次是”更努力地优化同一件事”。每一次都是”换了一种方式看这件事”。 这和第 28 章总结的”突破口模式”完全一致。

本章思考题

【思考题】

  1. 什么是信息熵？为什么”随机数据压不动”、“重复数据可高度压缩”？

  2. 无损压缩的两大流派是什么？它们分别解决哪种冗余？为什么现代压缩算法要组合两者？

  3. 有损压缩的核心哲学是什么？它体现了什么超越压缩领域的思维？

  4. 列式存储为什么压缩率远高于行式存储？请说出至少三种列式专用编码及其适用场景。

  5. “最高级的压缩是先改变数据布局，再谈算法”——这句话怎么理解？它和全书的哪个主题呼应？

  6. 行式 vs 列式的选择本质是什么问题？为什么 OLTP 和 OLAP 的选择相反？

【参考答案】

  1. 熵衡量数据的不确定性/意外程度，是压缩的理论下界（无损压缩不可能压到低于熵）。随机数据：每个符号等概率、不可预测，熵达到最大，因此压不动。重复数据：高度可预测（如 20 个 A），熵极低，因此可高度压缩。类比天气预报：“太阳照常升起”信息量几乎为零（可高度压缩），“六月下暴雪”极度意外（压不动）。通用判据：越不均匀、重复越多、模式越明显，熵越低、越可压缩；反之已压缩过的数据（接近熵）再压几乎无效。

  2. 两大流派：熵编码和字典编码，分别解决两种不同的冗余。熵编码（霍夫曼、算术编码）解决”符号分布不均”的冗余——高频符号用短码、低频用长码。字典编码（LZ 系列）解决”重复模式”的冗余——用 (距离, 长度) 的引用替换重复串。真实数据两种冗余同时存在，所以现代算法（DEFLATE 等）几乎都是两者组合：先 LZ 抓重复串，再对结果做霍夫曼编码。

  3. 核心哲学：“不要问怎么存下所有数据，要问接收者真正需要哪些信息”。它体现的超越思维：优化的第一性目标是”接收者”而不是”数据本身”——无损压缩问”怎么忠实存下所有比特”，有损压缩问”人眼/人耳能感知什么”。这个”以接收者为中心”的思维在工程里遍地都是：API 设计（用户需要什么）、缓存设计（什么值得缓存）、报表设计（老板要看什么结论）。它是第 25 章”重新定义什么是必要的”的绝佳范例。

  4. 原因：同列数据类型相同、语义相近，重复度极高，压缩算法依赖局部重复，同列放一起重复自然聚集；且可用专为列设计的编码。三种（及以上）：字典编码（低基数列，建字典存索引，压缩率极高）、游程编码（重复值多且排过序的列，存 (值,次数)）、差分编码（有序递增数据如时间戳，存相邻差值）、位图编码（极低基数列，支持位运算查询）、Frame of Reference（存相对基准的偏移）。

  5. 理解：通用压缩是”数据已是一锅炒饭（各类型混合），找强算法硬压”；列式存储是”先把炒饭按米、菜、肉分拣（按列分开放），每一堆同质，用最简单的算法就压到极低”。所以最高级的压缩不是”用更好的算法压同样的数据”，而是”先把数据组织成更容易压缩的形式”。呼应：第 24 章”数据布局影响性能”（数组 vs 链表、AoS vs SoA）、第 4 章”通用 vs 专用”。

  6. 本质是”访问模式”的问题（通用 vs 专用的具体体现）。OLTP：一次操作读写整行（点查、按主键更新），行式存储一次 IO 就能取到完整行，更优。OLAP：一次查询扫描海量行的少数几列做聚合，列式可以”只读需要的列”、压缩率高、向量化执行友好，更优。这就是 HTAP 难题——两种负载需要的存储格式本身矛盾，很难同时做到最优。更高层规律：存储格式没有”绝对最优”，只有”对某种访问模式最优”，访问模式变了，最优格式就跟着变。

反向链接