90 歲程式設計師獲IEEE 終身榮譽勳章!他的無損壓縮演算法改變了這個世界!

90 歲程式設計師獲IEEE 終身榮譽勳章!他的無損壓縮演算法改變了這個世界!

ADVERTISEMENT

 

近日,國際電機電子工程師學會(Institute of Electrical and Electronics Engineers,簡稱IEEE)宣布,授予傑可布·立夫(Fellow Jacob Ziv) 2021 年度IEEE 終身榮譽勳章。

Jacob Ziv

 

這位如今已90 歲的前輩,是一位以色列科學家,他開發了通用無損壓縮演算法Lempel-Ziv,為後來的GIF、PNG 和ZIP 檔案的開發奠定了堅實的基礎。

無損壓縮演算法發展史

20 世紀70 年代,隨著網際網路及PC 時代的來臨,如何在有限記憶體空間的設備上節省出更多的空間,並減少對頻寬的佔用,讓檔案在較低的網路頻寬下實現更快的傳輸,成為彼時IT 行業亟需解決的一大難題。

正因此,資料壓縮技術也從背後逐漸走入大眾視野,並開始在電腦領域扮演重要角色。

如今很多人都知道資料壓縮主要有兩種類型:一種是有損壓縮,一種是無損壓縮。

所謂有損壓縮,主要是利用了人類對圖像或音波中的某些頻率不敏感的特性,允許壓縮過程中損失一定的訊息,日常生活中,我們常見的語言、圖像、影片壓縮其實都是有損壓縮的方式。

與有損壓縮相比,無損壓縮要更為複雜一些,對此,IEEE 官方使用了「魔術」一詞來形容這門技術,其中原因主要是因為無損壓縮技術是利用資料的統計冗餘進行壓縮,在解壓之後,可完全恢復原始資料而不引起任何失真。這就像一位魔術師拿著魔術棒一揮,手中的東西不見了,再一揮,又原封不動地出現了,無損壓損技術就像表演魔術一樣。

而傑可布·立夫就是這位在資料壓縮領域拿著魔術棒的大師。

不過,在傑可布·立夫這位魔術師帶來奇特的魔術之前,壓縮演算法也經歷了百年的發展歷程:

事實上,發明於1838 年的摩斯電碼(Morse code),是最早的資料壓縮實例。隨著大型電腦的興起,數學家向農和羅伯特·法諾(Robert Fano:CSAIL的計算先驅和創始人)發明了Shannon-Fano(向農-法諾)編碼演算法。他們的演算法基於符號(symbol)出現的機率來給符號分配編碼(code)。一個符號出現的機率大小與對應的編碼成反比,進而用更短的方式來表示符號。1951 年,作為麻省理工的一名學生,大衛·霍夫曼(David Huffman)選擇寫學期論文而非期末考試的方式來完成學業任務,彼時他的論文題目是尋找二元樹編碼的最優演算法。不過,遺憾的是,經過幾個月的努力後依然沒有任何成果,霍夫曼決定放棄所有論文相關的工作,開始學習為參加期末考試做準備。

就在那時,霍夫曼偶然間找到一個與Shannon-Fano 編碼相類似但是更有效的編碼演算法,這種編碼方式效率高、運算速度快。後來到了20 世紀70 年代,隨著線上儲存的出現,哈夫曼編碼得到了廣泛應用。不過,經過不斷地嘗試,不少科學家發現哈夫曼編碼所得的編碼長度只是對訊息熵(描述訊源的不確定度)計算結果的一種近似,還無法真正逼近訊息熵的極限。同時,它需要兩次透過資料檔案:一次計算檔案的統計特徵,第二次編碼資料。將字典與編碼資料一起儲存,增加了壓縮檔案的大小。

1977 年,來自以色列的傑可布·立夫和亞伯拉罕·藍波(Abraham Lempel)兩位技術大師打破傳統的設計思想,創造出一種比哈夫曼編碼更有效的壓縮演算法,並以兩個人名字來命名。同時,他們還發表了一篇名為《A Universal Algorithm for Sequential Data Compression》(順序資料壓縮的一個通用演算法)的論文,揭曉了獨創的LZ77 演算法,這也是第一個使用字典來壓縮資料的演算法。

90 歲程式設計師獲IEEE 終身榮譽勳章!他的無損壓縮演算法改變了這個世界!

次年,傑可布·立夫和亞伯拉罕·藍波再次發表一篇改進版的論文(《Compression of Individual Sequences via Variable Rate Coding》),並帶來了LZ78 的壓縮演算法。與LZ77 不同,LZ78 解析輸入資料,產生一個靜態字典,不像LZ77 動態產生。該演算法成為80 年代初使用的Unix 壓縮程式的基礎;影響了90 年代的WinZip 和Gzip,為GIF、TIFF 圖片格式的開發帶來了一定的指引。

如果沒有這些演算法的存在,現在的我們不一定能夠使用更為便捷的網路就可以發送大型資料檔案,或還停留在將大型資料檔案拷貝到光碟上進行傳輸時代;聽音樂時,還有可能需要CD 而不是透過串流方式來傳輸......

立夫的過往經歷

這一切都需要感謝傑可布·立夫和亞伯拉罕·藍波。

「LZ 演算法是第一個成功的通用壓縮演算法」,一位支持立夫獲獎的工程師如是說。這些演算法以及傑可布·立夫對它們的分析,為後續關於通用演算法的大多數工作奠定了基礎。

回顧立夫的過往經歷,其跨越了半個世紀,將自己全身心地投入到壓縮演算法領域中。

1931 年,出生在當時由英國統治的巴勒斯坦城市提比里亞(Tiberias,現屬於以色列)的立夫,在很小的時候,立夫就對電力和電子產品有著濃厚的興趣,譬如,在練習小提琴的時候,他會嘗試把樂譜架變成一盞燈。此外,他還試圖用鋼琴彈奏的金屬零件製作一個馬可尼發射機。

1948 年,第一次以阿戰爭爆發時他在讀高中,後來被徵召到前線短暫地服過役。由於一群母親組織抗議,他才從前線回到了後方,在空軍受訓擔任雷達技師。戰爭結束後,他進入以色列理工學院學習電氣工程。

在1955 年完成碩士學位後,立夫重返國防界,並加入了以色列國防研究實驗室(現為拉斐爾先進防禦系統公司),開發用於導彈和其他軍事系統的電子元件。

1959 年,立夫被選為以色列國防實驗室為數不多的出國留學的研究人員之一。那時,立夫計劃繼續從事通訊工作,但他不再只對硬體感興趣。偶然機遇之下,他閱讀了《訊息理論》(Prentice-Hall,1953年)的書籍,他決定將訊息理論作為他關注的焦點。然而,除了麻省理工學院之外,還有什麼地方可以研究訊息理論呢?

當然還是麻省理工!於是,1960 年,立夫進入MIT 讀博,在訊息理論方面深造,在畢業返回以色列後進入了國防部擔任通訊部門主管。

1968 年,他返回美國,進入了貝爾實驗室。

兩年後,立夫和幾個同事一起加入了以色列理工學院。就是在這裡,他遇到了亞伯拉罕·藍波,兩個人共同討論瞭如何改進無損資料壓縮。

立夫和藍波都想知道他們是否可以開發一種無損資料壓縮演算法,該演算法適用於任何類型的資料,不需要預處理,並且能夠實現資料的最佳壓縮,這個目標被稱為Shannon 熵的對象定義。在設想時,他們並不清楚是否可以實現他們的目標。於是,他們決定找出答案。

在深入研究幾年後,隨著LZ77 和LZ78 的出現,代表了其研究成功。立夫和藍波開創了通用原始碼,一系列無需知道固有訊息壓縮資料的演算法,減少了從不失真和失真資料重建圖像所需的資料率。

對此,史丹佛大學從事訊息理論的電氣工程教授茲切·威斯曼(Tsachy Weissman)表示:「在他們發表作品時,演算法清晰優雅,易於實現,運算複雜度低,這一事實幾乎無關緊要。更多的是關於理論結果,為接下來的研究帶來重要意義。」

另外,立夫還促成了錯誤校正程式碼的低運算複雜性解碼理論。並於:

1993 年,因精確科學而被授予以色列獎(Israel Prize);1995 年,因其「對訊息理論、資料壓縮的理論和實踐的貢獻」獲得IEEE 理查德 · 漢明獎章;1997 年,獲得IEEE 訊息論學會的克勞德 · 向農獎;2008 年,獲得BBVA 基金會知識尖端獎。

如今,憑藉「其對訊息理論和資料壓縮技術的重要貢獻和傑出的研究領導地位」,被授予2021 年度IEEE 榮譽勳章,可謂實至名歸,向依舊奮戰在研究一線的前輩致敬!

bigdatadigest
作者

大數據文摘(bigdatadigest)成立於2013年7月,專注數據領域資訊、案例、技術,在多家具有影響力的網站、雜誌設有專欄,致力於打造精準數據分析社群。

使用 Facebook 留言

發表回應

謹慎發言,尊重彼此。按此展開留言規則