AAAWgmp1bWIAAAAeanVtZGMycGEAEQAQgAAAqgA4m3EDYzJwYQAAABZcanVtYgAAAEdqdW1kYzJtYQARABCAAACqADibcQN1cm46YzJwYTo1MTY2YTM1Yi1mYjQ2LTRkYjAtOTc3Ni1mMWQ5YjNjOTliOWUAAAADl2p1bWIAAAApanVtZGMyYXMAEQAQgAAAqgA4m3EDYzJwYS5hc3NlcnRpb25zAAAAALxqdW1iAAAARGp1bWRjYm9yABEAEIAAAKoAOJtxE2MycGEuaW5ncmVkaWVudC52MwAAAAAYYzJzaFeFmpY7sq4y6LcLpAbpiukAAABwY2JvcqNpZGM6Zm9ybWF0bWltYWdlL3N2Zyt4bWxqaW5zdGFuY2VJRHgseG1wOmlpZDpmOTk1ZGI1MC04ZmFhLTQxMDktODMyZC00ZmFiMzUzZjczZGFscmVsYXRpb25zaGlwaHBhcmVudE9mAAAB4mp1bWIAAABBanVtZGNib3IAEQAQgAAAqgA4m3ETYzJwYS5hY3Rpb25zLnYyAAAAABhjMnNoQs1RkAuqUawJHlrZyV2kVgAAAZljYm9yomdhY3Rpb25zgqJmYWN0aW9ua2MycGEub3BlbmVkanBhcmFtZXRlcnOha2luZ3JlZGllbnRzgaJjdXJseC1zZWxmI2p1bWJmPWMycGEuYXNzZXJ0aW9ucy9jMnBhLmluZ3JlZGllbnQudjNkaGFzaFggD4AmmShCsALW/jTFYJdN/GAAM8aUhoRRBbAeDNJ0G++kZmFjdGlvbngdY29tLmFudGhyb3BpYy5jbGF1ZGUucHJvdmlkZWRqcGFyYW1ldGVyc6F4H2NvbS5hbnRocm9waWMub3JpZ2luLWNvbmZpZGVuY2VndW5rbm93bmtkZXNjcmlwdGlvbnhmQ2xhdWRlIHByb3ZpZGVkIHRoaXMgZmlsZSBhdCB0aGUgcmVxdWVzdCBvZiBhIHVzZXIgYW5kIG1heSBoYXZlIGNyZWF0ZWQgb3IgbW9kaWZpZWQgdGhlIGZpbGUgY29udGVudHMubXNvZnR3YXJlQWdlbnShZG5hbWVmQ2xhdWRlcmFsbEFjdGlvbnNJbmNsdWRlZPUAAADIanVtYgAAAEBqdW1kY2JvcgARABCAAACqADibcRNjMnBhLmhhc2guZGF0YQAAAAAYYzJzaPgMNv64Ws6qgNvoNV4EkDAAAACAY2JvcqVjYWxnZnNoYTI1NmNwYWRNAAAAAAAAAAAAAAAAAGRoYXNoWCDDIwqgM6onN2g+mOtDwQJm5VgQVD9VXrFQM30i3GcY+WRuYW1lbmp1bWJmIG1hbmlmZXN0amV4Y2x1c2lvbnOBomVzdGFydBjmZmxlbmd0aBkeBAAAAj5qdW1iAAAAJ2p1bWRjMmNsABEAEIAAAKoAOJtxA2MycGEuY2xhaW0udjIAAAACD2Nib3KlY2FsZ2ZzaGEyNTZpc2lnbmF0dXJleE1zZWxmI2p1bWJmPS9jMnBhL3VybjpjMnBhOjUxNjZhMzViLWZiNDYtNGRiMC05Nzc2LWYxZDliM2M5OWI5ZS9jMnBhLnNpZ25hdHVyZWppbnN0YW5jZUlEeCx4bXA6aWlkOjRiOWIxZWQwLTY2M2UtNDNkZi1iMDdhLTg2MTRiZDg0OThjNnJjcmVhdGVkX2Fzc2VydGlvbnODomN1cmx4LXNlbGYjanVtYmY9YzJwYS5hc3NlcnRpb25zL2MycGEuaW5ncmVkaWVudC52M2RoYXNoWCAPgCaZKEKwAtb+NMVgl038YAAzxpSGhFEFsB4M0nQb76JjdXJseCpzZWxmI2p1bWJmPWMycGEuYXNzZXJ0aW9ucy9jMnBhLmFjdGlvbnMudjJkaGFzaFggRo6t7ubZcJjO0JNBrY8FzNex0NCgvGzWkLSSPpH0gA6iY3VybHgpc2VsZiNqdW1iZj1jMnBhLmFzc2VydGlvbnMvYzJwYS5oYXNoLmRhdGFkaGFzaFggzYohAQ2rk3a5rVg+4cDJ2BkgOp3UpFxvDDCgGbmG2cB0Y2xhaW1fZ2VuZXJhdG9yX2luZm+jZG5hbWVvQW50aHJvcGljIEZpbGVzZ3ZlcnNpb25lMS4wLjBrc3BlY1ZlcnNpb25lMi40LjAAABA4anVtYgAAAChqdW1kYzJjcwARABCAAACqADibcQNjMnBhLnNpZ25hdHVyZQAAABAIY2JvctKEWQISogEmGCFZAgowggIGMIIBjaADAgECAhRA5aAK7sI50L64g/oGQgU9Z1UTADAKBggqhkjOPQQDAzBJMRcwFQYDVQQKEw5BbnRocm9waWMsIFBCQzEuMCwGA1UEAxMlQW50aHJvcGljIENvbnRlbnQgQ3JlZGVudGlhbHMgUm9vdCBDQTAeFw0yNjA4MDcxODQzNTZaFw0yODA4MDYxOTQzNTZaMEQxFzAVBgNVBAoTDkFudGhyb3BpYywgUEJDMSkwJwYDVQQDEyBBbnRocm9waWMgQ2xhdWRlIENvbnRlbnQgU2lnbmluZzBZMBMGByqGSM49AgEGCCqGSM49AwEHA0IABJh6CmvLUBgFFNU0vUKlOVtE6djd17L5SuwX0LemFisBM3dkd/3cyjxFA3Qo5S46fX0/ihY0VZ7mfb9KF703t5OjWDBWMA4GA1UdDwEB/wQEAwIHgDAVBgNVHSUEDjAMBgorBgEEAYPoXgIBMAwGA1UdEwEB/wQCMAAwHwYDVR0jBBgwFoAUzlHiBIFOZFsj+OPEz5o+nMHXXMIwCgYIKoZIzj0EAwMDZwAwZAIwMXMdFJ4BetLLVY7ORuE9noqbbAZOZn/aArXyTwFAZfKrPzxF2vPoJNf1+UCdg1XGAjBwX1zd9WGqYkqmL5SFqw1QySjr1zJfpJM9+1rdDwSPLMOPOjKuiXjoU/pUUeG9RwmhY3BhZFkNngAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAPZYQBSYRjrzOnK3k3AJ70Yv4yxiA7GtZMi6VpOGLaem4ItFnwoZT9PoTb4Pjeobqm82XJ8z/IG1y3xfUMPv3OFoBtY= 一條紙帶被壓短 左邊寫著繞口令“吃葡萄不吐葡萄皮”和四個壓縮器壓本站文章的結果。右邊一條格子紙帶上,重複出現的片段用弧線指回前面,紙帶穿過一臺壓機,出來只剩短短一截位元。 吃葡萄不吐 葡萄皮… 本站文章 1.46 MB 壓到 gzip 1992 42.0% bzip2 1996 31.7% xz 2009 33.1% zstd 2016 33.8%

把本站 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 是“劃劃點劃”12。

這個辦法到底好在哪?我們用 1 億位元組的英文維基百科(enwik8,壓縮界常用的測試檔案3)統計字母頻率,按國際電碼的約定計時:點佔 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 年,夏農在《通訊的數學理論》裡把這個問題算清楚了4。一個出現機率為 pp 的符號,最少要用 log⁡2(1/p)\log_2(1/p) 個位元來表示;對所有符號按出現機率取平均,得到的下限叫熵:

H=∑ipilog⁡21piH=\sum_i p_i\log_2\frac{1}{p_i}

英文 26 個字母等長編碼要 5 位元(24=162^4=16 不夠,25=322^5=32 夠),而按 enwik8 裡的字母頻率算,熵是 4.21 位元。也就是說,只靠“常用字母短一點”,最多能省下大約六分之一。

夏農同時指出,只要碼字滿足一個條件就不需要停頓:沒有哪個碼字是另一個碼字的開頭。比如 E 用 0、T 用 10、A 用 11,收到 01011 只能讀成 E、T、A。這樣的碼叫字首碼。夏農和 MIT 的範諾各自給了一種構造方法,從上往下把符號按機率儘量平分成兩組,一組前面加 0,另一組加 1,再對每組重複5。這個方法很好用,但並不總是最省。最省的字首碼該怎麼構造?

Huffman:從最罕見的兩個合併

1951 年,範諾在 MIT 開資訊理論課,允許學生寫一篇學期論文代替期末考試,題目就是找出最省的字首碼。研究生 Huffman 想了幾個月,眼看要放棄去準備考試,忽然想到了反過來的做法6:不從上往下分,而是從下往上合併。每次取出出現次數最少的兩個符號,把它們併成一個節點,次數相加,放回去,再取最少的兩個,直到只剩一個節點。從根往下走,左邊記 0、右邊記 1,走到每個符號的路徑就是它的碼字。

他在 1952 年發表了這個方法,並證明它構造出的字首碼一定是最省的7。我們拿開頭說的那句繞口令試一下:“吃葡萄不吐葡萄皮,不吃葡萄倒吐葡萄皮”。

繞口令的 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。

這裡要先引入一個貫穿後文的說法。任何一個壓縮器都可以拆成兩半:模型負責估計下一個符號出現的機率,編碼器負責按這些機率分配位元8。莫爾斯的模型是鉛字盒,Huffman 的模型是整份檔案的字頻,兩者都假設每個符號和前後無關。Huffman 已經把編碼器做到了這個模型下的最優,剩下的差距只能來自模型。可文字顯然不是一個個獨立擲出來的:“葡”後面幾乎總是“萄”,整句“吃葡萄”還會原樣再出現。怎樣利用這種重複?

二、重複的片段

LZ77:用指標代替重複

1977 年,以色列理工學院的齊夫(Jacob Ziv)和倫佩爾(Abraham Lempel)發表了一種完全不同的辦法9。它不統計頻率,而是在剛讀過的那一段文字(叫滑動視窗)裡找和當前位置相同的最長片段。找到了,就輸出一個指標“往回數 dd 個字,抄 ℓ\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:邊走邊建字典

第二年,兩人又發表了 LZ7810:不再往回找,而是把見過的片段一條條登記進一本字典,輸出字典裡的編號。1984 年,Sperry 公司的韋爾奇(Terry Welch)把它簡化成 LZW11:字典一開始只有單個字元,每輸出一個編號,就把“當前片段加下一個字”登記成新詞條。圖 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 交專利費12。當時 GIF 幾乎是網頁上唯一的圖片格式,這個訊息引起了很大的憤怒。同一周,一群程式設計師建了郵件列表,著手設計一個不受專利約束的替代格式,這就是 PNG。

Deflate:LZ77 加 Huffman

PNG 要換掉 LZW,現成的替代品來自另一場官司。1988 年,壓縮軟體 ARC 的公司 SEA 起訴菲爾·卡茨(Phil Katz),說他的 PKARC 抄襲了 ARC。官司以卡茨賠錢和解告終,他轉而設計了一個新的格式,ZIP。1993 年前後的 PKZIP 2.04 版把一個叫 Deflate 的方法定為預設13:先用 LZ77 把文字切成“原樣的字”和“指標”,再用 Huffman 給它們分配碼長。前一步消除重複,後一步利用頻率,兩件事合在了一起。

Deflate 用的 LZ77 和 Huffman 都沒有專利問題。1992 年,蓋伊(Jean-loup Gailly)和阿德勒(Mark Adler)為了替代受 LZW 專利約束的 compress,用同樣的思路寫出了 gzip14;1995 年兩人又把它做成了 zlib 庫,Deflate 後來寫進了 RFC 195115。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)各自給出了算術編碼16。它不給每個符號單獨分配碼字,而是把整條訊息對應到 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是用繞口令的字頻編“葡萄皮”三個字。最後剩下的區間寬度等於三個字機率的乘積,寫下這個區間裡的一個數需要的位元數就是 ∑log⁡2(1/p)\sum\log_2(1/p),每個符號花多少位元可以是小數。下半部分換成一個看前一個字的模型:“葡”後面一定是“萄”,“萄”這一刀幾乎不切,它就幾乎不佔位元。

表 6最後一列是我們照 1987 年 Witten、Neal、Cleary 那篇論文17寫的 32 位整數算術編碼器的實測結果:p=5% 時每符號 0.2864 位元,和熵 0.2864 一致到小數點後四位,編完再解一遍也完全還原。

算術編碼從理論上解決了編碼器的問題:模型給出什麼機率,它就花多少位元,幾乎沒有浪費。從此壓縮演算法的進步,幾乎全部來自模型。1981 年裡薩寧和蘭登(Glen Langdon)把這個分工寫成了一篇論文,壓縮就是“建模”加“編碼”兩件事8。

可惜算術編碼也有專利。IBM 在八十年代申請了一系列算術編碼的專利,1992 年的 JPEG 標準裡同時定義了 Huffman 和算術編碼兩種方式,算術編碼那一種通常能再小百分之幾,卻幾乎沒有軟體支援18。後面我們還會看到,專利又一次改變了一個壓縮器的設計。

上下文模型:看前面幾個字

編碼器的問題解決了,模型該怎麼做?最直接的想法是:預測下一個字時,看看它前面是什麼。1984 年,克利裡(John Cleary)和威滕(Ian Witten)提出了 PPM(部分匹配預測)19:先看前 kk 個字,在這個上下文後面出現過的字裡統計機率;如果當前的字在這個上下文後面從沒出現過,就輸出一個“逃逸”符號,退到前 k−1k-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)發表了一個奇怪的變換20。惠勒在 1983 年就想到了它,十年後才和伯羅斯一起寫成報告。

做法是這樣的:把一段文字的所有迴圈移位(把開頭的字一個個挪到末尾)列出來,按字典序排序,然後只取每一行的最後一個字。

BWT 處理繞口令 繞口令加結尾標記共 19 個字,19 個迴圈移位排序後取最後一列,得到“皮,萄萄$不倒不萄萄葡葡葡葡吃吃吐吐皮”,相同的字聚成了串。 把 19 個迴圈移位按字元編碼排序,取每行最後一個字 第一列 最後一列 $ 吃 葡 萄 不 吐 葡 萄 皮 , 不 吃 葡 萄 倒 吐 葡 萄 皮 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 , 不 吐 葡 萄 皮 , 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 , 不 吃 葡 萄 吃 葡 萄 不 吐 葡 萄 皮 , 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 , 不 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 , 不 吃 葡 萄 倒 吐 葡 萄 皮 , 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 , 不 吃 葡 萄 倒 吐 葡 萄 皮 , 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 萄 不 吐 葡 萄 皮 , 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 , 不 吃 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 , 不 吃 葡 萄 倒 吐 葡 萄 皮 , 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 葡 萄 不 吐 葡 萄 皮 , 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 , 不 吃 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 , 不 吃 葡 萄 倒 吐 葡 萄 皮 , 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 , 不 吃 葡 萄 倒 吐 葡 萄 皮 $ 吃 葡 萄 不 吐 葡 萄 皮 以“萄”開頭的 4 行,最後一個字都是“葡”: 原文裡“萄”前面總是“葡” 以“葡萄”開頭的 4 行,最後一個字 是“吃”或“吐” 以“皮”開頭的 2 行,最後是“萄” 輸出:皮,萄萄$不倒不萄萄葡葡葡葡吃吃吐吐皮 (加上原文在第 5 行) “$”標記原文結尾;排在一起的行開頭相同,它們的最後一個字就是這個開頭在原文裡的前一個字
圖 9 · BWT 排序以後,出現在相同上下文前面的字聚到了一起,後面用很簡單的方法就能壓

圖 9是繞口令的結果。排序後,以“萄”開頭的四行排在一起,它們的最後一個字都是“葡”,因為原文裡“萄”前面總是“葡”;以“葡”開頭的行最後一個字都是“吃”或“吐”。輸出的這一列 皮,萄萄$不倒不萄萄葡葡葡葡吃吃吐吐皮 裡,相同的字成串地擠在了一起。

為什麼會這樣?排序是按每一行的開頭排的,開頭相同的行,它們最後一個字就是這段開頭在原文裡的前一個字。所以排序這一步,實際上是把“出現在相同上下文前面的字”歸到了一起,相當於免費做了一次上下文建模。而這個變換是可以還原的:只要知道最後一列和原文在哪一行,就能一步步把原文推回來。

把重排後的結果再用很簡單的方法(先把“最近出現過的字”換成小數字,再做熵編碼)壓一遍,就得到了接近 PPM 的壓縮率,速度卻快得多。

bzip2

1996 年,西沃德(Julian Seward)用 BWT 寫了 bzip,熵編碼用的是算術編碼。因為擔心算術編碼的專利,他在 1997 年的 bzip2 裡把它換成了 Huffman,寧可放棄一點壓縮率21。

現在可以回答開頭的第一個疑問了:本站文章是中文,而 LZ77 類的壓縮器是按位元組找重複的,一個漢字佔三個位元組,重複片段要足夠長才划得來;BWT 排序時天然把相同上下文的字聚在一起,對這種“詞彙量大、短語反覆出現”的文字更有效。表 8裡 bzip2 排在 xz 前面,也是這個原因。在英文的 enwik8 上,情況就反過來了,下一節會看到。

不過 bzip2 也有它的代價:它要把整塊資料(最多 900KB)讀進來排序,解壓時也要做逆變換,解壓速度只有 gzip 的五分之一到十分之一。到 2000 年以後,壓縮率和速度之間的取捨變成了新的主題。

六、更大的視窗與更快的速度

LZMA:把視窗開到幾百兆

一條路是繼續提高壓縮率。俄羅斯程式設計師帕夫洛夫(Igor Pavlov)為他的 7-Zip 設計了 LZMA22:仍然是 LZ77 的框架,但視窗從 Deflate 的 32KB 擴大到幾十上百 MB,能找到很遠以前的重複;匹配之後的編碼不用 Huffman,而是用一個帶上下文的二進位制區間編碼器(算術編碼的一種變體);壓縮時還會比較多種切分方法,選總位元最少的那一種。它壓得很小,但壓縮極慢。後來 Linux 世界把它做成了 xz,用來發布原始碼包和核心。

LZ4 與 zstd:快到可以隨手壓

另一條路是反過來:壓縮率差不多就行,但要非常快。2010 年前後,資料中心裡到處是要讀寫的資料,磁碟和網路變快了,CPU 花在 gzip 上的時間反而成了瓶頸。2011 年,法國工程師科萊(Yann Collet)釋出了 LZ423:只做 LZ77,不做熵編碼,所有設計都為速度讓路,解壓每秒能處理一兩個 GB。

LZ4 壓得不夠小。科萊想要的是一個比 gzip 壓得更小、又比 gzip 快得多的東西,他缺一個又快又不浪費位元的熵編碼器。Huffman 快但有整數位元的浪費,算術編碼精確但每個符號都要做乘除法,慢。

答案來自波蘭的物理學家杜達(Jarek Duda)。他在 2009 年提出了非對稱數字系統(ANS)24:把整個編碼狀態壓在一個整數里,編碼一個機率為 pp 的符號,大致就是讓這個整數變成原來的 1/p1/p 倍,再把溢位的低位吐出來。它的壓縮率和算術編碼一樣精確,而查表實現的版本(tANS)速度和 Huffman 差不多。杜達有意沒有申請專利,任何人都可以用(2022 年微軟拿到了一項 ANS 變體的美國專利,引起了不少爭議25)。

科萊用 ANS 寫了 FSE 編碼器,再和一個改進過的 LZ77 組合起來,2016 年 8 月在 Facebook 釋出了 Zstandard,也就是 zstd26。它有從 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 位元組的字典27,裡面是從大量網頁裡挑出來的常見單詞和 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 又加上了 zstd28。但只要還有一個客戶端只認 gzip,伺服器就得留著它,這就是 gzip 至今還在的第二個原因:新的格式只能增加,舊的格式很難退出。

到這裡,我們說的都是“無失真壓縮”,解壓出來必須和原來一個位元組都不差。可是開頭的問題裡還有一種檔案:照片、音樂、影片,它們的壓縮方式完全不同。

七、有失真壓縮:扔掉看不出來的

允許誤差,問題就變了

一張 600×400 的照片,每個畫素紅綠藍各 1 位元組,原始大小 720,000 位元組。用 PNG 無失真壓縮(先按相鄰畫素做差,再用 Deflate),只能壓到 61%,因為照片裡的噪點和細微的顏色變化幾乎沒有重複,也很難預測。

可是人看照片時,並不在意每個畫素是不是一模一樣。夏農在 1959 年把這個問題也形式化了:允許一定的誤差,最少需要多少位元,這叫率失真理論29。有失真壓縮要做的,就是找出人感覺不到的那部分資訊,把它扔掉。

餘弦變換:把能量集中起來

問題是哪些資訊人感覺不到?畫素本身是不能隨便扔的,扔掉任何一個都會留下一個洞。1974 年,阿哈邁德(Nasir Ahmed)等人提出了離散餘弦變換(DCT)30:把影象切成 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是在一張咖啡杯照片31上的實測。平均每個 8×8 塊裡,能量最大的一個係數就佔了 79%,最大的 10 個佔了 96%;全圖能量的 91% 都在左上角那一格。照片裡大部分割槽域是平滑的,細紋理很少,而人眼對細紋理的變化又本來就不敏感。只留每塊最大的 10 個係數、其餘全部置零再變換回來,亮度通道的峰值訊雜比(PSNR,衡量和原圖差多少的指標,30 dB 以上通常看不出明顯差別)還有 31.6 dB。

1992 年的 JPEG 標準就是這個思路18: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 用的是心理聲學模型:一個響的聲音會蓋住它附近頻率上輕的聲音,被蓋住的部分不用記32。影片還多一步,相鄰兩幀大部分內容相同,只記下哪些塊移動到了哪裡,又回到了 LZ77 “用指標代替重複”的老辦法。

有失真壓縮把“壓到多小”換成了“看起來差多少”,給了我們幾十倍的壓縮率。回到無失真壓縮,最後一個問題還沒回答:它的盡頭在哪裡?

八、模型與壓縮的極限

不能所有檔案都壓小

先說一個簡單的事實:不存在一個能把所有檔案都壓小的壓縮器33。長度為 nn 位元的檔案有 2n2^n 個,而比它短的檔案加起來只有 2n−12^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 系列換了一個思路34:同時執行幾十上百個模型,有看前 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)釋出了 nncp35。它的模型就是一個神經網路,從隨機的權重開始,一邊讀維基百科一邊訓練:每讀一個位元組,先給出下一個位元組的機率交給算術編碼器,再用這個位元組算一次損失,做一步梯度下降。解壓時,解壓方從同樣的隨機權重出發,用同樣的步驟訓練,就能得到完全一樣的預測。這對計算提出了一個苛刻的要求:兩邊每一次浮點運算的結果都必須一模一樣,差一位,後面全部解錯,所以 nncp 要自己控制所有的計算順序。

第一版 nncp 用的是 LSTM,還壓不過 cmix;2021 年換成約 2 億引數的 Transformer,放到 GPU 上跑,登上了榜首(表 15最後兩行)。這時的壓縮器和語言模型已經沒有區別了:它就是一個邊讀邊學、預測下一個字的語言模型。訓練語言模型時最小化的交叉熵,正是這個壓縮器每個字要花的平均位元數。

大語言模型當壓縮器

那麼,一個已經讀過海量文字的大語言模型,直接拿來當壓縮器的模型會怎樣?我們用一個 5 億引數的開源模型 Qwen2.5-0.5B36 試了一下:模型逐個 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 年的論文在更大的模型上得到了同樣的結論:不計模型本身的大小,大語言模型壓文字、圖片和聲音都比專門的壓縮器小37。

但這個結果有兩處要打折扣。

第一,模型本身也要算進去。 解壓的人必須有一模一樣的模型,這個模型有近 1GB,比被壓的文字大幾十萬倍。對一段文字來說,“壓縮結果加上解壓程式”才是公平的比法,這就是第一節說過的兩部分碼。模型讀過的東西越多,這個問題越明顯:讓它壓“床前明月光,疑是地上霜。舉頭望明月,低頭思故鄉。”這 24 個字,第一個字“床”要 23.5 位元,後面 23 個字一共只要 13.6 位元,因為整首詩就存在模型的權重裡。胡特獎從一開始就把解壓程式的大小也算進成績,就是為了堵住這個口子38。

第二,它太慢。 在一臺 4 核 CPU 上,這個小模型壓 4,374 位元組用了 162 秒,解壓又用了 137 秒,相當於每秒不到 30 位元組,比 gzip 慢了近百萬倍。

所以大語言模型沒有變成日常用的壓縮器,它證明的是另一件事。從莫爾斯的鉛字盒、Huffman 的字頻表、PPM 的上下文,到 PAQ 的混合器和 Transformer,壓縮器的編碼器在 1976 年就基本定型了,七十年來真正在變的,一直是模型對資料猜得有多準;而一個模型猜得越準,看起來就越像“懂”了這些文字。這正是“壓縮即智慧”這句話的意思,它和大語言模型的關係,在《梯度下降早就有了,大模型為什麼最近幾年才出現》裡有詳細的展開。

九、回到開頭

現在回頭看開頭那張表和那幾個問題。

同樣是“壓縮”,這幾個程式做的事情有什麼不同? 把一路上試過的結果排在一起就清楚了。

同一句話被各個演算法壓縮後的樣子 繞口令原文 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 重新排序,算術編碼變成一個小數,模型壓縮則讓猜得到的字幾乎不花位元。

參考資料

參考資料

  1. The Information: A History, a Theory, a FloodJames Gleick · Pantheon Books · 2011第 5 章講莫爾斯電碼:維爾(Alfred Vail)到莫里斯敦一家報社數鉛字盒裡每個字母的鉛字,按多少分配點劃。 ↩

  2. A Forgotten History: Alfred Vail and Samuel MorseSmithsonian Institution Archivessiarchives.si.edu ↗電碼的署名是莫爾斯,按字母頻率設計碼錶的工作很大程度上出自維爾,這一點至今有爭議。https://siarchives.si.edu/blog/forgotten-history-alfred-vail-and-samuel-morse ↩

  3. Large Text Compression BenchmarkMatt Mahoneymattmahoney.net ↗enwik8、enwik9 的出處,也是各壓縮器在 enwik9 上的成績來源。https://mattmahoney.net/dc/text.html ↩

  4. A Mathematical Theory of CommunicationClaude Shannon · Bell System Technical Journal 27 · 1948doi.org ↗https://doi.org/10.1002/j.1538-7305.1948.tb01338.x ↩

  5. The Transmission of InformationRobert Fano · MIT Research Laboratory of Electronics, Technical Report 65 · 1949夏農–範諾編碼:自上而下把符號按機率一分為二,不保證最優。 ↩

  6. Profile: David A. HuffmanGary Stix · Scientific American 265(3) · 19911951 年範諾的資訊理論課上,學生可以寫學期論文代替期末考試,題目是找最省的二進位制編碼;Huffman 在快放棄時想到了自下而上合併的辦法。 ↩

  7. A Method for the Construction of Minimum-Redundancy CodesDavid Huffman · Proceedings of the IRE 40(9) · 1952doi.org ↗https://doi.org/10.1109/JRPROC.1952.273898 ↩

  8. Universal Modeling and CodingJorma Rissanen, Glen Langdon · IEEE Transactions on Information Theory 27(1) · 1981doi.org ↗把壓縮拆成“建模”和“編碼”兩部分的經典表述。https://doi.org/10.1109/TIT.1981.1056282 ↩ ↩2

  9. A Universal Algorithm for Sequential Data CompressionJacob Ziv, Abraham Lempel · IEEE Transactions on Information Theory 23(3) · 1977doi.org ↗https://doi.org/10.1109/TIT.1977.1055714 ↩

  10. Compression of Individual Sequences via Variable-Rate CodingJacob Ziv, Abraham Lempel · IEEE Transactions on Information Theory 24(5) · 1978doi.org ↗https://doi.org/10.1109/TIT.1978.1055934 ↩

  11. A Technique for High-Performance Data CompressionTerry Welch · IEEE Computer 17(6) · 1984doi.org ↗對應專利 US 4,558,302,1985 年 12 月授權,後歸 Unisys,美國專利 2003 年 6 月 20 日到期。https://doi.org/10.1109/MC.1984.1659158 ↩

  12. History of the Portable Network Graphics (PNG) FormatGreg Roelofs · libpng.orglibpng.org ↗1994 年 12 月 28 日 CompuServe 宣佈 GIF 軟體要向 Unisys 交 LZW 專利費;同一周 PNG 的郵件列表成立,1996 年 10 月 PNG 1.0 成為 W3C 推薦標準。https://www.libpng.org/pub/png/pnghist.html ↩

  13. PKZIPWikipediaen.wikipedia.org ↗1988 年 SEA 起訴 Katz 的 PKARC 抄襲 ARC,Katz 隨後設計了 ZIP 格式;PKZIP 2.04 系列(1992 年底到 1993 年)把 Deflate 作為預設方法。https://en.wikipedia.org/wiki/PKZIP ↩

  14. GzipWikipediaen.wikipedia.org ↗Jean-loup Gailly 和 Mark Adler 編寫,0.1 版 1992 年 10 月 31 日釋出,1.0 版 1993 年 2 月;目的是替代受 LZW 專利約束的 Unix compress。https://en.wikipedia.org/wiki/Gzip ↩

  15. RFC 1951: DEFLATE Compressed Data Format Specification version 1.3L. Peter Deutsch · IETF · 1996rfc-editor.org ↗https://www.rfc-editor.org/rfc/rfc1951 ↩

  16. Generalized Kraft Inequality and Arithmetic CodingJorma Rissanen · IBM Journal of Research and Development 20(3) · 1976doi.org ↗https://doi.org/10.1147/rd.203.0198 ↩

  17. Arithmetic Coding for Data CompressionIan Witten, Radford Neal, John Cleary · Communications of the ACM 30(6) · 1987doi.org ↗第一份公開、可直接使用的整數算術編碼實現;本文實驗裡的編碼器就是照它的做法寫的。https://doi.org/10.1145/214762.214771 ↩

  18. ITU-T T.81: Digital Compression and Coding of Continuous-Tone Still ImagesITU-T / ISO/IEC 10918-1 · 1992w3.org ↗標準裡同時定義了 Huffman 和算術編碼兩種熵編碼;算術編碼那一種因為專利幾乎沒人用。https://www.w3.org/Graphics/JPEG/itu-t81.pdf ↩ ↩2

  19. Data Compression Using Adaptive Coding and Partial String MatchingJohn Cleary, Ian Witten · IEEE Transactions on Communications 32(4) · 1984doi.org ↗https://doi.org/10.1109/TCOM.1984.1096090 ↩

  20. A Block-sorting Lossless Data Compression AlgorithmMichael Burrows, David Wheeler · DEC Systems Research Center, Research Report 124 · 1994-05-10hpl.hp.com ↗https://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf ↩

  21. bzip2Wikipediaen.wikipedia.org ↗Julian Seward 1996 年 7 月釋出 bzip 0.15,用算術編碼;因為專利顧慮,1997 年 8 月的 bzip2 0.1 改用 Huffman,格式與 bzip 不相容。https://en.wikipedia.org/wiki/Bzip2 ↩

  22. XZ UtilsTukaani Projecttukaani.org ↗LZMA 由 Igor Pavlov 為 7-Zip 設計;XZ Utils 由 Lasse Collin 維護,xz 格式用的是改進版 LZMA2。https://tukaani.org/xz/ ↩

  23. LZ4 - Extremely fast compressionYann Collet · GitHubgithub.com ↗https://github.com/lz4/lz4 ↩

  24. Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic codingJarek Duda · arXiv · 2013arxiv.org ↗ANS 的第一版預印本在 2009 年;Duda 有意不申請專利。https://arxiv.org/abs/1311.2540 ↩

  25. Microsoft wins data-encoding patent despite inventor's efforts to keep it freeThe Register · 2022-02-17theregister.com ↗https://www.theregister.com/2022/02/17/microsoft_ans_patent/ ↩

  26. Smaller and faster data compression with ZstandardYann Collet, Chip Turner · Engineering at Meta · 2016-08-31engineering.fb.com ↗https://engineering.fb.com/2016/08/31/core-infra/smaller-and-faster-data-compression-with-zstandard/ ↩

  27. RFC 7932: Brotli Compressed Data FormatJyrki Alakuijala, Zoltán Szabadka · IETF · 2016rfc-editor.org ↗格式自帶一本 122,784 位元組的靜態字典(第 8 節、附錄 A)。https://www.rfc-editor.org/rfc/rfc7932 ↩

  28. Intent to Ship: Zstd Content-Encodingblink-dev · 2024groups.google.com ↗Chrome 123(2024 年 3 月)起接受 Content-Encoding: zstd。https://groups.google.com/a/chromium.org/g/blink-dev/c/GFFOLCF12a4/m/crdNkVeaAQAJ ↩

  29. Coding Theorems for a Discrete Source with a Fidelity CriterionClaude Shannon · IRE National Convention Record 7(4) · 1959率失真理論:允許一定誤差時,最少要多少位元。 ↩

  30. Discrete Cosine TransformNasir Ahmed, T. Natarajan, K. R. Rao · IEEE Transactions on Computers C-23(1) · 1974doi.org ↗https://doi.org/10.1109/T-C.1974.223784 ↩

  31. skimage.data.coffeescikit-imagescikit-image.org ↗實驗用的咖啡杯照片,600×400,作者 Rachel Michetti,以 CC0 釋出。https://scikit-image.org/docs/stable/api/skimage.data.html#skimage.data.coffee ↩

  32. The story of mp3Fraunhofer IISiis.fraunhofer.de ↗https://www.iis.fraunhofer.de/en/ff/amm/consumer-electronics/mp3.html ↩

  33. Data Compression ExplainedMatt Mahoneymattmahoney.net ↗壓縮的入門長文,包括“沒有壓縮器能把所有檔案都壓小”的計數論證和 PAQ 的上下文混合。https://mattmahoney.net/dc/dce.html ↩

  34. The PAQ Data Compression ProgramsMatt Mahoneymattmahoney.net ↗PAQ 的上下文混合:許多模型各自預測下一位,由線上訓練的神經網路混合。PAQ 系列始於 2002 年。https://mattmahoney.net/dc/paq.html ↩

  35. NNCP: Lossless Data Compression with Neural NetworksFabrice Bellardbellard.org ↗邊壓邊訓練的 LSTM / Transformer 壓縮器;解壓要逐位復現壓縮時的浮點運算。https://bellard.org/nncp/ ↩

  36. Qwen2.5 Technical ReportQwen Team · arXiv · 2024arxiv.org ↗實驗用的是其中最小的 Qwen2.5-0.5B 基礎模型(約 4.9 億引數)。https://arxiv.org/abs/2412.15115 ↩

  37. Language Modeling Is CompressionGrégoire Delétang 等 · ICLR 2024 · 2023arxiv.org ↗https://arxiv.org/abs/2309.10668 ↩

  38. 500'000€ Prize for Compressing Human KnowledgeMarcus Hutter · Hutter Prizeprize.hutter1.net ↗http://prize.hutter1.net/ ↩