--- title: "压缩算法简史：从莫尔斯电码到 zstd" description: "把本站文章交给几代压缩器，1996 年的 bzip2 压得比 2016 年的 zstd 还小，1992 年的 gzip 至今仍是网页的默认格式。顺着这个现象往回找：莫尔斯为什么给 E 一个点，Huffman 怎样把“按频率分配码长”做到最优，LZ77 怎样把重复的片段换成一个指针，专利怎样逼出了 gzip 和 PNG，算术编码和上下文模型怎样把“压缩”变成“预测”，BWT 为什么先排序再压，zstd 和 Brotli 又为什么在压缩率之外去追速度；最后看有损压缩扔掉了什么，以及压缩的尽头在哪里。" pubDate: 2026-10-28 tags: ["压缩", "算法", "历史", "信息论", "入门"] hero: "./hero.svg" clc: "TP274" refs: - id: gleick title: "The Information: A History, a Theory, a Flood" author: James Gleick site: Pantheon Books date: "2011" note: "第 5 章讲莫尔斯电码：维尔（Alfred Vail）到莫里斯敦一家报社数铅字盒里每个字母的铅字，按多少分配点划。" - id: vail title: "A Forgotten History: Alfred Vail and Samuel Morse" url: https://siarchives.si.edu/blog/forgotten-history-alfred-vail-and-samuel-morse site: Smithsonian Institution Archives note: "电码的署名是莫尔斯，按字母频率设计码表的工作很大程度上出自维尔，这一点至今有争议。" - id: shannon48 title: "A Mathematical Theory of Communication" url: https://doi.org/10.1002/j.1538-7305.1948.tb01338.x author: Claude Shannon site: Bell System Technical Journal 27 date: "1948" - id: fano title: "The Transmission of Information" author: Robert Fano site: MIT Research Laboratory of Electronics, Technical Report 65 date: "1949" note: "香农–范诺编码：自上而下把符号按概率一分为二，不保证最优。" - id: huffman title: "A Method for the Construction of Minimum-Redundancy Codes" url: https://doi.org/10.1109/JRPROC.1952.273898 author: David Huffman site: Proceedings of the IRE 40(9) date: "1952" - id: stix title: "Profile: David A. Huffman" author: Gary Stix site: Scientific American 265(3) date: "1991" note: "1951 年范诺的信息论课上，学生可以写学期论文代替期末考试，题目是找最省的二进制编码；Huffman 在快放弃时想到了自下而上合并的办法。" - id: lz77 title: "A Universal Algorithm for Sequential Data Compression" url: https://doi.org/10.1109/TIT.1977.1055714 author: Jacob Ziv, Abraham Lempel site: IEEE Transactions on Information Theory 23(3) date: "1977" - id: lz78 title: "Compression of Individual Sequences via Variable-Rate Coding" url: https://doi.org/10.1109/TIT.1978.1055934 author: Jacob Ziv, Abraham Lempel site: IEEE Transactions on Information Theory 24(5) date: "1978" - id: welch title: "A Technique for High-Performance Data Compression" url: https://doi.org/10.1109/MC.1984.1659158 author: Terry Welch site: IEEE Computer 17(6) date: "1984" note: "对应专利 US 4,558,302，1985 年 12 月授权，后归 Unisys，美国专利 2003 年 6 月 20 日到期。" - id: pnghist title: "History of the Portable Network Graphics (PNG) Format" url: https://www.libpng.org/pub/png/pnghist.html author: Greg Roelofs site: libpng.org note: "1994 年 12 月 28 日 CompuServe 宣布 GIF 软件要向 Unisys 交 LZW 专利费；同一周 PNG 的邮件列表成立，1996 年 10 月 PNG 1.0 成为 W3C 推荐标准。" - id: pkzip title: "PKZIP" url: https://en.wikipedia.org/wiki/PKZIP site: Wikipedia note: "1988 年 SEA 起诉 Katz 的 PKARC 抄袭 ARC，Katz 随后设计了 ZIP 格式；PKZIP 2.04 系列（1992 年底到 1993 年）把 Deflate 作为默认方法。" - id: gzip title: "Gzip" url: https://en.wikipedia.org/wiki/Gzip site: Wikipedia note: "Jean-loup Gailly 和 Mark Adler 编写，0.1 版 1992 年 10 月 31 日发布，1.0 版 1993 年 2 月；目的是替代受 LZW 专利约束的 Unix compress。" - id: rfc1951 title: "RFC 1951: DEFLATE Compressed Data Format Specification version 1.3" url: https://www.rfc-editor.org/rfc/rfc1951 author: L. Peter Deutsch site: IETF date: "1996" - id: rissanen title: "Generalized Kraft Inequality and Arithmetic Coding" url: https://doi.org/10.1147/rd.203.0198 author: Jorma Rissanen site: IBM Journal of Research and Development 20(3) date: "1976" - id: langdon title: "Universal Modeling and Coding" url: https://doi.org/10.1109/TIT.1981.1056282 author: Jorma Rissanen, Glen Langdon site: IEEE Transactions on Information Theory 27(1) date: "1981" note: "把压缩拆成“建模”和“编码”两部分的经典表述。" - id: wnc title: "Arithmetic Coding for Data Compression" url: https://doi.org/10.1145/214762.214771 author: Ian Witten, Radford Neal, John Cleary site: Communications of the ACM 30(6) date: "1987" note: "第一份公开、可直接使用的整数算术编码实现；本文实验里的编码器就是照它的做法写的。" - id: ppm title: "Data Compression Using Adaptive Coding and Partial String Matching" url: https://doi.org/10.1109/TCOM.1984.1096090 author: John Cleary, Ian Witten site: IEEE Transactions on Communications 32(4) date: "1984" - id: bwt title: "A Block-sorting Lossless Data Compression Algorithm" url: https://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf author: Michael Burrows, David Wheeler site: DEC Systems Research Center, Research Report 124 date: 1994-05-10 - id: bzip2 title: "bzip2" url: https://en.wikipedia.org/wiki/Bzip2 site: Wikipedia note: "Julian Seward 1996 年 7 月发布 bzip 0.15，用算术编码；因为专利顾虑，1997 年 8 月的 bzip2 0.1 改用 Huffman，格式与 bzip 不兼容。" - id: xz title: "XZ Utils" url: https://tukaani.org/xz/ site: Tukaani Project note: "LZMA 由 Igor Pavlov 为 7-Zip 设计；XZ Utils 由 Lasse Collin 维护，xz 格式用的是改进版 LZMA2。" - id: lz4 title: "LZ4 - Extremely fast compression" url: https://github.com/lz4/lz4 author: Yann Collet site: GitHub - id: duda title: "Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding" url: https://arxiv.org/abs/1311.2540 author: Jarek Duda site: arXiv date: "2013" note: "ANS 的第一版预印本在 2009 年；Duda 有意不申请专利。" - id: msans title: "Microsoft wins data-encoding patent despite inventor's efforts to keep it free" url: https://www.theregister.com/2022/02/17/microsoft_ans_patent/ site: The Register date: 2022-02-17 - id: zstdfb title: "Smaller and faster data compression with Zstandard" url: https://engineering.fb.com/2016/08/31/core-infra/smaller-and-faster-data-compression-with-zstandard/ author: Yann Collet, Chip Turner site: Engineering at Meta date: 2016-08-31 - id: brotli title: "RFC 7932: Brotli Compressed Data Format" url: https://www.rfc-editor.org/rfc/rfc7932 author: Jyrki Alakuijala, Zoltán Szabadka site: IETF date: "2016" note: "格式自带一本 122,784 字节的静态字典（第 8 节、附录 A）。" - id: chromezstd title: "Intent to Ship: Zstd Content-Encoding" url: https://groups.google.com/a/chromium.org/g/blink-dev/c/GFFOLCF12a4/m/crdNkVeaAQAJ site: blink-dev date: "2024" note: "Chrome 123（2024 年 3 月）起接受 Content-Encoding: zstd。" - id: shannon59 title: "Coding Theorems for a Discrete Source with a Fidelity Criterion" author: Claude Shannon site: IRE National Convention Record 7(4) date: "1959" note: "率失真理论：允许一定误差时，最少要多少比特。" - id: dct title: "Discrete Cosine Transform" url: https://doi.org/10.1109/T-C.1974.223784 author: Nasir Ahmed, T. Natarajan, K. R. Rao site: IEEE Transactions on Computers C-23(1) date: "1974" - id: jpeg title: "ITU-T T.81: Digital Compression and Coding of Continuous-Tone Still Images" url: https://www.w3.org/Graphics/JPEG/itu-t81.pdf site: ITU-T / ISO/IEC 10918-1 date: "1992" note: "标准里同时定义了 Huffman 和算术编码两种熵编码；算术编码那一种因为专利几乎没人用。" - id: mp3 title: "The story of mp3" url: https://www.iis.fraunhofer.de/en/ff/amm/consumer-electronics/mp3.html site: Fraunhofer IIS - id: coffee title: "skimage.data.coffee" url: https://scikit-image.org/docs/stable/api/skimage.data.html#skimage.data.coffee site: scikit-image note: "实验用的咖啡杯照片，600×400，作者 Rachel Michetti，以 CC0 发布。" - id: dce title: "Data Compression Explained" url: https://mattmahoney.net/dc/dce.html author: Matt Mahoney note: "压缩的入门长文，包括“没有压缩器能把所有文件都压小”的计数论证和 PAQ 的上下文混合。" - id: paq title: "The PAQ Data Compression Programs" url: https://mattmahoney.net/dc/paq.html author: Matt Mahoney note: "PAQ 的上下文混合：许多模型各自预测下一位，由在线训练的神经网络混合。PAQ 系列始于 2002 年。" - id: nncp title: "NNCP: Lossless Data Compression with Neural Networks" url: https://bellard.org/nncp/ author: Fabrice Bellard note: "边压边训练的 LSTM / Transformer 压缩器；解压要逐位复现压缩时的浮点运算。" - id: qwen title: "Qwen2.5 Technical Report" url: https://arxiv.org/abs/2412.15115 author: Qwen Team site: arXiv date: "2024" note: "实验用的是其中最小的 Qwen2.5-0.5B 基础模型（约 4.9 亿参数）。" - id: ltcb title: "Large Text Compression Benchmark" url: https://mattmahoney.net/dc/text.html author: Matt Mahoney note: "enwik8、enwik9 的出处，也是各压缩器在 enwik9 上的成绩来源。" - id: hutter title: "500'000€ Prize for Compressing Human Knowledge" url: http://prize.hutter1.net/ author: Marcus Hutter site: Hutter Prize - id: deletang title: "Language Modeling Is Compression" url: https://arxiv.org/abs/2309.10668 author: Grégoire Delétang 等 site: ICLR 2024 date: "2023" --- 把本站 58 篇文章的正文（去掉代码和配图）拼成一个文件，1,462,752 字节，交给四个不同年代的压缩器，各用它压得最狠的那一档： ```text 压缩器 年份 压缩后 占原来 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 是“划划点划”[^gleick][^vail]。 这个办法到底好在哪？我们用 1 亿字节的英文维基百科（enwik8，压缩界常用的测试文件[^ltcb]）统计字母频率，按国际电码的约定计时：点占 1 个时间单位，划占 3 个，码内间隔 1 个，字母之间空 3 个。
莫尔斯电码的码长分配 英文里 E 最常见，莫尔斯电码只给它一个点；按 enwik8 的字母频率算，莫尔斯码表离同一套码字的最优分配只差 4%。 enwik8 里最常见的字母 字母 出现频率 莫尔斯电码 Huffman 码 E 11.4% · 010 T 9.0% − 000 A 8.5% · − 1111 I 7.7% · · 1101 O 7.4% − − − 1100 N 7.0% − · 1010 … Z 0.2% − − · · 01100000 平均每个字母的代价 莫尔斯电码（时间单位） 倒过来分配 13.55 实际码表 9.16 最优分配 8.78 二进制（比特） 等长编码 5 Huffman 4.25 熵（下限） 4.21 点 1、划 3、码内间隔 1、字母间隔 3
图 1 · 莫尔斯电码给最常见的字母最短的码，平均代价离最优分配只差 4%
图 1的结果是，莫尔斯电码平均每个字母要 9.16 个时间单位。把同一套码字按频率重新分配一次，最优也只能到 8.78，莫尔斯的分配离最优只差 4%；反过来让最常见的字母用最长的码，就要 13.55。**给常见的符号短码、罕见的符号长码**，这是压缩最早、也最朴素的一个想法。 不过电报靠的是字母之间那段停顿来分隔字母，停顿本身也要占时间。计算机里只有 0 和 1，没有“停顿”这个第三种符号，那么码长不一的时候，**接收方怎么知道一个字母在哪里结束？** ### 香农：一个符号最少要几个比特 1948 年，香农在《通信的数学理论》里把这个问题算清楚了[^shannon48]。一个出现概率为 $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，再对每组重复[^fano]。这个方法很好用，但并不总是最省。**最省的前缀码该怎么构造？** ### Huffman：从最罕见的两个合并 1951 年，范诺在 MIT 开信息论课，允许学生写一篇学期论文代替期末考试，题目就是找出最省的前缀码。研究生 Huffman 想了几个月，眼看要放弃去准备考试，忽然想到了反过来的做法[^stix]：**不从上往下分，而是从下往上合并**。每次取出出现次数最少的两个符号，把它们并成一个节点，次数相加，放回去，再取最少的两个，直到只剩一个节点。从根往下走，左边记 0、右边记 1，走到每个符号的路径就是它的码字。 他在 1952 年发表了这个方法，并证明它构造出的前缀码一定是最省的[^huffman]。我们拿开头说的那句绕口令试一下：“吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮”。
绕口令的 Huffman 树 “吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮”18 个字、8 种字，Huffman 从出现最少的“，”和“倒”开始合并，最后总长 52 比特，等长编码 54 比特。 每次合并次数最少的两个 0 1 0 1 0 1 0 1 0 1 0 1 0 1 吃 ×2 葡 ×4 萄 ×4 不 ×2 吐 ×2 皮 ×2 ， ×1 倒 ×1 2 4 4 6 8 10 18 圆圈里是合并后的次数；从根往下，左 0 右 1 得到的码字 字 · 次数 码字 萄 ×4 00 吃 ×2 010 不 ×2 011 吐 ×2 100 皮 ×2 101 葡 ×4 111 ， ×1 1100 倒 ×1 1101 合计 52 比特 等长 3 比特 × 18 = 54 比特
图 2 · Huffman 从下往上合并出最省的前缀码；这句话各字频率接近，只比等长编码省 2 比特
图 2里，8 种字共 18 个，等长编码每个字 3 比特，一共 54 比特；Huffman 码一共 52 比特，只省了 2 比特。这句话里的字出现次数差不多，频率上可省的本来就不多。 放到大文件上也是这样。对 enwik8 逐字节做 Huffman，平均每字节 5.11 比特，熵是 5.08，Huffman 已经贴着下限了；可 gzip 能压到 2.92 比特。中文文章按字节统计更吃亏，因为一个汉字被 UTF-8 拆成三个字节，单看一个字节几乎看不出规律。
只看频率能压到多少（平均每个原始字节几比特，原样存是 8）
数据符号单位熵（零阶）Huffmangzip -9
enwik8（英文）字节5.085.112.92
本站文章（中文）字节6.386.413.36
字3.883.90

本站文章有 2,213 种不同的字，UTF-8 平均每个字 2.12 字节；按字统计时，换算回每个原始字节的比特数。

表 3 · Huffman 已经贴着“只看频率”的下限，离 gzip 还差得远；中文按字统计比按字节好得多
表 3说明了两件事。第一，“什么算一个符号”本身很重要：本站文章按字统计的 Huffman 码，比按字节统计少了四成。第二，即使选对了符号，只看频率的方法也明显输给 gzip。 这里要先引入一个贯穿后文的说法。任何一个压缩器都可以拆成两半：**模型**负责估计下一个符号出现的概率，**编码器**负责按这些概率分配比特[^langdon]。莫尔斯的模型是铅字盒，Huffman 的模型是整份文件的字频，两者都假设每个符号和前后无关。Huffman 已经把编码器做到了这个模型下的最优，剩下的差距只能来自模型。可文字显然不是一个个独立掷出来的：“葡”后面几乎总是“萄”，整句“吃葡萄”还会原样再出现。**怎样利用这种重复？** ## 二、重复的片段 ### LZ77：用指针代替重复 1977 年，以色列理工学院的齐夫（Jacob Ziv）和伦佩尔（Abraham Lempel）发表了一种完全不同的办法[^lz77]。它不统计频率，而是在**刚读过的那一段文字**（叫滑动窗口）里找和当前位置相同的最长片段。找到了，就输出一个指针“往回数 $d$ 个字，抄 $\ell$ 个”；找不到，就原样输出一个字。
LZ77 和 LZW 处理同一句绕口令 LZ77 把后半句里重复的“吃葡萄”“吐葡萄皮”换成往回指的指针；LZW 边输出编号边登记新词条，重复片段第二次出现时只占一个编号。 LZ77：在刚读过的文字里找最长的相同片段 (4,2) (10,3) (10,4) 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 输出：吃 葡 萄 不 吐 (4,2) 皮 ， 不 (10,3) 倒 (10,4) 18 个字变成 9 个原样的字加 3 个指针；(4,2) 读作“往回数 4 个字，抄 2 个” LZW：输出字典编号，同时登记“当前片段 + 下一个字” 初始字典：不=0 倒=1 吃=2 吐=3 皮=4 萄=5 葡=6 ，=7 吃 2 葡 6 萄 5 不 0 吐 3 葡萄 9 皮 4 ， 7 不 0 吃葡 8 萄 5 倒 1 吐葡 12 萄 5 皮 4 新词条：8=吃葡 9=葡萄 10=萄不 11=不吐 12=吐葡 13=葡萄皮 14=皮， 　　　　15=，不 16=不吃 17=吃葡萄 18=萄倒 19=倒吐 20=吐葡萄 21=萄皮 18 个字输出 15 个编号；“葡萄”“吃葡”“吐葡”第二次出现时只占一个编号
图 4 · LZ 系列不统计频率，而是把重复的片段换成一个指针或一个字典编号
图 4上半部分是 LZ77 处理那句绕口令的真实结果。第一次出现“葡萄”时只能原样写下；第二次出现时，变成“往回 4 个字、抄 2 个”。到了后半句，“吃葡萄”和“吐葡萄皮”整段都能抄，18 个字最后变成 9 个原样的字加 3 个指针。 这个方法的妙处在于不需要事先知道文字里有哪些重复，也不需要把字典传给解压方：解压方一边还原，一边就拥有了同样的“刚读过的文字”，指针指向的地方它已经写出来了。后来的研究证明了，不管数据来自什么样的信源，只要文件足够长，这种做法的压缩率都会逼近那个信源的熵，事先不需要知道数据的统计规律，所以它被叫作“通用”算法。 ### LZ78 与 LZW：边走边建字典 第二年，两人又发表了 LZ78[^lz78]：不再往回找，而是把见过的片段一条条登记进一本字典，输出字典里的编号。1984 年，Sperry 公司的韦尔奇（Terry Welch）把它简化成 LZW[^welch]：字典一开始只有单个字符，每输出一个编号，就把“当前片段加下一个字”登记成新词条。图 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 交专利费[^pnghist]。当时 GIF 几乎是网页上唯一的图片格式，这个消息引起了很大的愤怒。同一周，一群程序员建了邮件列表，着手设计一个不受专利约束的替代格式，这就是 PNG。 ### Deflate：LZ77 加 Huffman PNG 要换掉 LZW，现成的替代品来自另一场官司。1988 年，压缩软件 ARC 的公司 SEA 起诉菲尔·卡茨（Phil Katz），说他的 PKARC 抄袭了 ARC。官司以卡茨赔钱和解告终，他转而设计了一个新的格式，ZIP。1993 年前后的 PKZIP 2.04 版把一个叫 **Deflate** 的方法定为默认[^pkzip]：先用 LZ77 把文字切成“原样的字”和“指针”，再用 Huffman 给它们分配码长。前一步消除重复，后一步利用频率，两件事合在了一起。 Deflate 用的 LZ77 和 Huffman 都没有专利问题。1992 年，盖伊（Jean-loup Gailly）和阿德勒（Mark Adler）为了替代受 LZW 专利约束的 `compress`，用同样的思路写出了 gzip[^gzip]；1995 年两人又把它做成了 zlib 库，Deflate 后来写进了 RFC 1951[^rfc1951]。PNG 直接采用了 zlib，1996 年 10 月成为 W3C 推荐标准。
LZW、Deflate 与几个格式的来历 LZ78 演化出有专利的 LZW，用在 compress 和 GIF 里；1994 年 Unisys 收费促成了 PNG。LZ77 加 Huffman 组成 Deflate，成为 ZIP、gzip、zlib、PNG 和 HTTP 共用的格式。 几个格式的来历（箭头：A 用到了 B 的方法，或 A 促成了 B） LZ78 1978 LZ77 1977 Huffman 1952 LZW 1984 专利 compress 1985 GIF 1987 Unisys 收费 1994 Deflate 1991–93 gzip 1992 zlib 1995 ZIP（PKZIP） HTTP/1.1 1997 PNG 1996 虚线框和虚线：专利收费，逼出了替代格式 强调色：Deflate = LZ77 + Huffman， ZIP、gzip、PNG、HTTP 共用它 ARC 官司（1988）之后，Katz 设计了 ZIP
图 5 · LZW 的专利把大家推向了 Deflate，ZIP、gzip、PNG、HTTP 从此用同一个格式
图 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 的补救办法是把几个符号打包成一组再编码，可组越大，码表就越大。
二元信源，每个位置是 1 的概率为 p：平均每个符号几比特（10 万个符号）
编码方法p = 50%p = 20%p = 5%p = 1%
熵（下限）1.0000.7210.2860.081
Huffman，逐个符号1.0001.0001.0001.000
Huffman，2 个一组1.0000.7790.5740.515
Huffman，4 个一组1.0000.7390.3670.273
Huffman，8 个一组1.0000.7260.2980.157
算术编码（实测）1.0000.7210.2860.081

8 个一组时，码表要为实际出现过的每种组合各配一个码字，p = 20%、5%、1% 时分别是 226、79、28 条。算术编码是 32 位整数实现，编完再解码一遍，全部还原。

表 6 · Huffman 每个码字至少 1 比特，信源越偏浪费越多；算术编码不论 p 多少都贴着熵
表 6是一个偏得很厉害的二元信源：每个位置是 1 的概率只有 5%，熵是每符号 0.286 比特。逐个符号做 Huffman 每符号 1 比特，浪费了 3.5 倍；8 个一组打包，码表要 79 条，才降到 0.298。 ### 算术编码：把整条消息变成一个小数 1976 年，IBM 的里萨宁（Jorma Rissanen）和斯坦福的帕斯科（Richard Pasco）各自给出了**算术编码**[^rissanen]。它不给每个符号单独分配码字，而是把整条消息对应到 0 到 1 之间的一个区间：每读一个符号，就按它的概率把当前区间切一刀，留下对应的那一段。
算术编码把消息变成一个区间 编“葡萄皮”三个字，每读一个字就按它的概率把区间切下一段；只看字频时最后的区间宽 0.0055，要 7.51 比特，看前一个字时宽 0.1111，只要 3.17 比特。 只看字频（整句的字频，和 Huffman 用的一样） 读入 葡 葡 萄 吃 不 吐 皮 ， 倒 0.0000 1.0000 读入 萄 葡 萄 吃 不 吐 皮 ， 倒 0.0000 0.2222 读入 皮 葡 萄 吃 不 吐 皮 ， 倒 0.0494 0.0988 剩下的区间宽 0.0055，要 log₂(1/宽) = 7.51 比特才能指认它 看前一个字（按这句话里“前一个字”之后出现过什么来统计） 读入 葡 葡 萄 吃 不 吐 皮 ， 倒 0.0000 1.0000 葡 → 萄 萄 0.0000 0.2222 萄 → 皮 不 皮 倒 0.0000 0.2222 “葡”后面一定是“萄”，这一刀不切；最后区间宽 0.1111，只要 3.17 比特
图 7 · 算术编码每读一个字就按概率切一刀；模型猜得越准，切掉的越少，花的比特越少
图 7是用绕口令的字频编“葡萄皮”三个字。最后剩下的区间宽度等于三个字概率的乘积，写下这个区间里的一个数需要的比特数就是 $\sum\log_2(1/p)$，**每个符号花多少比特可以是小数**。下半部分换成一个看前一个字的模型：“葡”后面一定是“萄”，“萄”这一刀几乎不切，它就几乎不占比特。 表 6最后一列是我们照 1987 年 Witten、Neal、Cleary 那篇论文[^wnc]写的 32 位整数算术编码器的实测结果：p=5% 时每符号 0.2864 比特，和熵 0.2864 一致到小数点后四位，编完再解一遍也完全还原。 算术编码从理论上解决了编码器的问题：**模型给出什么概率，它就花多少比特，几乎没有浪费**。从此压缩算法的进步，几乎全部来自模型。1981 年里萨宁和兰登（Glen Langdon）把这个分工写成了一篇论文，压缩就是“建模”加“编码”两件事[^langdon]。 可惜算术编码也有专利。IBM 在八十年代申请了一系列算术编码的专利，1992 年的 JPEG 标准里同时定义了 Huffman 和算术编码两种方式，算术编码那一种通常能再小百分之几，却几乎没有软件支持[^jpeg]。后面我们还会看到，专利又一次改变了一个压缩器的设计。 ### 上下文模型：看前面几个字 编码器的问题解决了，模型该怎么做？最直接的想法是：**预测下一个字时，看看它前面是什么**。1984 年，克利里（John Cleary）和威滕（Ian Witten）提出了 PPM（部分匹配预测）[^ppm]：先看前 $k$ 个字，在这个上下文后面出现过的字里统计概率；如果当前的字在这个上下文后面从没出现过，就输出一个“逃逸”符号，退到前 $k-1$ 个字再查，一直退到不看上下文。 我们在本站文章上写了一个 60 行的 PPM：不做任何预训练，边读边统计，解压方用同样的规则就能同步重建出一样的模型。
本站文章（1,462,752 字节）用边读边学的上下文模型压缩
方法压缩后（字节）比特/字节
PPM，不看上下文713,3443.90
PPM，看前 1 个字498,0392.72
PPM，看前 2 个字454,0332.48
PPM，看前 3 个字444,3372.43
对照：开头那张表里的压缩器
bzip2 -9463,4952.53
xz -9483,6362.65
brotli -11485,2862.65
zstd -19494,1292.70
gzip -9613,8443.36

PPM 一栏是理想码长 Σlog₂(1/p)，接上前面那种算术编码器只会多几个字节。模型从空白开始，边压边学，解压方按同样的规则能同步重建。

表 8 · 看前 1 个字就比 gzip 好得多，看前 3 个字比所有常用压缩器都小
表 8里，只看前 1 个字，每字节就从 3.90 比特降到了 2.72 比特，已经比 gzip 好得多；看前 3 个字，降到 2.43 比特，比开头那张表里的所有压缩器都小。**模型看得越多，猜得越准，压得越小。** 那为什么开头那张表里没有 PPM 这类压缩器？因为它慢。每处理一个字都要查几阶上下文、更新几张统计表，再做一次算术编码，同样是 C 语言实现，PPM 类压缩器的速度通常只有 gzip 的几分之一，解压也一样慢；LZ77 解压时只是照着指针复制，快得多。九十年代的机器上，这个差距很要紧。**有没有办法拿到上下文模型的大部分好处，又不付出那么大的代价？** ## 五、先排序，再压缩 ### BWT：一个可以还原的重排 1994 年，DEC 的伯罗斯（Michael Burrows）和惠勒（David Wheeler）发表了一个奇怪的变换[^bwt]。惠勒在 1983 年就想到了它，十年后才和伯罗斯一起写成报告。 做法是这样的：把一段文字的所有循环移位（把开头的字一个个挪到末尾）列出来，按字典序排序，然后只取每一行的**最后一个字**。
BWT 处理绕口令 绕口令加结尾标记共 19 个字，19 个循环移位排序后取最后一列，得到“皮，萄萄$不倒不萄萄葡葡葡葡吃吃吐吐皮”，相同的字聚成了串。 把 19 个循环移位按字符编码排序，取每行最后一个字 第一列 最后一列 $ 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 葡 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 以“萄”开头的 4 行，最后一个字都是“葡”： 原文里“萄”前面总是“葡” 以“葡萄”开头的 4 行，最后一个字 是“吃”或“吐” 以“皮”开头的 2 行，最后是“萄” 输出：皮，萄萄$不倒不萄萄葡葡葡葡吃吃吐吐皮 （加上原文在第 5 行） “$”标记原文结尾；排在一起的行开头相同，它们的最后一个字就是这个开头在原文里的前一个字
图 9 · BWT 排序以后，出现在相同上下文前面的字聚到了一起，后面用很简单的方法就能压
图 9是绕口令的结果。排序后，以“萄”开头的四行排在一起，它们的最后一个字都是“葡”，因为原文里“萄”前面总是“葡”；以“葡”开头的行最后一个字都是“吃”或“吐”。输出的这一列 `皮，萄萄$不倒不萄萄葡葡葡葡吃吃吐吐皮` 里，相同的字成串地挤在了一起。 为什么会这样？排序是按每一行的开头排的，开头相同的行，它们最后一个字就是这段开头在原文里的**前一个字**。所以排序这一步，实际上是把“出现在相同上下文前面的字”归到了一起，相当于免费做了一次上下文建模。而这个变换是可以还原的：只要知道最后一列和原文在哪一行，就能一步步把原文推回来。 把重排后的结果再用很简单的方法（先把“最近出现过的字”换成小数字，再做熵编码）压一遍，就得到了接近 PPM 的压缩率，速度却快得多。 ### bzip2 1996 年，西沃德（Julian Seward）用 BWT 写了 bzip，熵编码用的是算术编码。因为担心算术编码的专利，他在 1997 年的 bzip2 里把它换成了 Huffman，宁可放弃一点压缩率[^bzip2]。 现在可以回答开头的第一个疑问了：本站文章是中文，而 LZ77 类的压缩器是按字节找重复的，一个汉字占三个字节，重复片段要足够长才划得来；BWT 排序时天然把相同上下文的字聚在一起，对这种“词汇量大、短语反复出现”的文字更有效。表 8里 bzip2 排在 xz 前面，也是这个原因。在英文的 enwik8 上，情况就反过来了，下一节会看到。 不过 bzip2 也有它的代价：它要把整块数据（最多 900KB）读进来排序，解压时也要做逆变换，解压速度只有 gzip 的五分之一到十分之一。到 2000 年以后，**压缩率和速度之间的取舍**变成了新的主题。 ## 六、更大的窗口与更快的速度 ### LZMA：把窗口开到几百兆 一条路是继续提高压缩率。俄罗斯程序员帕夫洛夫（Igor Pavlov）为他的 7-Zip 设计了 LZMA[^xz]：仍然是 LZ77 的框架，但窗口从 Deflate 的 32KB 扩大到几十上百 MB，能找到很远以前的重复；匹配之后的编码不用 Huffman，而是用一个带上下文的二进制区间编码器（算术编码的一种变体）；压缩时还会比较多种切分方法，选总比特最少的那一种。它压得很小，但压缩极慢。后来 Linux 世界把它做成了 xz，用来发布源码包和内核。 ### LZ4 与 zstd：快到可以随手压 另一条路是反过来：**压缩率差不多就行，但要非常快**。2010 年前后，数据中心里到处是要读写的数据，磁盘和网络变快了，CPU 花在 gzip 上的时间反而成了瓶颈。2011 年，法国工程师科莱（Yann Collet）发布了 LZ4[^lz4]：只做 LZ77，不做熵编码，所有设计都为速度让路，解压每秒能处理一两个 GB。 LZ4 压得不够小。科莱想要的是一个比 gzip 压得更小、又比 gzip 快得多的东西，他缺一个又快又不浪费比特的熵编码器。Huffman 快但有整数比特的浪费，算术编码精确但每个符号都要做乘除法，慢。 答案来自波兰的物理学家杜达（Jarek Duda）。他在 2009 年提出了**非对称数字系统（ANS）**[^duda]：把整个编码状态压在一个整数里，编码一个概率为 $p$ 的符号，大致就是让这个整数变成原来的 $1/p$ 倍，再把溢出的低位吐出来。它的压缩率和算术编码一样精确，而查表实现的版本（tANS）速度和 Huffman 差不多。杜达有意没有申请专利，任何人都可以用（2022 年微软拿到了一项 ANS 变体的美国专利，引起了不少争议[^msans]）。 科莱用 ANS 写了 FSE 编码器，再和一个改进过的 LZ77 组合起来，2016 年 8 月在 Facebook 发布了 Zstandard，也就是 zstd[^zstdfb]。它有从 1 到 22 的压缩级别，低级别比 gzip 快几倍，高级别接近 xz，而**不论用哪一级压，解压都一样快**。
同一台机器、单线程：压缩后占原来的比例与速度
压缩器年份enwik8（英文 100MB）本站文章（中文 1.4MB）压缩 MB/s解压 MB/s
lz4201157.3%65.3%4851,488
gzip -6199236.5%42.2%29271
gzip -9199236.5%42.0%21278
bzip2 -9199629.0%31.7%1929
xz -9200924.9%33.1%3.273
zstd -3201635.4%41.9%1931,222
zstd -19201626.9%33.8%4.01,083
brotli -11201527.0%33.2%0.8390

绿色是每列压得最小的。速度取自本站文章那一份，三次取最快。年份是格式或工具首次发布的年份，gzip 和 zlib 用的是同一个 Deflate，bzip2 的格式定于 1997 年。

表 10 · zstd -3 压得和 gzip 一样小，快好几倍；最小的压缩器因数据而异，而且都很慢
表 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 字节的字典**[^brotli]，里面是从大量网页里挑出来的常见单词和 HTML 片段，任何文件一开头就可以引用它。zstd 则提供了另一种办法：用同类数据先训练出一本字典，压缩和解压两边各存一份。
300 个几百字节的段落各自单独压缩：平均每段压到几字节
数据原始gzip -9zstd -19brotli -11zstd + 字典
本站文章的段落425353（83%）355（84%）287（68%）233（55%）
维基百科的段落462287（62%）284（61%）200（43%）196（42%）

brotli 用的是格式里内置的 122,784 字节字典；zstd 的字典是用另外 1,368 段（中文）或 2,460 段（英文）训练出的 32KB 字典，测试的 300 段不在其中。

表 11 · 几百字节的文件，前面没有可以引用的内容；自带或事先训练的字典能多压掉一截
表 11把本站文章和 enwik8 各切成 300 个几百字节的段落，逐段单独压缩。gzip 和不带字典的 zstd 只能压掉两成到四成，中文段落只压掉 16%；Brotli 靠内置字典好了一截；zstd 用同类段落训练出的 32KB 字典，中文段落压到了原来的 55%。 Brotli 在 2016 年进了 Chrome 和 Firefox，成了 gzip 之外最常见的网页压缩格式；2024 年 3 月的 Chrome 123 又加上了 zstd[^chromezstd]。但只要还有一个客户端只认 gzip，服务器就得留着它，这就是 gzip 至今还在的第二个原因：**新的格式只能增加，旧的格式很难退出**。 到这里，我们说的都是“无损压缩”，解压出来必须和原来一个字节都不差。可是开头的问题里还有一种文件：照片、音乐、视频，它们的压缩方式完全不同。 ## 七、有损压缩：扔掉看不出来的 ### 允许误差，问题就变了 一张 600×400 的照片，每个像素红绿蓝各 1 字节，原始大小 720,000 字节。用 PNG 无损压缩（先按相邻像素做差，再用 Deflate），只能压到 61%，因为照片里的噪点和细微的颜色变化几乎没有重复，也很难预测。 可是人看照片时，并不在意每个像素是不是一模一样。香农在 1959 年把这个问题也形式化了：**允许一定的误差，最少需要多少比特**，这叫率失真理论[^shannon59]。有损压缩要做的，就是找出人感觉不到的那部分信息，把它扔掉。 ### 余弦变换：把能量集中起来 问题是哪些信息人感觉不到？像素本身是不能随便扔的，扔掉任何一个都会留下一个洞。1974 年，阿哈迈德（Nasir Ahmed）等人提出了**离散余弦变换（DCT）**[^dct]：把图像切成 8×8 的小块，把每块 64 个像素换成 64 个“频率”系数，左上角是这一块的平均亮度，越往右下是越细的纹理。
DCT 把能量集中到左上角 咖啡杯照片切成 8×8 块做余弦变换，全图 91% 的能量在左上角那个平均亮度系数里；每块只留最大的 10 个系数，就保留了 96% 的能量，PSNR 31.6 dB。 8×8 块里 64 个系数各占全图能量多少 左上角 91.1% （这一块的平均亮度） 右边一格 1.7% 下边一格 2.2% 往右、往下：越来越细的横向、纵向纹理 颜色越深占得越多（对数刻度） 每块只留能量最大的 k 个系数 k = 1 79.2% k = 3 88.6% k = 6 93.4% k = 10 96.1% k = 64 100.0% 只留 k 个系数再变换回来 亮度 PSNR k = 3 26.5 dB k = 10 31.6 dB
图 12 · 照片做完余弦变换，能量集中在少数几个低频系数上，其余的大多可以扔掉
图 12是在一张咖啡杯照片[^coffee]上的实测。平均每个 8×8 块里，能量最大的一个系数就占了 79%，最大的 10 个占了 96%；全图能量的 91% 都在左上角那一格。照片里大部分区域是平滑的，细纹理很少，而人眼对细纹理的变化又本来就不敏感。只留每块最大的 10 个系数、其余全部置零再变换回来，亮度通道的峰值信噪比（PSNR，衡量和原图差多少的指标，30 dB 以上通常看不出明显差别）还有 31.6 dB。 1992 年的 JPEG 标准就是这个思路[^jpeg]：DCT 之后，按一张“量化表”把每个系数除以一个数再取整，高频系数除以大数，大多变成 0；剩下的再用游程编码加 Huffman 压缩。质量参数调的就是这张表的大小。
咖啡杯照片（600×400）在不同格式下的大小
格式字节占原始PSNR
原始 RGB720,000100%（原图）
PNG（无损）441,80161%无误差
JPEG 质量 95104,71114.5%37.5 dB
JPEG 质量 7541,6065.8%32.4 dB
JPEG 质量 5027,3553.8%30.5 dB
JPEG 质量 2015,1492.1%28.0 dB
JPEG 质量 56,5580.9%23.5 dB

PSNR 是和原图逐像素比较的峰值信噪比，越高越接近原图，30 dB 以上通常看不出明显差别；质量 5 时已经有明显的色块。用 Pillow 保存。

表 13 · 无损的 PNG 只压到六成；允许一点误差，JPEG 默认质量只要原始大小的 6%
表 13里，质量 75（大多数软件的默认值）的 JPEG 只有原始大小的 5.8%，是 PNG 的十分之一，肉眼几乎看不出差别；质量 5 时只剩 0.9%，色块就很明显了。 声音也是同样的道理。MP3 用的是心理声学模型：一个响的声音会盖住它附近频率上轻的声音，被盖住的部分不用记[^mp3]。视频还多一步，相邻两帧大部分内容相同，只记下哪些块移动到了哪里，又回到了 LZ77 “用指针代替重复”的老办法。 有损压缩把“压到多小”换成了“看起来差多少”，给了我们几十倍的压缩率。回到无损压缩，最后一个问题还没回答：**它的尽头在哪里？** ## 八、模型与压缩的极限 ### 不能所有文件都压小 先说一个简单的事实：**不存在一个能把所有文件都压小的压缩器**[^dce]。长度为 $n$ 比特的文件有 $2^n$ 个，而比它短的文件加起来只有 $2^n-1$ 个，不可能一一对应。任何压缩器把一些文件压小了，就一定会把另一些文件变大。压缩器能用，是因为我们关心的文件（文字、程序、图片）有规律，而随机的文件没有。
再用 gzip -9 压一遍
输入原来（字节）再压之后变化
1MB 随机字节1,048,5761,048,902+326
已经 gzip 过的本站文章613,844614,040+196
质量 75 的 JPEG 照片41,60641,472-134
表 14 · 没有规律、或者规律已经被拿走的数据，再压只会变大或几乎不变
表 14是三个例子：1MB 随机字节、已经 gzip 过的文件、已经是 JPEG 的照片，再用 gzip 压一遍。前两个反而变大了，JPEG 只小了 0.3%。一个好的压缩器输出的东西，本身就接近随机，规律已经被拿走了。这就是为什么把照片和视频打成 ZIP 包几乎不会变小。 ### 规律的尽头 那对有规律的文件，下限是多少？香农的熵只回答了一半，它假设我们已经知道文字的概率分布。真正的下限是这段文字的**最短描述**，也就是柯尔莫哥洛夫复杂度：能输出它的最短程序有多长。这个数在理论上是存在的，却被证明是不可计算的，我们永远没法确定某个压缩结果已经是最小。 所以压缩只能一点点地往下逼近。第四节已经说过，编码器在算术编码出现后就几乎没有浪费了，剩下能改进的只有模型：它对下一个字猜得越准，压得越小。从这里开始，压缩器的历史就是模型的历史，而模型一路变强的过程，和后来的大语言模型是同一条路。 ### 上下文混合：不只听一个模型的 PPM 每次只听一个上下文的意见：先问“前 3 个字”，没见过就退到“前 2 个字”。可是哪个上下文最可靠，处处不同。读到“吃葡萄倒吐葡”时，“前 1 个字是葡”几乎可以断定下一个是“萄”；读到一个新词的开头，看前 3 个字反而会被误导；读到表格、代码、网址，又需要完全不同的上下文，比如“上一行同一列是什么”。 2002 年起，马洪尼（Matt Mahoney）的 PAQ 系列换了一个思路[^paq]：同时运行几十上百个模型，有看前 1 到 6 个字节的，有看前一个完整单词的，有跳着看的，有专门对付表格和图片的，每个模型都给出自己的预测；再由一个**混合器**决定各听几分。为了让混合简单，PAQ 不直接预测下一个字节，而是一位一位地预测：下一位是 1 的概率是多少。每个模型报一个概率，混合器是一个很小的神经网络，把这些概率加权组合；压完一位，它就按预测错了多少，用梯度下降把权重调一下。哪个模型在当前这段数据上说得准，它的权重就涨上去。 2006 年，胡特（Marcus Hutter）以 PAQ 的一个版本为起点，设立了压缩维基百科的奖金，理由是压缩文字和理解文字本来就是同一个问题，后来的获奖者大多是 PAQ 的后代。混合带来的进步，在压缩榜上一目了然。
把 1GB 英文维基百科（enwik9）压到多小
压缩器年份模型怎么猜下一个字节压缩后比特/字节
gzip -9在前面 32KB 里找重复片段322.6 MB2.58
bzip2 -9整块排序后统计254.0 MB2.03
xz -9e在大窗口里找重复片段197.3 MB1.58
PPMd看前几个字节，只听一个上下文179.0 MB1.43
paq8hp122007几百个手写模型，小神经网络混合132.0 MB1.06
cmix v12014上千个手写模型混合128.6 MB1.03
nncp（LSTM）2019神经网络边压边学125.6 MB1.00
cmix v182019手写模型加小 LSTM 混合115.7 MB0.93
nncp v3.1（Transformer）2021约 2 亿参数，GPU 上边压边学108.4 MB0.87
nncp v3.2（Transformer）2023同上，再调参106.6 MB0.85

数据取自 Mahoney 的大文本压缩榜；前四行是常用压缩器的最高档。比特/字节只算压缩结果，不含解压程序。

表 15 · 模型从“找重复”到“混合上千个手写模型”再到“神经网络边压边学”，一代比一代压得小
表 15从上往下，是压缩器的模型一代比一代强的过程：gzip 只会找重复，PPMd 看前几个字节，paq8 和 cmix 混合成百上千个模型。混合的模型越多，压得越小，速度也越慢：每一位都要跑一遍所有模型，再跑一遍混合器。 ### 神经网络：边压边学 PAQ 里的模型都是人手写的：要看前几个字、要不要看单词、表格怎么对齐，全靠作者的经验。既然混合器已经是个小神经网络，能不能连模型也交给神经网络去学？ 2019 年，写过 QEMU 和 FFmpeg 的贝拉（Fabrice Bellard）发布了 nncp[^nncp]。它的模型就是一个神经网络，从随机的权重开始，一边读维基百科一边训练：每读一个字节，先给出下一个字节的概率交给算术编码器，再用这个字节算一次损失，做一步梯度下降。解压时，解压方从同样的随机权重出发，用同样的步骤训练，就能得到完全一样的预测。这对计算提出了一个苛刻的要求：两边每一次浮点运算的结果都必须一模一样，差一位，后面全部解错，所以 nncp 要自己控制所有的计算顺序。 第一版 nncp 用的是 LSTM，还压不过 cmix；2021 年换成约 2 亿参数的 Transformer，放到 GPU 上跑，登上了榜首（表 15最后两行）。这时的压缩器和语言模型已经没有区别了：它就是一个边读边学、预测下一个字的语言模型。**训练语言模型时最小化的交叉熵，正是这个压缩器每个字要花的平均比特数。** ### 大语言模型当压缩器 那么，一个已经读过海量文字的大语言模型，直接拿来当压缩器的模型会怎样？我们用一个 5 亿参数的开源模型 Qwen2.5-0.5B[^qwen] 试了一下：模型逐个 token 给出下一个 token 的概率，交给第四节那种算术编码器写成比特，解压时用同一个模型一边猜一边还原。压的是本文第一节的正文，它写于这个模型发布之后，模型不可能见过。
压本文第一节的正文（4,374 字节，1,702 个字）
压缩器压缩后（字节）比特/字节解压方还要带上
gzip -92,4424.47—
zstd -192,3694.33—
bzip2 -92,2814.17—
xz -9e2,4444.47—
brotli -112,1473.93内置 122KB 字典
PPM，先读过本站其余文章1,3702.501.46MB 文章的统计
Qwen2.5-0.5B + 算术编码6931.27近 1GB 的模型

语言模型一行是真实编码出来的比特串（5,543 比特），再用同一个模型解码，与原文逐字节一致。PPM 一行是理想码长。

表 16 · 读过海量文字的语言模型压得最小，代价是解压方要带上同一个近 1GB 的模型
表 16里，这个小模型把 4,374 字节压到了 693 字节，每字节 1.27 比特，不到 xz 的三分之一；预先读过本站其余 58 篇文章的 PPM，也只能压到每字节 2.50 比特。解压出来的文字和原文一个字节都不差。DeepMind 2023 年的论文在更大的模型上得到了同样的结论：不计模型本身的大小，大语言模型压文字、图片和声音都比专门的压缩器小[^deletang]。 但这个结果有两处要打折扣。 **第一，模型本身也要算进去。** 解压的人必须有一模一样的模型，这个模型有近 1GB，比被压的文字大几十万倍。对一段文字来说，“压缩结果加上解压程序”才是公平的比法，这就是第一节说过的两部分码。模型读过的东西越多，这个问题越明显：让它压“床前明月光，疑是地上霜。举头望明月，低头思故乡。”这 24 个字，第一个字“床”要 23.5 比特，后面 23 个字一共只要 13.6 比特，因为整首诗就存在模型的权重里。胡特奖从一开始就把解压程序的大小也算进成绩，就是为了堵住这个口子[^hutter]。 **第二，它太慢。** 在一台 4 核 CPU 上，这个小模型压 4,374 字节用了 162 秒，解压又用了 137 秒，相当于每秒不到 30 字节，比 gzip 慢了近百万倍。 所以大语言模型没有变成日常用的压缩器，它证明的是另一件事。从莫尔斯的铅字盒、Huffman 的字频表、PPM 的上下文，到 PAQ 的混合器和 Transformer，压缩器的编码器在 1976 年就基本定型了，七十年来真正在变的，一直是**模型对数据猜得有多准**；而一个模型猜得越准，看起来就越像“懂”了这些文字。这正是“压缩即智能”这句话的意思，它和大语言模型的关系，在[《梯度下降早就有了，大模型为什么最近几年才出现》](/blog/llm-why-now/)里有详细的展开。 ## 九、回到开头 现在回头看开头那张表和那几个问题。 **同样是“压缩”，这几个程序做的事情有什么不同？** 把一路上试过的结果排在一起就清楚了。
同一句话被各个算法压缩后的样子 绕口令原文 432 比特；Huffman 变成 52 比特的串，LZ77 和 LZW 把重复片段换成指针和编号，BWT 只是把字重新排序，算术编码把整句变成一个小数；读过本站文章的 PPM 要 202 比特，语言模型只要 70 比特；gzip 加上文件头和原文一样长。 同一句绕口令，经过各个算法以后 原文 UTF-8 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 e5 90 83 e8 91 a1 e8 90 84 e4 b8 8d e5 90 90 e8 91 a1 e8 90 … 432 比特 54 字节 Huffman 第一节 0101110001110011100101110001101011100110110011100101 52 比特 另需一张码表 LZ77 第二节 吃葡萄不吐(4,2)皮，不(10,3)倒(10,4) 12 个记号 9 个字 + 3 个指针 LZW 第二节 2 6 5 0 3 9 4 7 0 8 5 1 12 5 4 15 个编号 字典从 8 条长到 22 条 BWT 第五节 皮 ， 萄 萄 $ 不 倒 不 萄 萄 葡 葡 葡 葡 吃 吃 吐 吐 皮 再做“最近出现过”编号：5 8 7 0 3 4 5 1 3 0 8 0 0 0 7 0 8 0 8 19 个字 只换了顺序 算术编码 第四节，看字频 0.0111010000010001100001110011111100100010101001101010 52 比特 整句变成一个小数 PPM 读过本站文章 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 14 26 24 8 17 21 1 17 7 6 14 7 0 17 15 7 0 1 202 比特 没见过“葡萄” 语言模型 Qwen2.5-0.5B 吃 葡 萄 不 吐 葡 萄 皮 ， 不 吃 葡 萄 倒 吐 葡 萄 皮 17 4 4 8 3 2 2 5 3 3 3 1 1 14 1 0 0 0 70 比特 要带上近 1GB 的模型 gzip LZ77 + Huffman 7b 3a a1 f9 c5 c4 85 2f 26 b4 3c d9 d1 fb 74 c2 04 08 fb f9 ac 75 … 432 比特 加上文件头，和原文一样长 模型两行：柱子越高，这个字花的比特越多（数字是比特数）；强调色是指针、多字词条和每行的总比特
图 17 · 同一句话：Huffman 换成比特，LZ 换成指针，BWT 换个顺序，算术编码变成一个小数，模型压缩让猜得到的字几乎不花比特
图 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 重新排序，算术编码变成一个小数，模型压缩则让猜得到的字几乎不花比特。 ## 参考资料