為了逃避考試,他發明了最好的壓縮算法(的一半)

追踪科技
1粉絲
38 次觀看·2026年5月24日
AI 生成·可能包含錯誤
視頻概述
AI 生成這段影片詳細介紹了最常見的壓縮格式 ZIP 的誕生歷史及其背後的技術原理。ZIP 的核心是由 LZ77 算法與霍夫曼編碼(Huffman Coding)縫合而成的 Deflate 算法。影片從信息論的基礎出發,解釋了如何透過「不等長編碼」來節省空間,並探討了在專利爭端與開源趨勢的影響下,ZIP 如何擊敗其他競爭格式,最終成為現代計算機的基礎設施。
如果你把一個幻燈片的後罪名改成Zip
會發生什麼
雙擊它
你就能直接看到裏面的文字和圖片
而且不僅是PPT
我們日常使用的Office三件套
瀏覽的網頁
安卓安裝包
APK
甚至電子書
它們的本質都是Zip格式的壓縮包
Zip的誕生充滿了巧合與波折
它的一半算法是爲不想考試的研究生髮明的
而另一半算法
和我們每天發的表情包息息相關
將它們縫在一起的
卻是爲打出了專利官司的程序員
大家好
歡迎來到亮子味
今天我們來聊聊
這個最常見的壓縮格式
是怎麼誕生的
1951年
MIT的羅伯特法諾教授
在信息論課上公佈了一個好消息
各位同學
你們可以不參加期末考試
只要改進一下
剛剛講的壓縮算法就行
一位叫霍夫曼的研究生一聽
就開始專心研究怎麼逃避考試
法諾教授講的壓縮算法
核心思想就三個字
不等長
在1951年
比較流行的Univac-1計算機
靠磁帶來保存數據
而一條磁帶上各個位置的寬度一樣
每個英文字母都會佔用7個比特
這叫做等長存儲
但一篇文章裏
字母ABCDEFG數量顯然不一樣
如果讓頻率高的字母只佔用一兩個比特
頻率低的字母多用幾個比特
讓它們不等長
空間不就省下來了嗎
那該怎麼決定它們有多長呢
法諾教授表示
你需要種一棵樹
二叉樹
舉個例子
要壓縮這句繞口令
我們就把各個字符的頻率從高到低排列
然後大致對半分
A和N加起來的概率是51.6%
剩下的概率總和爲48.3%
經過第一次二分
就可以確定字母的首位編碼
現在第一個集合中只剩下了A和N
直接再次二分
就有了第二位編碼
現在我們用00和01兩位比特
就可以表示出出現次數最多的A和N了
這可比7位比特節省多了
在另一個集合中
我們再不斷重複按概率對半分的步驟
C是100
而出現次數比較少的I是1111
這樣就完成了不等長壓縮編碼
長度的變化體現了相容信息論的精髓
概率越小信息量越大
你今天出門喝了一瓶水
和你給三體人廣播了座標
都是十個字
但後者的信息量顯然更多
所以相容悟出了一個真理
只要知道了各個符號的概率
就可以算出它能被壓縮的極限大小
這個極限就叫做相容信息商
它可以衡量壓縮算法到底夠不夠耗時
剛纔那句熱火鈴的信息商是2.843比特
而用這顆二叉數編碼後
平均每個符號需要2.903比特
確實壓縮了
但和極限還有點距離
所以它如今只出現在信息論教材裏
沒有什麼實際應用場景
法諾教授佈置的作業
就是找到一個更逼近信息商的算法
但他並沒有告訴學生
這算法就是他和相農搞出來的
而且他們都沒想出來怎麼改進
但他在課上拋出的這塊磚
引的不是玉
而是未來的Zip
甚至可以說是整個壓縮算法領域的奠基石
啥也不知道的霍夫曼奮鬥了好幾個月
眼看還有一週就要考試了
卻一無所獲
就在他決定開白
把筆記本丟進垃圾桶的瞬間
一個天才般的想法冒了出來
如果不是二分
而是劇類呢
我們不從概率最大的A和N開始
而是把概率最小的O和U合併在一起
得到一個概率爲6.4%的集合
像這樣一直合併概率最小的部分
不斷重複
就自下而上得到了一顆二叉數
將向左的節點命名爲0
向右的節點命名爲1
我們就爲字母賦予了不同嫦娥的編碼
這裏的A是01
L是00100
O則是000000
這就是霍夫曼編碼
它可以保證用最長的一串數字
來代表概率最小的字符
值得一提的是
有些壓縮算法像英語
符號之間需要空格
但相同法諾和霍夫曼編碼更像是漢語
哪怕直接寫一長串編碼
也完全不會搞錯寫的內容
你只需要按順序在這顆二叉數上移動
走到盡頭就輸出結果再回到根節點上
重新開始移動就行了
換句話說
任何一個字符的編碼
都不會是另一個字符編碼的前半部分
這種特性叫做非前綴碼
在霍夫曼編碼下
這句話的平均碼長只有2.864
比相同法諾編碼的2.903要小
當法諾看到這份簡潔優雅的答案時
不由用意大利風味的英語感嘆
原來就這麼簡單
這就是ZIP加速的一半核心算法
但顯然霍夫曼編碼離傷還有點距離
沒有壓縮至極限
如果把概率寫成2的-k次方的形式
只有當字符的編碼長度剛好都等於k時
霍夫曼編碼的平均碼長才能等於信息商
但現實中
每個字符的概率不一定剛好是
1 2 1 4 1 1 8這樣的數字
我們也沒法用零點幾個比特來表示字符
有沒有更好的算法呢
當然有
但當時的傳真機
到後來的MP3
圖像的GPEG
乃至後來的BJ2 ZIP壓縮格式
都選擇了霍夫曼編碼
爲啥呢
因爲更好的算法要花錢
1976年
IBM研究院的Resennen研究出了
能夠無限逼近傷的算術編碼
他的思路有點像避規和分形
以剛纔的繞口令爲例
一共有11種字母
我們就把長度爲1的線段
分爲11份
每條線段的長度等於各個字母的概率
字母A就是0到0.29
而字母N就是0.29到0.516
要寫出看這個單詞
我們就先選中字母C的區間0.516到0.71
將它按同樣的比例分成11份
再選中第一個區間0.516到0.57226
這就是A
N也是同樣的辦法
不斷重複
我們就能得到一個非常小的區間
可以用其中的小數來表示
這個算法看着就很好使
所以IBM趕緊給他註冊了專利
準備收錢
但當時的電腦性能撐不起這麼複雜的浮點運算
相比之下
霍夫曼編碼還免費
程序員們迅速達成了一致
還是開源好
隨着計算機和互聯網的發展
大家需要存儲或者傳輸給別人的信息也越來越多
但那時候
一張5.25英寸軟盤的容量只有360KB或者1.2MB
最大的3.5英寸軟盤也只有不到3MB
如何在這麼小的空間裏保存更多的數據呢
大家急需更好的壓縮算法
而這引出了另一種壓縮思路
也是Zip壓縮格式的另一半核心
當個復讀機
細心的觀衆朋友應該已經發現了
這句繞口令中
看這個單詞會反覆出現
霍夫曼編碼壓縮的是字母
如果我們能夠壓縮詞
是不是就能夠提高效率呢
這就是Zip和IBM
之前在輸入輸出數據時
每次只讀取一個字符
假如我們把這個窗口拉長
讓它在數據流上滑動
同時檢查之前和之後的數據
遇到寫過的詞組時就記下兩個數字
它離現在有多遠
以及一次需要複製多少個字符
這樣只需要兩個數字就完成了壓縮
它的優點在於只需要遍歷一遍數據
而霍夫曼編碼需要兩遍
所以它更快
這是最早也是應用最廣泛的LZ算法
它正是Zip壓縮格式的另一半核心
和霍夫曼算法類似
LZ77算法並不是完美的
它還有兩個改進型
1978年它們又給窗口塞了一個字頂
遇到新詞就記到小本本上
已經有的舊詞則可以直接提出來
然後順帶輸出下一個字符
窗口不斷和詞典交互
就能記得更牢
因爲當時還不允許爲軟件註冊專利
所以Lamppost所在的公司爲它專門造了臺硬件
然後把硬件和軟件一起註冊專利
後來Sperry公司的另一位研究員Terry Welch
爲LZ78算法做出了第二次改進
先把整條信息裏的三個字符全部存入詞典裏
後面每次循環時
每次多向後讀取一個字符
組合成一個新詞
再寫入詞典
如此循環
我們就可以把信息一次性壓縮完成
比如ababab
就可以壓縮成簡短的01241
於是LZ的後面又加上了一個人的首字母
變成了LZW算法
如果覺得不好記
我們很歡迎大家記成量子位算法
如今LZW算法最大的貢獻
就是你每天發的動圖表情包
每張GIF圖片都用到了這種壓縮技術
那LZW算法火了嗎
爲啥後來的ZIP壓縮
還是選擇了最原始的LZ77
而不是更好的LZW算法呢
答案依然是專利
以GIF格式爲例
它最初由ComServe公司發明
完全免費
1944年
UNISYS公司突然喊話
我有LZW算法的專利
都來交錢
如果你想把GIF用在商業行爲上
就欠UNISYS一份專利錢
不過別擔心
這個專利在2004年7月已經過期了
但當時的限制讓一些網友退而求其次
將免費的LZ77算法和其他壓縮算法
縫合起來
製作高效的壓縮軟件
這就是ZIP壓縮爲什麼選擇了LZ77和霍夫曼編碼
而ZIP壓縮算法爲何會誕生
又是怎麼流行開的
就是另一場版權戰爭的故事了
把時間倒退回1984年
Tom Hennessey開始在BBS論壇上
銷售採用了LZ算法的壓縮軟件ARC
但1987年
他的朋友在一本電腦雜誌上看到了兩條廣告
一條是他們的ARC
另一個是極其相似的壓縮軟件
PKARC
Tom Hennessey非常震驚
抄襲也就算了
還貼臉宣傳
他決定起訴PKARC的作者Philip Case
並打贏了官司
一位軟件專家找到了關鍵證據
PKARC裏的註釋就連拼寫錯誤都和ARC一樣
但當時的人們對Philip Case這種個人開發者抱有同情
開始攻擊和排斥ARC
這直接導致了ARC軟件在商業上的潰敗
因此Tom對此一直耿耿於懷
聽聞Case因酗酒去世時
Tom用ARC版權聲明的最後一句話
如此評價他
如果你不遵守本薛克協議的條款
那麼你的良心將停繞你一生
另一邊Philip Case停止銷售PKARC後
想出另一種壓縮方式
把LZ77和霍夫曼編碼縫在一起
在LZ77編碼的部分中
他先使用一個32KB的窗口
把所有的數據過一遍
如果重複字符的長度超過了三個字節
就記下它的長度 位置和距離
接着他種下了兩棵霍夫曼樹
一棵用來記錄內容長度
而另一棵樹用來記錄距離
也就是重複字符有多遠
但別忘了
這個滑動窗口只有32768個字節的長度
那時候的Macintosh Classic電腦
也只有2MB內存
如果每個距離都用這麼長的位數來記
太吃內存了
接下來就是這個算法最奇妙的地方
他給距離又畫了一個表
把32768字節分成了30段
每段又單獨附了一個編碼
短距離用短的碼
長距離就用長的碼
這個過程有點像建一棟道金字塔型的大廈
它一共有30層
要找數據時先確定樓層
再找門牌號
大多數情況下
人們要找的都是下面幾層數據
找起來就會很快
也節約了不少空間
1993年
他在PKZip2.0裏發表了這套算法
命名爲Deflate
意思是可以讓文件像放氣的氣球一樣變小
使用PKZip2.0打包文件後
後罪名就是如今我們最熟悉的.zip
在PKZip2.0中
他還放了一份手冊
詳細說明了如何編寫和使用Deflate算法
誰都可以自由使用
僅僅一年後
Unix公司開始向LZW算法收費
人們急需.zip格式的替代品
UseNet論壇上有一群成員提議
那我們自己寫一個不是.zip的圖片壓縮格式吧
於是他們起草了一個文件名可以自我遞歸的新格式
Ping
意爲Ping is not.zip
也就是後來的PNG圖片
但要創造一種標準的圖片格式
得寫個壓縮算法的庫
接下這個活兒的是Rinlop Gelly和Mark Elder
他們一下子又看中了免費開源的Deflate算法
以它爲基礎寫了一個壓縮算法庫
ZLip
這個庫的體積小
依賴弱
所以很容易遷移
它不僅被用在了PNG裏
後來微軟的Office
Adobe Photoshop
乃至幾乎所有的操作系統
都內置了ZLip庫的接口
所以不管你用什麼電腦
都可以直接打開Zip格式的壓縮包
順帶一提
現代互聯網的網頁壓縮格式Gzip
也是他們兩人發明的
同樣受限於LZW的專利問題
他們在PKZip 2.0發佈後不久
就把Gzip也改成了Deflate壓縮
就這樣
在博夫曼編碼和LZ77算法的支撐下
ZLip成爲了現代計算機的基礎設施
Zip壓縮格式就此一統江湖
而Deflate壓縮的發明者
Philip Keyes也並沒有被大家遺忘
如果你用16進制直接查看一個PPT
會看到它的末尾是博夫曼算法
而文件中各個部分的分格符
都是兩個英文字母
PK
這是Philip Keyes的首字母
也是版權戰爭後留下的印記
本期視頻到這裏就結束了
如果你覺得有所收穫
歡迎留下評論
點贊投幣轉發
一鍵三連
我們下期節目再見
