改變世界的無(wú)損壓縮算法發(fā)展史

近日，國(guó)際電氣與電子工程學(xué)會(huì)（Institute of Electrical and Electronics Engineers，簡(jiǎn)稱 IEEE）宣布，授予 IEEE 終身 Fellow Jacob Ziv 2021 年度 IEEE 榮譽(yù)勛章。

這位如今已 90 歲的前輩，是一位以色列科學(xué)家，他開發(fā)了通用無(wú)損壓縮算法 Lempel-Ziv，為后來(lái)的 GIF、PNG 和 ZIP 文件的開發(fā)奠定了堅(jiān)實(shí)的基礎(chǔ)。

1、無(wú)損壓縮算法發(fā)展史

20 世紀(jì) 70 年代，隨著互聯(lián)網(wǎng)及 PC 時(shí)代的來(lái)臨，如何在有限內(nèi)存空間的設(shè)備上節(jié)省出更多的空間，并減少對(duì)帶寬的占用，讓文件在較低的網(wǎng)絡(luò)帶寬下實(shí)現(xiàn)更快的傳輸，成為彼時(shí) IT 行業(yè)亟需解決的一大難題。

正因此，數(shù)據(jù)壓縮技術(shù)也從背后逐漸走入大眾視野，并開始在計(jì)算機(jī)領(lǐng)域扮演重要角色。

現(xiàn)如今，想必很多人都知道，數(shù)據(jù)壓縮主要有兩種類型：一種是有損壓縮，一種是無(wú)損壓縮。

所謂有損壓縮，主要是利用了人類對(duì)圖像或聲波中的某些頻率成分不敏感的特性，允許壓縮過程中損失一定的信息，日常生活中，我們常見的語(yǔ)言、圖像、視頻壓縮其實(shí)都是有損壓縮的方式。

與有損壓縮相比，無(wú)損壓縮要更為復(fù)雜一些，對(duì)此，IEEE 官方使用了「魔術(shù)」一詞來(lái)形容這門技術(shù)，其中原因主要是因?yàn)闊o(wú)損壓縮技術(shù)是利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮，在解壓之后，可完全恢復(fù)原始數(shù)據(jù)而不引起任何失真。這就像一位魔術(shù)師拿著魔術(shù)棒一揮，手中的東西不見了，再一揮，又原封不動(dòng)地出現(xiàn)了，無(wú)損壓損技術(shù)就像表演魔術(shù)一樣。

而 Jacob Ziv 就是這位在數(shù)據(jù)壓縮領(lǐng)域拿著魔術(shù)棒的大師。

不過，在 Jacob Ziv 這位魔術(shù)師帶來(lái)奇特的魔術(shù)之前，壓縮算法也經(jīng)歷了百年的發(fā)展歷程（http://ethw.org/History_of_Lossless_Data_Compression_Algorithms）：

事實(shí)上，發(fā)明于 1838 年的 Morse code，是最早的數(shù)據(jù)壓縮實(shí)例。

隨著大型機(jī)的興起，數(shù)學(xué)家香農(nóng)和 Robert Fano（CSAIL的計(jì)算先驅(qū)和創(chuàng)始人）發(fā)明了 Shannon-Fano（香農(nóng)-范諾）編碼算法。他們的算法基于符號(hào)（symbol）出現(xiàn)的概率來(lái)給符號(hào)分配編碼（code）。一個(gè)符號(hào)出現(xiàn)的概率大小與對(duì)應(yīng)的編碼成反比，從而用更短的方式來(lái)表示符號(hào)。

1951 年，作為麻省理工的一名學(xué)生，David Huffman 選擇寫學(xué)期論文而非期末考試的方式來(lái)完成學(xué)業(yè)任務(wù)，彼時(shí)他的論文題目是尋找二叉編碼的最優(yōu)算法。不過，遺憾的是，經(jīng)過幾個(gè)月的努力后依然沒有任何成果，Huffman 決定放棄所有論文相關(guān)的工作，開始學(xué)習(xí)為參加期末考試做準(zhǔn)備。就在那時(shí)，Huffman 偶然間找到一個(gè)與 Shannon-Fano 編碼相類似但是更有效的編碼算法，這種編碼方式效率高、運(yùn)算速度快。

后來(lái)到了 20 世紀(jì) 70 年代，隨著在線存儲(chǔ)的出現(xiàn)，哈夫曼編碼得到了廣泛應(yīng)用。不過，經(jīng)過不斷地嘗試，不少科學(xué)家發(fā)現(xiàn)哈夫曼編碼所得的編碼長(zhǎng)度只是對(duì)信息熵（描述信源的不確定度）計(jì)算結(jié)果的一種近似，還無(wú)法真正逼近信息熵的極限。同時(shí)，它需要兩次通過數(shù)據(jù)文件：一次計(jì)算文件的統(tǒng)計(jì)特征，第二次編碼數(shù)據(jù)。將字典與編碼數(shù)據(jù)一起存儲(chǔ)，增加了壓縮文件的大小。

1977 年，來(lái)自以色列的 Jacob Ziv 和 Abraham Lempel 兩位技術(shù)大神打破傳統(tǒng)的設(shè)計(jì)思想，創(chuàng)造出一種哈夫曼編碼更有效的壓縮算法，并以兩個(gè)人名字來(lái)命名。同時(shí)，他們還發(fā)表了一篇名為《A Universal Algorithm for Sequential Data Compression》（順序數(shù)據(jù)壓縮的一個(gè)通用算法 ，https://www2.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1977_universal_algorithm.pdf）的論文，揭曉了獨(dú)創(chuàng)的 LZ77 算法，這也是第一個(gè)使用字典來(lái)壓縮數(shù)據(jù)的算法。

次年，Jacob Ziv 和 Abraham Lempel 再次發(fā)表一篇改進(jìn)版的論文（《Compression of Individual Sequences via Variable Rate Coding》），并帶來(lái)了 LZ78 的壓縮算法。與 LZ77 不同，LZ78 解析輸入數(shù)據(jù)，生成一個(gè)靜態(tài)字典，不像 LZ77 動(dòng)態(tài)產(chǎn)生。該算法成為 80 年代初使用的 Unix 壓縮程序的基礎(chǔ)；影響了 90 年代的 WinZip 和 Gzip，為 GIF、TIFF 圖片格式的開發(fā)帶來(lái)了一定的指引。

如果沒有這些算法的存在，現(xiàn)在的我們不一定能夠使用更為便捷的網(wǎng)絡(luò)就可以發(fā)送大型數(shù)據(jù)文件，或還停留在將大型數(shù)據(jù)文件拷貝到光盤上進(jìn)行傳輸時(shí)代；聽音樂時(shí)，還有可能需要 CD 而不是通過流式傳輸。..。..

2、 Ziv 的過往經(jīng)歷

這一切都需要感謝 Jacob Ziv 和 Abraham Lempel。

“LZ 算法是第一個(gè)成功的通用壓縮算法”，一位支持 Ziv 獲獎(jiǎng)的工程師如是說(shuō)。這些算法以及 Jacob Ziv 對(duì)它們的分析，為后續(xù)關(guān)于通用算法的大多數(shù)工作奠定了基礎(chǔ)。

回顧 Ziv 的過往經(jīng)歷，其跨越了半個(gè)世紀(jì)，將自己全身心地投入到壓縮算法領(lǐng)域中。

1931 年，出生在當(dāng)時(shí)由英國(guó)統(tǒng)治的巴勒斯坦城市 Tiberias（現(xiàn)屬于以色列）的 Ziv，在很小的時(shí)候，Ziv 就對(duì)電力和電子產(chǎn)品有著濃厚的興趣，譬如，在練習(xí)小提琴的時(shí)候，他會(huì)嘗試把樂譜架變成一盞燈。此外，他還試圖用鋼琴?gòu)椬嗟慕饘倭慵谱饕粋€(gè)馬可尼發(fā)射機(jī)。

1948 年，第一次阿以戰(zhàn)爭(zhēng)爆發(fā)時(shí)他在讀高中，后來(lái)被征召到前線短暫地服過役。由于一群母親組織抗議，他才從前線回到了后方，在空軍受訓(xùn)擔(dān)任雷達(dá)技師。戰(zhàn)爭(zhēng)結(jié)束后，他進(jìn)入以色列理工學(xué)院學(xué)習(xí)電氣工程。

在 1955 年完成碩士學(xué)位后，Ziv 重返國(guó)防界，并加入了以色列國(guó)防研究實(shí)驗(yàn)室（現(xiàn)為拉斐爾先進(jìn)防御系統(tǒng)），開發(fā)用于導(dǎo)彈和其他軍事系統(tǒng)的電子元件。

1959 年，Ziv 被選為以色列國(guó)防實(shí)驗(yàn)室為數(shù)不多的出國(guó)留學(xué)的研究人員之一。那時(shí)，Ziv 計(jì)劃繼續(xù)從事通信工作，但他不再只對(duì)硬件感興趣。偶然機(jī)遇之下，他閱讀了《信息理論》（Prentice-Hall，1953年）的書籍，他決定將信息理論作為他關(guān)注的焦點(diǎn)。然而，除了麻省理工學(xué)院之外，還有什么地方可以研究信息理論呢？

當(dāng)然還是麻省理工！于是，1960 年，Ziv 進(jìn)入 MIT 讀博，在信息理論方面深造，在畢業(yè)返回以色列后進(jìn)入了國(guó)防部擔(dān)任通信部門主管。

1968 年，他返回美國(guó)，進(jìn)入了貝爾實(shí)驗(yàn)室。

兩年后，Ziv 和幾個(gè)同事一起加入了以色列理工學(xué)院。就是在這里，他遇到了 Abraham Lempel，兩個(gè)人共同討論了如何改進(jìn)無(wú)損數(shù)據(jù)壓縮。

Ziv 和 Lempel 都想知道他們是否可以開發(fā)一種無(wú)損數(shù)據(jù)壓縮算法，該算法適用于任何類型的數(shù)據(jù)，不需要預(yù)處理，并且能夠?qū)崿F(xiàn)數(shù)據(jù)的最佳壓縮，這個(gè)目標(biāo)被稱為 Shannon 熵的對(duì)象定義。在設(shè)想時(shí)，他們并不清楚是否可以實(shí)現(xiàn)他們的目標(biāo)。于是，他們決定找出答案。

在深入研究幾年后，隨著 LZ77 和 LZ78 的出現(xiàn)，代表了其研究成功。Ziv 和 Lempel 開創(chuàng)了通用源編碼，一系列無(wú)需知道固有信息壓縮數(shù)據(jù)的算法，減少了從不失真和失真數(shù)據(jù)重建圖像所需的數(shù)據(jù)率。

對(duì)此，斯坦福大學(xué)從事信息理論的電氣工程教授 Tsachy Weissman 表示：“在他們發(fā)表作品時(shí)，算法清晰優(yōu)雅，易于實(shí)現(xiàn)，計(jì)算復(fù)雜度低，這一事實(shí)幾乎無(wú)關(guān)緊要。更多的是關(guān)于理論結(jié)果，為接下來(lái)的研究帶來(lái)重要意義?！?/p>

另外，Ziv 還促成了錯(cuò)誤校正代碼的低計(jì)算復(fù)雜性解碼理論。并于：

1993 年，因精確科學(xué)而被授予以色列獎(jiǎng)（Israel Prize）；

1995 年，因其“對(duì)信息理論、數(shù)據(jù)壓縮的理論和實(shí)踐的貢獻(xiàn)”獲得 IEEE 理查德 · 漢明獎(jiǎng)?wù)拢?/p>

1997 年，獲得 IEEE 信息論學(xué)會(huì)的克勞德 · 香農(nóng)獎(jiǎng)；

2008 年，獲得 BBVA 基金會(huì)知識(shí)前沿獎(jiǎng)。

如今，憑借「其對(duì)信息理論和數(shù)據(jù)壓縮技術(shù)的重要貢獻(xiàn)和杰出的研究領(lǐng)導(dǎo)地位」，被授予 2021 年度 IEEE 榮譽(yù)勛章，可謂實(shí)至名歸，向依舊奮戰(zhàn)在研究一線的前輩致敬！

原文標(biāo)題：90 歲程序員：他的壓縮算法改變了世界！

文章出處：【微信公眾號(hào)：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。

責(zé)任編輯：haq