90 歲程序員：他的壓縮算法改變了世界！
導(dǎo)讀：近日，國際電氣與電子工程學(xué)會（Institute of Electrical and Electronics Engineers，簡稱 IEEE）宣布，授予 IEEE 終身 Fellow Jacob Ziv 2021 年度 IEEE 榮譽勛章。
事實上，發(fā)明于 1838 年的 Morse code，是最早的數(shù)據(jù)壓縮實例。 隨著大型機的興起，數(shù)學(xué)家香農(nóng)和 Robert Fano（CSAIL的計算先驅(qū)和創(chuàng)始人）發(fā)明了 Shannon-Fano（香農(nóng)-范諾）編碼算法。他們的算法基于符號(symbol)出現(xiàn)的概率來給符號分配編碼(code)。一個符號出現(xiàn)的概率大小與對應(yīng)的編碼成反比，從而用更短的方式來表示符號。 1951 年，作為麻省理工的一名學(xué)生，David Huffman 選擇寫學(xué)期論文而非期末考試的方式來完成學(xué)業(yè)任務(wù)，彼時他的論文題目是尋找二叉編碼的最優(yōu)算法。不過，遺憾的是，經(jīng)過幾個月的努力后依然沒有任何成果，Huffman 決定放棄所有論文相關(guān)的工作，開始學(xué)習(xí)為參加期末考試做準備。就在那時，Huffman 偶然間找到一個與 Shannon-Fano 編碼相類似但是更有效的編碼算法，這種編碼方式效率高、運算速度快。 后來到了 20 世紀 70 年代，隨著在線存儲的出現(xiàn)，哈夫曼編碼得到了廣泛應(yīng)用。不過，經(jīng)過不斷地嘗試，不少科學(xué)家發(fā)現(xiàn)哈夫曼編碼所得的編碼長度只是對信息熵（描述信源的不確定度）計算結(jié)果的一種近似，還無法真正逼近信息熵的極限。同時，它需要兩次通過數(shù)據(jù)文件：一次計算文件的統(tǒng)計特征，第二次編碼數(shù)據(jù)。將字典與編碼數(shù)據(jù)一起存儲，增加了壓縮文件的大小。
在他們發(fā)表作品時，算法清晰優(yōu)雅，易于實現(xiàn)，計算復(fù)雜度低，這一事實幾乎無關(guān)緊要。更多的是關(guān)于理論結(jié)果，為接下來的研究帶來重要意義。
1993 年，因精確科學(xué)而被授予以色列獎（Israel Prize）； 1995 年，因其“對信息理論、數(shù)據(jù)壓縮的理論和實踐的貢獻”獲得 IEEE 理查德 · 漢明獎?wù)拢?/span> 1997 年，獲得 IEEE 信息論學(xué)會的克勞德 · 香農(nóng)獎； 2008 年，獲得 BBVA 基金會知識前沿獎。
評論
圖片
表情