压缩算法简史：从莫尔斯电码到 zstd

把本站 58 篇文章的正文（去掉代码和配图）拼成一个文件，1,462,752 字节，交给四个不同年代的压缩器，各用它压得最狠的那一档：

压缩器       年份    压缩后       占原来
gzip -9     1992    613,844     42.0%
bzip2 -9    1996    463,495     31.7%
xz -9       2009    483,636     33.1%
zstd -19    2016    494,129     33.8%

结果有点出人意料。最小的是 1996 年的 bzip2，比二十年后的 zstd 还小一点；而网页服务器至今默认用来压网页的，恰恰是成绩最差的 gzip。几个问题跟着就来了：同样是“压缩”，这几个程序做的事情有什么不同？三十年过去，压缩率为什么没有大幅进步，新的压缩器又为什么一个接一个地出现？压缩有没有尽头，一个文件能不能一直压下去？

表里的数字只说明了压得多小，看不出每个压缩器对文字做了什么。要回答这些问题，得从比计算机还早一百年的电报说起。我们顺着时间往下走，每一代压缩算法都是被一个具体的问题逼出来的；一路上会拿同一句绕口令去试每一种算法，看它被压成了什么样子，最后把这些样子排在一起，回到开头这张表。

一、不等长的编码

莫尔斯电码：常用的字母用短码

1830 年代，莫尔斯和他的合伙人维尔在做电报。电线上只能传“通”和“断”，于是要给每个字母规定一串长短不一的电信号：短的叫点，长的叫划。电报按时间算钱，同样一句话，信号越短越好。

维尔的做法是去数铅字。他跑到新泽西州莫里斯敦的一家报社，数排字工铅字盒里每个字母各有多少枚铅字：E 最多，T 其次，Z、Q 最少。于是 E 只给一个点，T 只给一个划，Q 是“划划点划”¹²。

这个办法到底好在哪？我们用 1 亿字节的英文维基百科（enwik8，压缩界常用的测试文件³）统计字母频率，按国际电码的约定计时：点占 1 个时间单位，划占 3 个，码内间隔 1 个，字母之间空 3 个。

图 1的结果是，莫尔斯电码平均每个字母要 9.16 个时间单位。把同一套码字按频率重新分配一次，最优也只能到 8.78，莫尔斯的分配离最优只差 4%；反过来让最常见的字母用最长的码，就要 13.55。给常见的符号短码、罕见的符号长码，这是压缩最早、也最朴素的一个想法。

不过电报靠的是字母之间那段停顿来分隔字母，停顿本身也要占时间。计算机里只有 0 和 1，没有“停顿”这个第三种符号，那么码长不一的时候，接收方怎么知道一个字母在哪里结束？

香农：一个符号最少要几个比特

1948 年，香农在《通信的数学理论》里把这个问题算清楚了⁴。一个出现概率为 $p$ 的符号，最少要用 $\log_2(1/p)$ 个比特来表示；对所有符号按出现概率取平均，得到的下限叫熵：

$H=\sum_i p_i\log_2\frac{1}{p_i}$

英文 26 个字母等长编码要 5 比特（$2^4=16$ 不够，$2^5=32$ 够），而按 enwik8 里的字母频率算，熵是 4.21 比特。也就是说，只靠“常用字母短一点”，最多能省下大约六分之一。

香农同时指出，只要码字满足一个条件就不需要停顿：没有哪个码字是另一个码字的开头。比如 E 用 0、T 用 10、A 用 11，收到 01011 只能读成 E、T、A。这样的码叫前缀码。香农和 MIT 的范诺各自给了一种构造方法，从上往下把符号按概率尽量平分成两组，一组前面加 0，另一组加 1，再对每组重复⁵。这个方法很好用，但并不总是最省。最省的前缀码该怎么构造？

Huffman：从最罕见的两个合并

1951 年，范诺在 MIT 开信息论课，允许学生写一篇学期论文代替期末考试，题目就是找出最省的前缀码。研究生 Huffman 想了几个月，眼看要放弃去准备考试，忽然想到了反过来的做法⁶：不从上往下分，而是从下往上合并。每次取出出现次数最少的两个符号，把它们并成一个节点，次数相加，放回去，再取最少的两个，直到只剩一个节点。从根往下走，左边记 0、右边记 1，走到每个符号的路径就是它的码字。

他在 1952 年发表了这个方法，并证明它构造出的前缀码一定是最省的⁷。我们拿开头说的那句绕口令试一下：“吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮”。

图 2里，8 种字共 18 个，等长编码每个字 3 比特，一共 54 比特；Huffman 码一共 52 比特，只省了 2 比特。这句话里的字出现次数差不多，频率上可省的本来就不多。

放到大文件上也是这样。对 enwik8 逐字节做 Huffman，平均每字节 5.11 比特，熵是 5.08，Huffman 已经贴着下限了；可 gzip 能压到 2.92 比特。中文文章按字节统计更吃亏，因为一个汉字被 UTF-8 拆成三个字节，单看一个字节几乎看不出规律。

表 3说明了两件事。第一，“什么算一个符号”本身很重要：本站文章按字统计的 Huffman 码，比按字节统计少了四成。第二，即使选对了符号，只看频率的方法也明显输给 gzip。

这里要先引入一个贯穿后文的说法。任何一个压缩器都可以拆成两半：模型负责估计下一个符号出现的概率，编码器负责按这些概率分配比特⁸。莫尔斯的模型是铅字盒，Huffman 的模型是整份文件的字频，两者都假设每个符号和前后无关。Huffman 已经把编码器做到了这个模型下的最优，剩下的差距只能来自模型。可文字显然不是一个个独立掷出来的：“葡”后面几乎总是“萄”，整句“吃葡萄”还会原样再出现。怎样利用这种重复？

二、重复的片段

LZ77：用指针代替重复

1977 年，以色列理工学院的齐夫（Jacob Ziv）和伦佩尔（Abraham Lempel）发表了一种完全不同的办法⁹。它不统计频率，而是在刚读过的那一段文字（叫滑动窗口）里找和当前位置相同的最长片段。找到了，就输出一个指针“往回数 $d$ 个字，抄 $\ell$ 个”；找不到，就原样输出一个字。

图 4上半部分是 LZ77 处理那句绕口令的真实结果。第一次出现“葡萄”时只能原样写下；第二次出现时，变成“往回 4 个字、抄 2 个”。到了后半句，“吃葡萄”和“吐葡萄皮”整段都能抄，18 个字最后变成 9 个原样的字加 3 个指针。

这个方法的妙处在于不需要事先知道文字里有哪些重复，也不需要把字典传给解压方：解压方一边还原，一边就拥有了同样的“刚读过的文字”，指针指向的地方它已经写出来了。后来的研究证明了，不管数据来自什么样的信源，只要文件足够长，这种做法的压缩率都会逼近那个信源的熵，事先不需要知道数据的统计规律，所以它被叫作“通用”算法。

LZ78 与 LZW：边走边建字典

第二年，两人又发表了 LZ78¹⁰：不再往回找，而是把见过的片段一条条登记进一本字典，输出字典里的编号。1984 年，Sperry 公司的韦尔奇（Terry Welch）把它简化成 LZW¹¹：字典一开始只有单个字符，每输出一个编号，就把“当前片段加下一个字”登记成新词条。图 4下半部分里，字典从 8 个单字长到了 22 条，第二次遇到“吃葡”“吐葡”时都只输出一个编号。

LZW 的好处是实现极简单、速度快，很适合八十年代的机器。它很快被做进了 Unix 的 compress 命令（1985 年前后），又被 CompuServe 用在 1987 年的 GIF 图片格式里，成了那个年代最常见的压缩算法。

不过 LZ 系列只解决了“重复”，没有解决“频率”：指针和原样的字本身还是用固定长度写出去的。能不能把两种办法合起来？ 在回答这个问题之前，历史先拐了一个弯。

三、专利与 Deflate

LZW 的专利

韦尔奇在发表 LZW 之前申请了专利，1985 年 12 月授权，后来归 Unisys 所有。很长一段时间里 Unisys 只向做调制解调器芯片的厂商收费，用 compress 和 GIF 的人并不在意。

1994 年 12 月 28 日，圣诞假期中间，CompuServe 突然宣布：凡是读写 GIF 的软件，都要向 Unisys 交专利费¹²。当时 GIF 几乎是网页上唯一的图片格式，这个消息引起了很大的愤怒。同一周，一群程序员建了邮件列表，着手设计一个不受专利约束的替代格式，这就是 PNG。

Deflate：LZ77 加 Huffman

PNG 要换掉 LZW，现成的替代品来自另一场官司。1988 年，压缩软件 ARC 的公司 SEA 起诉菲尔·卡茨（Phil Katz），说他的 PKARC 抄袭了 ARC。官司以卡茨赔钱和解告终，他转而设计了一个新的格式，ZIP。1993 年前后的 PKZIP 2.04 版把一个叫 Deflate 的方法定为默认¹³：先用 LZ77 把文字切成“原样的字”和“指针”，再用 Huffman 给它们分配码长。前一步消除重复，后一步利用频率，两件事合在了一起。

Deflate 用的 LZ77 和 Huffman 都没有专利问题。1992 年，盖伊（Jean-loup Gailly）和阿德勒（Mark Adler）为了替代受 LZW 专利约束的 compress，用同样的思路写出了 gzip¹⁴；1995 年两人又把它做成了 zlib 库，Deflate 后来写进了 RFC 1951¹⁵。PNG 直接采用了 zlib，1996 年 10 月成为 W3C 推荐标准。

图 5把这几条线画在一起。到九十年代末，HTTP/1.1 把 gzip 定为网页的传输编码之一，ZIP、gzip、PNG、HTTP 用的都是同一个 Deflate，一个格式一旦成为所有程序都认的约定，它就不再只是一个算法了。这是开头那张表里 gzip 压得最差、却至今最常见的第一个原因。

Deflate 已经把“频率”和“重复”都用上了，压缩率还能怎么提高？两条路都还有余地：Huffman 码有一个先天的浪费，LZ77 的“模型”也很粗糙。我们先看前一个。

四、比特的零头：算术编码与上下文模型

Huffman 的整数比特

Huffman 码的每个码字至少 1 比特，而且长度都是整数。如果一个符号出现的概率是 95%，按香农的公式它只值 0.074 比特，Huffman 却至少要给它 1 比特。

这种情况在真实数据里很常见。黑白传真里 95% 是白点；更重要的是，一旦模型变聪明，它对下一个字的预测会变得很有把握，比如“葡”后面是“萄”的概率接近 1，整数比特就成了大浪费。Huffman 的补救办法是把几个符号打包成一组再编码，可组越大，码表就越大。

表 6是一个偏得很厉害的二元信源：每个位置是 1 的概率只有 5%，熵是每符号 0.286 比特。逐个符号做 Huffman 每符号 1 比特，浪费了 3.5 倍；8 个一组打包，码表要 79 条，才降到 0.298。

算术编码：把整条消息变成一个小数

1976 年，IBM 的里萨宁（Jorma Rissanen）和斯坦福的帕斯科（Richard Pasco）各自给出了算术编码¹⁶。它不给每个符号单独分配码字，而是把整条消息对应到 0 到 1 之间的一个区间：每读一个符号，就按它的概率把当前区间切一刀，留下对应的那一段。

图 7是用绕口令的字频编“葡萄皮”三个字。最后剩下的区间宽度等于三个字概率的乘积，写下这个区间里的一个数需要的比特数就是 $\sum\log_2(1/p)$，每个符号花多少比特可以是小数。下半部分换成一个看前一个字的模型：“葡”后面一定是“萄”，“萄”这一刀几乎不切，它就几乎不占比特。

表 6最后一列是我们照 1987 年 Witten、Neal、Cleary 那篇论文¹⁷写的 32 位整数算术编码器的实测结果：p=5% 时每符号 0.2864 比特，和熵 0.2864 一致到小数点后四位，编完再解一遍也完全还原。

算术编码从理论上解决了编码器的问题：模型给出什么概率，它就花多少比特，几乎没有浪费。从此压缩算法的进步，几乎全部来自模型。1981 年里萨宁和兰登（Glen Langdon）把这个分工写成了一篇论文，压缩就是“建模”加“编码”两件事⁸。

可惜算术编码也有专利。IBM 在八十年代申请了一系列算术编码的专利，1992 年的 JPEG 标准里同时定义了 Huffman 和算术编码两种方式，算术编码那一种通常能再小百分之几，却几乎没有软件支持¹⁸。后面我们还会看到，专利又一次改变了一个压缩器的设计。

上下文模型：看前面几个字

编码器的问题解决了，模型该怎么做？最直接的想法是：预测下一个字时，看看它前面是什么。1984 年，克利里（John Cleary）和威滕（Ian Witten）提出了 PPM（部分匹配预测）¹⁹：先看前 $k$ 个字，在这个上下文后面出现过的字里统计概率；如果当前的字在这个上下文后面从没出现过，就输出一个“逃逸”符号，退到前 $k-1$ 个字再查，一直退到不看上下文。

我们在本站文章上写了一个 60 行的 PPM：不做任何预训练，边读边统计，解压方用同样的规则就能同步重建出一样的模型。

表 8里，只看前 1 个字，每字节就从 3.90 比特降到了 2.72 比特，已经比 gzip 好得多；看前 3 个字，降到 2.43 比特，比开头那张表里的所有压缩器都小。模型看得越多，猜得越准，压得越小。

那为什么开头那张表里没有 PPM 这类压缩器？因为它慢。每处理一个字都要查几阶上下文、更新几张统计表，再做一次算术编码，同样是 C 语言实现，PPM 类压缩器的速度通常只有 gzip 的几分之一，解压也一样慢；LZ77 解压时只是照着指针复制，快得多。九十年代的机器上，这个差距很要紧。有没有办法拿到上下文模型的大部分好处，又不付出那么大的代价？

五、先排序，再压缩

BWT：一个可以还原的重排

1994 年，DEC 的伯罗斯（Michael Burrows）和惠勒（David Wheeler）发表了一个奇怪的变换²⁰。惠勒在 1983 年就想到了它，十年后才和伯罗斯一起写成报告。

做法是这样的：把一段文字的所有循环移位（把开头的字一个个挪到末尾）列出来，按字典序排序，然后只取每一行的最后一个字。

图 9是绕口令的结果。排序后，以“萄”开头的四行排在一起，它们的最后一个字都是“葡”，因为原文里“萄”前面总是“葡”；以“葡”开头的行最后一个字都是“吃”或“吐”。输出的这一列 皮，萄萄$不倒不萄萄葡葡葡葡吃吃吐吐皮 里，相同的字成串地挤在了一起。

为什么会这样？排序是按每一行的开头排的，开头相同的行，它们最后一个字就是这段开头在原文里的前一个字。所以排序这一步，实际上是把“出现在相同上下文前面的字”归到了一起，相当于免费做了一次上下文建模。而这个变换是可以还原的：只要知道最后一列和原文在哪一行，就能一步步把原文推回来。

把重排后的结果再用很简单的方法（先把“最近出现过的字”换成小数字，再做熵编码）压一遍，就得到了接近 PPM 的压缩率，速度却快得多。

bzip2

1996 年，西沃德（Julian Seward）用 BWT 写了 bzip，熵编码用的是算术编码。因为担心算术编码的专利，他在 1997 年的 bzip2 里把它换成了 Huffman，宁可放弃一点压缩率²¹。

现在可以回答开头的第一个疑问了：本站文章是中文，而 LZ77 类的压缩器是按字节找重复的，一个汉字占三个字节，重复片段要足够长才划得来；BWT 排序时天然把相同上下文的字聚在一起，对这种“词汇量大、短语反复出现”的文字更有效。表 8里 bzip2 排在 xz 前面，也是这个原因。在英文的 enwik8 上，情况就反过来了，下一节会看到。

不过 bzip2 也有它的代价：它要把整块数据（最多 900KB）读进来排序，解压时也要做逆变换，解压速度只有 gzip 的五分之一到十分之一。到 2000 年以后，压缩率和速度之间的取舍变成了新的主题。

六、更大的窗口与更快的速度

LZMA：把窗口开到几百兆

一条路是继续提高压缩率。俄罗斯程序员帕夫洛夫（Igor Pavlov）为他的 7-Zip 设计了 LZMA²²：仍然是 LZ77 的框架，但窗口从 Deflate 的 32KB 扩大到几十上百 MB，能找到很远以前的重复；匹配之后的编码不用 Huffman，而是用一个带上下文的二进制区间编码器（算术编码的一种变体）；压缩时还会比较多种切分方法，选总比特最少的那一种。它压得很小，但压缩极慢。后来 Linux 世界把它做成了 xz，用来发布源码包和内核。

LZ4 与 zstd：快到可以随手压

另一条路是反过来：压缩率差不多就行，但要非常快。2010 年前后，数据中心里到处是要读写的数据，磁盘和网络变快了，CPU 花在 gzip 上的时间反而成了瓶颈。2011 年，法国工程师科莱（Yann Collet）发布了 LZ4²³：只做 LZ77，不做熵编码，所有设计都为速度让路，解压每秒能处理一两个 GB。

LZ4 压得不够小。科莱想要的是一个比 gzip 压得更小、又比 gzip 快得多的东西，他缺一个又快又不浪费比特的熵编码器。Huffman 快但有整数比特的浪费，算术编码精确但每个符号都要做乘除法，慢。

答案来自波兰的物理学家杜达（Jarek Duda）。他在 2009 年提出了非对称数字系统（ANS）²⁴：把整个编码状态压在一个整数里，编码一个概率为 $p$ 的符号，大致就是让这个整数变成原来的 $1/p$ 倍，再把溢出的低位吐出来。它的压缩率和算术编码一样精确，而查表实现的版本（tANS）速度和 Huffman 差不多。杜达有意没有申请专利，任何人都可以用（2022 年微软拿到了一项 ANS 变体的美国专利，引起了不少争议²⁵）。

科莱用 ANS 写了 FSE 编码器，再和一个改进过的 LZ77 组合起来，2016 年 8 月在 Facebook 发布了 Zstandard，也就是 zstd²⁶。它有从 1 到 22 的压缩级别，低级别比 gzip 快几倍，高级别接近 xz，而不论用哪一级压，解压都一样快。

表 10是 enwik8 和本站文章在同一台机器上的实测。几个现象值得注意：

zstd -3 压得和 gzip -9 一样小，压缩快 7 到 9 倍，解压快 4 倍多。 这是 ANS 加上为现代 CPU 重新设计的结果，也是 zstd 能在数据库、文件系统、Linux 内核里迅速取代 gzip 的原因。

英文上 xz 最小，中文上 bzip2 最小。 没有一个压缩器在所有数据上都最好，这一点上一节已经解释过。

压缩率最好的几个，压缩都很慢。 xz -9 和 zstd -19 每秒只能压一到四兆。但 zstd -19 解压时依然有每秒 1 GB，适合“压一次、解很多次”的场景，比如软件包。

小文件：字典

还有一类数据，压缩率和速度都不是关键，难在它太短。一个网络请求、一条日志、一段 JSON，往往只有几百字节。LZ77 靠的是“前面出现过”，文件刚开头，前面什么都没有。那句 18 个字的绕口令用 UTF-8 存是 54 字节，gzip 压完还是 54 字节，xz 压完反而变成 96 字节：文件头、校验和、码表这些固定开销，就把压出来的那点空间吃掉了。

Google 在 2015 年发布的 Brotli 是为网页设计的，它的做法是在格式里自带一本 122,784 字节的字典²⁷，里面是从大量网页里挑出来的常见单词和 HTML 片段，任何文件一开头就可以引用它。zstd 则提供了另一种办法：用同类数据先训练出一本字典，压缩和解压两边各存一份。

表 11把本站文章和 enwik8 各切成 300 个几百字节的段落，逐段单独压缩。gzip 和不带字典的 zstd 只能压掉两成到四成，中文段落只压掉 16%；Brotli 靠内置字典好了一截；zstd 用同类段落训练出的 32KB 字典，中文段落压到了原来的 55%。

Brotli 在 2016 年进了 Chrome 和 Firefox，成了 gzip 之外最常见的网页压缩格式；2024 年 3 月的 Chrome 123 又加上了 zstd²⁸。但只要还有一个客户端只认 gzip，服务器就得留着它，这就是 gzip 至今还在的第二个原因：新的格式只能增加，旧的格式很难退出。

到这里，我们说的都是“无损压缩”，解压出来必须和原来一个字节都不差。可是开头的问题里还有一种文件：照片、音乐、视频，它们的压缩方式完全不同。

七、有损压缩：扔掉看不出来的

允许误差，问题就变了

一张 600×400 的照片，每个像素红绿蓝各 1 字节，原始大小 720,000 字节。用 PNG 无损压缩（先按相邻像素做差，再用 Deflate），只能压到 61%，因为照片里的噪点和细微的颜色变化几乎没有重复，也很难预测。

可是人看照片时，并不在意每个像素是不是一模一样。香农在 1959 年把这个问题也形式化了：允许一定的误差，最少需要多少比特，这叫率失真理论²⁹。有损压缩要做的，就是找出人感觉不到的那部分信息，把它扔掉。

余弦变换：把能量集中起来

问题是哪些信息人感觉不到？像素本身是不能随便扔的，扔掉任何一个都会留下一个洞。1974 年，阿哈迈德（Nasir Ahmed）等人提出了离散余弦变换（DCT）³⁰：把图像切成 8×8 的小块，把每块 64 个像素换成 64 个“频率”系数，左上角是这一块的平均亮度，越往右下是越细的纹理。

图 12是在一张咖啡杯照片³¹上的实测。平均每个 8×8 块里，能量最大的一个系数就占了 79%，最大的 10 个占了 96%；全图能量的 91% 都在左上角那一格。照片里大部分区域是平滑的，细纹理很少，而人眼对细纹理的变化又本来就不敏感。只留每块最大的 10 个系数、其余全部置零再变换回来，亮度通道的峰值信噪比（PSNR，衡量和原图差多少的指标，30 dB 以上通常看不出明显差别）还有 31.6 dB。

1992 年的 JPEG 标准就是这个思路¹⁸：DCT 之后，按一张“量化表”把每个系数除以一个数再取整，高频系数除以大数，大多变成 0；剩下的再用游程编码加 Huffman 压缩。质量参数调的就是这张表的大小。

表 13里，质量 75（大多数软件的默认值）的 JPEG 只有原始大小的 5.8%，是 PNG 的十分之一，肉眼几乎看不出差别；质量 5 时只剩 0.9%，色块就很明显了。

声音也是同样的道理。MP3 用的是心理声学模型：一个响的声音会盖住它附近频率上轻的声音，被盖住的部分不用记³²。视频还多一步，相邻两帧大部分内容相同，只记下哪些块移动到了哪里，又回到了 LZ77 “用指针代替重复”的老办法。

有损压缩把“压到多小”换成了“看起来差多少”，给了我们几十倍的压缩率。回到无损压缩，最后一个问题还没回答：它的尽头在哪里？

八、模型与压缩的极限

不能所有文件都压小

先说一个简单的事实：不存在一个能把所有文件都压小的压缩器³³。长度为 $n$ 比特的文件有 $2^n$ 个，而比它短的文件加起来只有 $2^n-1$ 个，不可能一一对应。任何压缩器把一些文件压小了，就一定会把另一些文件变大。压缩器能用，是因为我们关心的文件（文字、程序、图片）有规律，而随机的文件没有。

表 14是三个例子：1MB 随机字节、已经 gzip 过的文件、已经是 JPEG 的照片，再用 gzip 压一遍。前两个反而变大了，JPEG 只小了 0.3%。一个好的压缩器输出的东西，本身就接近随机，规律已经被拿走了。这就是为什么把照片和视频打成 ZIP 包几乎不会变小。

规律的尽头

那对有规律的文件，下限是多少？香农的熵只回答了一半，它假设我们已经知道文字的概率分布。真正的下限是这段文字的最短描述，也就是柯尔莫哥洛夫复杂度：能输出它的最短程序有多长。这个数在理论上是存在的，却被证明是不可计算的，我们永远没法确定某个压缩结果已经是最小。

所以压缩只能一点点地往下逼近。第四节已经说过，编码器在算术编码出现后就几乎没有浪费了，剩下能改进的只有模型：它对下一个字猜得越准，压得越小。从这里开始，压缩器的历史就是模型的历史，而模型一路变强的过程，和后来的大语言模型是同一条路。

上下文混合：不只听一个模型的

PPM 每次只听一个上下文的意见：先问“前 3 个字”，没见过就退到“前 2 个字”。可是哪个上下文最可靠，处处不同。读到“吃葡萄倒吐葡”时，“前 1 个字是葡”几乎可以断定下一个是“萄”；读到一个新词的开头，看前 3 个字反而会被误导；读到表格、代码、网址，又需要完全不同的上下文，比如“上一行同一列是什么”。

2002 年起，马洪尼（Matt Mahoney）的 PAQ 系列换了一个思路³⁴：同时运行几十上百个模型，有看前 1 到 6 个字节的，有看前一个完整单词的，有跳着看的，有专门对付表格和图片的，每个模型都给出自己的预测；再由一个混合器决定各听几分。为了让混合简单，PAQ 不直接预测下一个字节，而是一位一位地预测：下一位是 1 的概率是多少。每个模型报一个概率，混合器是一个很小的神经网络，把这些概率加权组合；压完一位，它就按预测错了多少，用梯度下降把权重调一下。哪个模型在当前这段数据上说得准，它的权重就涨上去。

2006 年，胡特（Marcus Hutter）以 PAQ 的一个版本为起点，设立了压缩维基百科的奖金，理由是压缩文字和理解文字本来就是同一个问题，后来的获奖者大多是 PAQ 的后代。混合带来的进步，在压缩榜上一目了然。

表 15从上往下，是压缩器的模型一代比一代强的过程：gzip 只会找重复，PPMd 看前几个字节，paq8 和 cmix 混合成百上千个模型。混合的模型越多，压得越小，速度也越慢：每一位都要跑一遍所有模型，再跑一遍混合器。

神经网络：边压边学

PAQ 里的模型都是人手写的：要看前几个字、要不要看单词、表格怎么对齐，全靠作者的经验。既然混合器已经是个小神经网络，能不能连模型也交给神经网络去学？

2019 年，写过 QEMU 和 FFmpeg 的贝拉（Fabrice Bellard）发布了 nncp³⁵。它的模型就是一个神经网络，从随机的权重开始，一边读维基百科一边训练：每读一个字节，先给出下一个字节的概率交给算术编码器，再用这个字节算一次损失，做一步梯度下降。解压时，解压方从同样的随机权重出发，用同样的步骤训练，就能得到完全一样的预测。这对计算提出了一个苛刻的要求：两边每一次浮点运算的结果都必须一模一样，差一位，后面全部解错，所以 nncp 要自己控制所有的计算顺序。

第一版 nncp 用的是 LSTM，还压不过 cmix；2021 年换成约 2 亿参数的 Transformer，放到 GPU 上跑，登上了榜首（表 15最后两行）。这时的压缩器和语言模型已经没有区别了：它就是一个边读边学、预测下一个字的语言模型。训练语言模型时最小化的交叉熵，正是这个压缩器每个字要花的平均比特数。

大语言模型当压缩器

那么，一个已经读过海量文字的大语言模型，直接拿来当压缩器的模型会怎样？我们用一个 5 亿参数的开源模型 Qwen2.5-0.5B³⁶ 试了一下：模型逐个 token 给出下一个 token 的概率，交给第四节那种算术编码器写成比特，解压时用同一个模型一边猜一边还原。压的是本文第一节的正文，它写于这个模型发布之后，模型不可能见过。

表 16里，这个小模型把 4,374 字节压到了 693 字节，每字节 1.27 比特，不到 xz 的三分之一；预先读过本站其余 58 篇文章的 PPM，也只能压到每字节 2.50 比特。解压出来的文字和原文一个字节都不差。DeepMind 2023 年的论文在更大的模型上得到了同样的结论：不计模型本身的大小，大语言模型压文字、图片和声音都比专门的压缩器小³⁷。

但这个结果有两处要打折扣。

第一，模型本身也要算进去。 解压的人必须有一模一样的模型，这个模型有近 1GB，比被压的文字大几十万倍。对一段文字来说，“压缩结果加上解压程序”才是公平的比法，这就是第一节说过的两部分码。模型读过的东西越多，这个问题越明显：让它压“床前明月光，疑是地上霜。举头望明月，低头思故乡。”这 24 个字，第一个字“床”要 23.5 比特，后面 23 个字一共只要 13.6 比特，因为整首诗就存在模型的权重里。胡特奖从一开始就把解压程序的大小也算进成绩，就是为了堵住这个口子³⁸。

第二，它太慢。 在一台 4 核 CPU 上，这个小模型压 4,374 字节用了 162 秒，解压又用了 137 秒，相当于每秒不到 30 字节，比 gzip 慢了近百万倍。

所以大语言模型没有变成日常用的压缩器，它证明的是另一件事。从莫尔斯的铅字盒、Huffman 的字频表、PPM 的上下文，到 PAQ 的混合器和 Transformer，压缩器的编码器在 1976 年就基本定型了，七十年来真正在变的，一直是模型对数据猜得有多准；而一个模型猜得越准，看起来就越像“懂”了这些文字。这正是“压缩即智能”这句话的意思，它和大语言模型的关系，在《梯度下降早就有了，大模型为什么最近几年才出现》里有详细的展开。

九、回到开头

现在回头看开头那张表和那几个问题。

同样是“压缩”，这几个程序做的事情有什么不同？ 把一路上试过的结果排在一起就清楚了。

图 17左边是同一句绕口令，右边是它被各个算法处理之后的样子。Huffman 把每个字换成一串长短不一的比特；LZ77 和 LZW 把重复的片段换成指针和编号，结果里还认得出原文；BWT 只是重新排了顺序，一个字也没少，相同的字却挤到了一起；算术编码把整句话变成一个小数；最后两行是带模型的压缩，颜色越深表示这个字花的比特越多。只读过本站文章的 PPM 没见过“葡萄”，第一次遇到要二十多比特，读过海量文字的语言模型认得这句绕口令，后半句除了出乎意料的“倒”字，几乎不花比特。gzip、bzip2、xz、zstd 这些日常用的压缩器，就是把前几行的办法组合起来：gzip 是 LZ77 加 Huffman，bzip2 是 BWT 加 Huffman，xz 是 LZ77 加区间编码，zstd 是 LZ77 加 ANS。

bzip2 为什么赢了 zstd？ 因为没有一个模型在所有数据上都最好。BWT 把相同上下文的字聚到一起，对词汇量大的中文文章特别有效；换成英文的 enwik8，xz 和 zstd -19 都比 bzip2 小。zstd 的设计目标本来也不是压缩率第一，而是在每一档速度上都压得够小。

三十年来为什么压缩率进步不大？ 因为普通压缩器的模型受速度限制：要每秒处理几十几百兆，只能用 LZ77 这种“找重复”的模型。更好的模型早就有了，PPM、PAQ、神经网络都能压得更小，代价是慢几十倍到近百万倍。新压缩器的进步，主要在“同样的压缩率，快多少”上：zstd -3 和 gzip 一样小，却快好几倍。

gzip 为什么还在？ 因为它是 Deflate，是 ZIP、PNG、HTTP 共同的约定，而这个约定是被 LZW 的专利逼出来的。格式一旦被所有程序认识，就很难退出。

能不能一直压下去？ 不能。压缩是把数据里的规律拿走，压过一次的东西已经接近随机，再压只会变大。规律本身有多少，我们永远算不出精确值，只能靠更好的模型去逼近。

小结

1. 只靠符号的频率能压多少？莫尔斯电码用铅字盒估频率，香农给出了下限（熵），Huffman 构造出最省的前缀码；但文字的字与字并不独立，只看频率压不了多少。
2. 怎样利用重复？LZ77 用“往回多少、抄多长”的指针代替重复片段，LZW 边走边建字典。
3. 为什么是 gzip？LZW 的专利逼出了 gzip 和 PNG，它们用的 Deflate 是 LZ77 加 Huffman，后来成了 ZIP、PNG、HTTP 共同的格式。
4. Huffman 的整数比特怎么办？算术编码让每个符号可以只花零点几比特，从此压缩的进步全在模型上；上下文模型 PPM 看前几个字，压得更小但很慢。
5. 怎样又快又利用上下文？BWT 通过排序把相同上下文的字聚在一起，bzip2 用它在中文上压过了后来的压缩器。
6. 压缩率之外还要什么？LZMA 用大窗口换压缩率，LZ4 和 zstd 借助 ANS 换速度，Brotli 和 zstd 的字典解决了小文件。
7. 有损压缩扔掉了什么？DCT 把图像的能量集中到少数几个系数上，JPEG 扔掉人眼不敏感的高频，体积只剩几十分之一。
8. 压缩有没有尽头？没有压缩器能压小所有文件，压过的东西接近随机；真正的下限不可计算，进步只能来自更准的模型：PAQ 混合上百个手写模型，nncp 让神经网络边压边学，大语言模型压得更小，但要带上几亿个参数，而且慢得没法日常用。
9. 这些算法到底做了什么？同一句话，Huffman 换成比特，LZ 换成指针，BWT 重新排序，算术编码变成一个小数，模型压缩则让猜得到的字几乎不花比特。

参考资料