近日,國際電氣與電子工程學會(Institute of Electrical and Electronics Engineers,簡稱IEEE)宣布,授予IEEE終身 Fellow Jacob Ziv 2021 年度IEEE榮譽勛章。
這位如今已 90 歲的前輩,是一位以色列科學家,他開發(fā)了通用無損壓縮算法 Lempel-Ziv,為后來的 GIF、PNG 和 ZIP 文件的開發(fā)奠定了堅實的基礎。
無損壓縮算法發(fā)展史
20 世紀 70 年代,隨著互聯(lián)網(wǎng)及 PC 時代的來臨,如何在有限內(nèi)存空間的設備上節(jié)省出更多的空間,并減少對帶寬的占用,讓文件在較低的網(wǎng)絡帶寬下實現(xiàn)更快的傳輸,成為彼時 IT 行業(yè)亟需解決的一大難題。
正因此,數(shù)據(jù)壓縮技術也從背后逐漸走入大眾視野,并開始在計算機領域扮演重要角色。
現(xiàn)如今,想必很多人都知道,數(shù)據(jù)壓縮主要有兩種類型:一種是有損壓縮,一種是無損壓縮。
所謂有損壓縮,主要是利用了人類對圖像或聲波中的某些頻率成分不敏感的特性,允許壓縮過程中損失一定的信息,日常生活中,我們常見的語言、圖像、視頻壓縮其實都是有損壓縮的方式。
與有損壓縮相比,無損壓縮要更為復雜一些,對此,IEEE 官方使用了「魔術」一詞來形容這門技術,其中原因主要是因為無損壓縮技術是利用數(shù)據(jù)的統(tǒng)計冗余進行壓縮,在解壓之后,可完全恢復原始數(shù)據(jù)而不引起任何失真。這就像一位魔術師拿著魔術棒一揮,手中的東西不見了,再一揮,又原封不動地出現(xiàn)了,無損壓損技術就像表演魔術一樣。
而 Jacob Ziv 就是這位在數(shù)據(jù)壓縮領域拿著魔術棒的大師。
不過,在 Jacob Ziv 這位魔術師帶來奇特的魔術之前,壓縮算法也經(jīng)歷了百年的發(fā)展歷程:
事實上,發(fā)明于 1838 年的 Morse code,是最早的數(shù)據(jù)壓縮實例。
隨著大型機的興起,數(shù)學家香農(nóng)和 Robert Fano(CSAIL 的計算先驅(qū)和創(chuàng)始人)發(fā)明了 Shannon-Fano(香農(nóng) - 范諾)編碼算法。他們的算法基于符號 ( symbol ) 出現(xiàn)的概率來給符號分配編碼 ( code ) 。一個符號出現(xiàn)的概率大小與對應的編碼成反比,從而用更短的方式來表示符號。
1951 年,作為麻省理工的一名學生,David Huffman 選擇寫學期論文而非期末考試的方式來完成學業(yè)任務,彼時他的論文題目是尋找二叉編碼的最you算法。不過,遺憾的是,經(jīng)過幾個月的努力后依然沒有任何成果,Huffman 決定放棄所有論文相關的工作,開始學習為參加期末考試做準備。就在那時,Huffman 偶然間找到一個與 Shannon-Fano 編碼相類似但是更有效的編碼算法,這種編碼方式效率高、運算速度快。
后來到了 20 世紀 70 年代,隨著在線存儲的出現(xiàn),哈夫曼編碼得到了廣泛應用。不過,經(jīng)過不斷地嘗試,不少科學家發(fā)現(xiàn)哈夫曼編碼所得的編碼長度只是對信息熵(描述信源的不確定度)計算結(jié)果的一種近似,還無法真正逼近信息熵的極限。同時,它需要兩次通過數(shù)據(jù)文件:一次計算文件的統(tǒng)計特征,第二次編碼數(shù)據(jù)。將字典與編碼數(shù)據(jù)一起存儲,增加了壓縮文件的大小。
1977 年,來自以色列的 Jacob Ziv 和 Abraham Lempel 兩位技術大神打破傳統(tǒng)的設計思想,創(chuàng)造出一種哈夫曼編碼更有效的壓縮算法,并以兩個人名字來命名。同時,他們還發(fā)表了一篇名為《A Universal Algorithm for Sequential Data Compression》(順序數(shù)據(jù)壓縮的一個通用算法)的論文,揭曉了獨創(chuàng)的 LZ77 算法,這也是第1個使用字典來壓縮數(shù)據(jù)的算法。
次年,Jacob Ziv 和 Abraham Lempel 再次發(fā)表一篇改進版的論文(《Compression of Individual Sequences via Variable Rate Coding》),并帶來了 LZ78 的壓縮算法。與 LZ77 不同,LZ78 解析輸入數(shù)據(jù),生成一個靜態(tài)字典,不像 LZ77 動態(tài)產(chǎn)生。該算法成為 80 年代初使用的 Unix 壓縮程序的基礎;影響了 90 年代的 WinZip 和 Gzip,為 GIF、TIFF 圖片格式的開發(fā)帶來了一定的指引。
如果沒有這些算法的存在,現(xiàn)在的我們不一定能夠使用更為便捷的網(wǎng)絡就可以發(fā)送大型數(shù)據(jù)文件,或還停留在將大型數(shù)據(jù)文件拷貝到光盤上進行傳輸時代;聽音樂時,還有可能需要 CD 而不是通過流式傳輸 ......
Ziv 的過往經(jīng)歷
這一切都需要感謝 Jacob Ziv 和 Abraham Lempel。
"LZ 算法是第1個成功的通用壓縮算法 ",一位支持 Ziv 獲獎的工程師如是說。這些算法以及 Jacob Ziv 對它們的分析,為后續(xù)關于通用算法的大多數(shù)工作奠定了基礎。
回顧 Ziv 的過往經(jīng)歷,其跨越了半個世紀,將自己全身心地投入到壓縮算法領域中。
1931 年,出生在當時由英國統(tǒng)治的巴勒斯坦城市 Tiberias(現(xiàn)屬于以色列)的 Ziv,在很小的時候,Ziv 就對電力和電子產(chǎn)品有著濃厚的興趣,譬如,在練習小提琴的時候,他會嘗試把樂譜架變成一盞燈。此外,他還試圖用鋼琴彈奏的金屬零件制作一個馬可尼發(fā)射機。
1948 年,第1次阿以戰(zhàn)爭爆發(fā)時他在讀高中,后來被征召到前線短暫地服過役。由于一群母親組織抗議,他才從前線回到了后方,在空軍受訓擔任雷達技師。戰(zhàn)爭結(jié)束后,他進入以色列理工學院學習電氣工程。
在 1955 年完成碩士學位后,Ziv 重返國防界,并加入了以色列國防研究實驗室(現(xiàn)為拉斐爾先進防御系統(tǒng)),開發(fā)用于導彈和其他軍事系統(tǒng)的電子元件。
1959 年,Ziv 被選為以色列國防實驗室為數(shù)不多的出國留學的研究人員之一。那時,Ziv 計劃繼續(xù)從事通信工作,但他不再只對硬件感興趣。偶然機遇之下,他閱讀了《信息理論》(Prentice-Hall,1953 年)的書籍,他決定將信息理論作為他關注的焦點。然而,除了麻省理工學院之外,還有什么地方可以研究信息理論呢?
當然還是麻省理工!于是,1960 年,Ziv 進入 MIT 讀博,在信息理論方面深造,在畢業(yè)返回以色列后進入了國防部擔任通信部門主管。
1968 年,他返回美國,進入了貝爾實驗室。
兩年后,Ziv 和幾個同事一起加入了以色列理工學院。就是在這里,他遇到了 Abraham Lempel,兩個人共同討論了如何改進無損數(shù)據(jù)壓縮。
Ziv 和 Lempel 都想知道他們是否可以開發(fā)一種無損數(shù)據(jù)壓縮算法,該算法適用于任何類型的數(shù)據(jù),不需要預處理,并且能夠?qū)崿F(xiàn)數(shù)據(jù)的最加壓縮,這個目標被稱為 Shannon 熵的對象定義。在設想時,他們并不清楚是否可以實現(xiàn)他們的目標。于是,他們決定找出答案。
在深入研究幾年后,隨著 LZ77 和 LZ78 的出現(xiàn),代表了其研究成功。Ziv 和 Lempel 開創(chuàng)了通用源編碼,一系列無需知道固有信息壓縮數(shù)據(jù)的算法,減少了從不失真和失真數(shù)據(jù)重建圖像所需的數(shù)據(jù)率。
對此,斯坦福大學從事信息理論的電氣工程教授 Tsachy Weissman 表示:" 在他們發(fā)表作品時,算法清晰優(yōu)雅,易于實現(xiàn),計算復雜度低,這一事實幾乎無關緊要。更多的是關于理論結(jié)果,為接下來的研究帶來重要意義。"
另外,Ziv 還促成了錯誤校正代碼的低計算復雜性解碼理論。并于:
1993 年,因精確科學而被授予以色列獎(Israel Prize);
1995 年,因其 " 對信息理論、數(shù)據(jù)壓縮的理論和實踐的貢獻 " 獲得 IEEE 理查德 · 漢明獎章;
1997 年,獲得 IEEE 信息論學會的克勞德 · 香農(nóng)獎;
2008 年,獲得 BBVA 基金會知識前沿獎。
如今,憑借「其對信息理論和數(shù)據(jù)壓縮技術的重要貢獻和杰出的研究領導地位」,被授予 2021 年度 IEEE 榮譽勛章,可謂實至名歸,向依舊奮戰(zhàn)在研究一線的前輩致敬!