90?歲了，他用算法改變了世界！
時間：2021-10-11 13:57:16
手機(jī)看文章
掃描二維碼
隨時隨地手機(jī)看文章
[導(dǎo)讀]推薦關(guān)注下方公眾號學(xué)習(xí)更多嵌入式知識！近日，國際電氣與電子工程學(xué)會（InstituteofElectricalandElectronicsEngineers，簡稱IEEE）宣布，授予IEEE終身FellowJacobZiv2021度IEEE榮譽勛章。這位如今已90歲的前輩，是一位...
推薦關(guān)注下方公眾號學(xué)習(xí)更多嵌入式知識！近日，國際電氣與電子工程學(xué)會（Institute of Electrical and Electronics Engineers，簡稱IEEE）宣布，授予IEEE終身Fellow Jacob Ziv 2021度IEEE榮譽勛章。
20世紀(jì)70年代，隨著互聯(lián)網(wǎng)及PC時代的來臨，如何在有限內(nèi)存空間的設(shè)備上節(jié)省出更多的空間，并減少對帶寬的占用，讓文件在較低的網(wǎng)絡(luò)帶寬下實現(xiàn)更快的傳輸，成為彼時IT行業(yè)亟需解決的一大難題。
正因此，數(shù)據(jù)壓縮技術(shù)也從背后逐漸走入大眾視野，并開始在計算機(jī)領(lǐng)域扮演重要角色。現(xiàn)如今，想必很多人都知道，數(shù)據(jù)壓縮主要有兩種類型：一種是有損壓縮，一種是無損壓縮。所謂有損壓縮，主要是利用了人類對圖像或聲波中的某些頻率成分不敏感的特性，允許壓縮過程中損失一定的信息，日常生活中，我們常見的語言、圖像、視頻壓縮其實都是有損壓縮的方式。與有損壓縮相比，無損壓縮要更為復(fù)雜一些，對此，IEEE 官方使用了「魔術(shù)」一詞來形容這門技術(shù)，其中原因主要是因為無損壓縮技術(shù)是利用數(shù)據(jù)的統(tǒng)計冗余進(jìn)行壓縮，在解壓之后，可完全恢復(fù)原始數(shù)據(jù)而不引起任何失真。這就像一位魔術(shù)師拿著魔術(shù)棒一揮，手中的東西不見了，再一揮，又原封不動地出現(xiàn)了，無損壓損技術(shù)就像表演魔術(shù)一樣。而Jacob Ziv就是這位在數(shù)據(jù)壓縮領(lǐng)域拿著魔術(shù)棒的大師。不過，在Jacob Ziv這位魔術(shù)師帶來奇特的魔術(shù)之前，壓縮算法也經(jīng)歷了百年的發(fā)展歷程http://ethw.org/History_of_Lossless_Data_Compression_Algorithms
這一切都需要感謝Jacob Ziv和Abraham Lempel。
"LZ算法是第一個成功的通用壓縮算法"，一位支持Ziv獲獎的工程師如是說。這些算法以及Jacob Ziv對它們的分析，為后續(xù)關(guān)于通用算法的大多數(shù)工作奠定了基礎(chǔ)。回顧Ziv的過往經(jīng)歷，其跨越了半個世紀(jì)，將自己全身心地投入到壓縮算法領(lǐng)域中。1931年，出生在當(dāng)時由英國統(tǒng)治的巴勒斯坦城市Tiberias（現(xiàn)屬于以色列）的Ziv，在很小的時候，Ziv就對電力和電子產(chǎn)品有著濃厚的興趣，譬如，在練習(xí)小提琴的時候，他會嘗試把樂譜架變成一盞燈。此外，他還試圖用鋼琴彈奏的金屬零件制作一個馬可尼發(fā)射機(jī)。1948年，第一次阿以戰(zhàn)爭爆發(fā)時他在讀高中，后來被征召到前線短暫地服過役。由于一群母親組織抗議，他才從前線回到了后方，在空軍受訓(xùn)擔(dān)任雷達(dá)技師。戰(zhàn)爭結(jié)束后，他進(jìn)入以色列理工學(xué)院學(xué)習(xí)電氣工程。在1955年完成碩士學(xué)位后，Ziv重返國防界，并加入了以色列國防研究實驗室（現(xiàn)為拉斐爾先進(jìn)防御系統(tǒng)），開發(fā)用于導(dǎo)彈和其他軍事系統(tǒng)的電子元件。1959年，Ziv被選為以色列國防實驗室為數(shù)不多的出國留學(xué)的研究人員之一。那時，Ziv計劃繼續(xù)從事通信工作，但他不再只對硬件感興趣。偶然機(jī)遇之下，他閱讀了《信息理論》（Prentice-Hall，1953年）的書籍，他決定將信息理論作為他關(guān)注的焦點。然而，除了麻省理工學(xué)院之外，還有什么地方可以研究信息理論呢？當(dāng)然還是麻省理工！于是，1960年，Ziv進(jìn)入MIT讀博，在信息理論方面深造，在畢業(yè)返回以色列后進(jìn)入了國防部擔(dān)任通信部門主管。1968年，他返回美國，進(jìn)入了貝爾實驗室。兩年后，Ziv和幾個同事一起加入了以色列理工學(xué)院。就是在這里，他遇到了Abraham Lempel，兩個人共同討論了如何改進(jìn)無損數(shù)據(jù)壓縮。Ziv和Lempel都想知道他們是否可以開發(fā)一種無損數(shù)據(jù)壓縮算法，該算法適用于任何類型的數(shù)據(jù)，不需要預(yù)處理，并且能夠?qū)崿F(xiàn)數(shù)據(jù)的最佳壓縮，這個目標(biāo)被稱為Shannon熵的對象定義。在設(shè)想時，他們并不清楚是否可以實現(xiàn)他們的目標(biāo)。于是，他們決定找出答案。在深入研究幾年后，隨著LZ77和LZ78的出現(xiàn)，代表了其研究成功。Ziv和Lempel開創(chuàng)了通用源編碼，一系列無需知道固有信息壓縮數(shù)據(jù)的算法，減少了從不失真和失真數(shù)據(jù)重建圖像所需的數(shù)據(jù)率。對此，斯坦福大學(xué)從事信息理論的電氣工程教授Tsachy Weissman表示："在他們發(fā)表作品時，算法清晰優(yōu)雅，易于實現(xiàn)，計算復(fù)雜度低，這一事實幾乎無關(guān)緊要。更多的是關(guān)于理論結(jié)果，為接下來的研究帶來重要意義。"另外，Ziv還促成了錯誤校正代碼的低計算復(fù)雜性解碼理論。并于：
20世紀(jì)70年代，隨著互聯(lián)網(wǎng)及PC時代的來臨，如何在有限內(nèi)存空間的設(shè)備上節(jié)省出更多的空間，并減少對帶寬的占用，讓文件在較低的網(wǎng)絡(luò)帶寬下實現(xiàn)更快的傳輸，成為彼時IT行業(yè)亟需解決的一大難題。
正因此，數(shù)據(jù)壓縮技術(shù)也從背后逐漸走入大眾視野，并開始在計算機(jī)領(lǐng)域扮演重要角色。現(xiàn)如今，想必很多人都知道，數(shù)據(jù)壓縮主要有兩種類型：一種是有損壓縮，一種是無損壓縮。所謂有損壓縮，主要是利用了人類對圖像或聲波中的某些頻率成分不敏感的特性，允許壓縮過程中損失一定的信息，日常生活中，我們常見的語言、圖像、視頻壓縮其實都是有損壓縮的方式。與有損壓縮相比，無損壓縮要更為復(fù)雜一些，對此，IEEE 官方使用了「魔術(shù)」一詞來形容這門技術(shù)，其中原因主要是因為無損壓縮技術(shù)是利用數(shù)據(jù)的統(tǒng)計冗余進(jìn)行壓縮，在解壓之后，可完全恢復(fù)原始數(shù)據(jù)而不引起任何失真。這就像一位魔術(shù)師拿著魔術(shù)棒一揮，手中的東西不見了，再一揮，又原封不動地出現(xiàn)了，無損壓損技術(shù)就像表演魔術(shù)一樣。而Jacob Ziv就是這位在數(shù)據(jù)壓縮領(lǐng)域拿著魔術(shù)棒的大師。不過，在Jacob Ziv這位魔術(shù)師帶來奇特的魔術(shù)之前，壓縮算法也經(jīng)歷了百年的發(fā)展歷程http://ethw.org/History_of_Lossless_Data_Compression_Algorithms- 事實上，發(fā)明于1838年的Morse code，是最早的數(shù)據(jù)壓縮實例。
- 隨著大型機(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í)為參加期末考試做準(zhǔn)備。就在那時，Huffman 偶然間找到一個與Shannon-Fano編碼相類似但是更有效的編碼算法，這種編碼方式效率高、運算速度快。
- 后來到了20世紀(jì)70年代，隨著在線存儲的出現(xiàn)，哈夫曼編碼得到了廣泛應(yīng)用。不過，經(jīng)過不斷地嘗試，不少科學(xué)家發(fā)現(xiàn)哈夫曼編碼所得的編碼長度只是對信息熵（描述信源的不確定度）計算結(jié)果的一種近似，還無法真正逼近信息熵的極限。同時，它需要兩次通過數(shù)據(jù)文件：一次計算文件的統(tǒng)計特征，第二次編碼數(shù)據(jù)。將字典與編碼數(shù)據(jù)一起存儲，增加了壓縮文件的大小。
這一切都需要感謝Jacob Ziv和Abraham Lempel。
"LZ算法是第一個成功的通用壓縮算法"，一位支持Ziv獲獎的工程師如是說。這些算法以及Jacob Ziv對它們的分析，為后續(xù)關(guān)于通用算法的大多數(shù)工作奠定了基礎(chǔ)。回顧Ziv的過往經(jīng)歷，其跨越了半個世紀(jì)，將自己全身心地投入到壓縮算法領(lǐng)域中。1931年，出生在當(dāng)時由英國統(tǒng)治的巴勒斯坦城市Tiberias（現(xiàn)屬于以色列）的Ziv，在很小的時候，Ziv就對電力和電子產(chǎn)品有著濃厚的興趣，譬如，在練習(xí)小提琴的時候，他會嘗試把樂譜架變成一盞燈。此外，他還試圖用鋼琴彈奏的金屬零件制作一個馬可尼發(fā)射機(jī)。1948年，第一次阿以戰(zhàn)爭爆發(fā)時他在讀高中，后來被征召到前線短暫地服過役。由于一群母親組織抗議，他才從前線回到了后方，在空軍受訓(xùn)擔(dān)任雷達(dá)技師。戰(zhàn)爭結(jié)束后，他進(jìn)入以色列理工學(xué)院學(xué)習(xí)電氣工程。在1955年完成碩士學(xué)位后，Ziv重返國防界，并加入了以色列國防研究實驗室（現(xiàn)為拉斐爾先進(jìn)防御系統(tǒng)），開發(fā)用于導(dǎo)彈和其他軍事系統(tǒng)的電子元件。1959年，Ziv被選為以色列國防實驗室為數(shù)不多的出國留學(xué)的研究人員之一。那時，Ziv計劃繼續(xù)從事通信工作，但他不再只對硬件感興趣。偶然機(jī)遇之下，他閱讀了《信息理論》（Prentice-Hall，1953年）的書籍，他決定將信息理論作為他關(guān)注的焦點。然而，除了麻省理工學(xué)院之外，還有什么地方可以研究信息理論呢？當(dāng)然還是麻省理工！于是，1960年，Ziv進(jìn)入MIT讀博，在信息理論方面深造，在畢業(yè)返回以色列后進(jìn)入了國防部擔(dān)任通信部門主管。1968年，他返回美國，進(jìn)入了貝爾實驗室。兩年后，Ziv和幾個同事一起加入了以色列理工學(xué)院。就是在這里，他遇到了Abraham Lempel，兩個人共同討論了如何改進(jìn)無損數(shù)據(jù)壓縮。Ziv和Lempel都想知道他們是否可以開發(fā)一種無損數(shù)據(jù)壓縮算法，該算法適用于任何類型的數(shù)據(jù)，不需要預(yù)處理，并且能夠?qū)崿F(xiàn)數(shù)據(jù)的最佳壓縮，這個目標(biāo)被稱為Shannon熵的對象定義。在設(shè)想時，他們并不清楚是否可以實現(xiàn)他們的目標(biāo)。于是，他們決定找出答案。在深入研究幾年后，隨著LZ77和LZ78的出現(xiàn)，代表了其研究成功。Ziv和Lempel開創(chuàng)了通用源編碼，一系列無需知道固有信息壓縮數(shù)據(jù)的算法，減少了從不失真和失真數(shù)據(jù)重建圖像所需的數(shù)據(jù)率。對此，斯坦福大學(xué)從事信息理論的電氣工程教授Tsachy Weissman表示："在他們發(fā)表作品時，算法清晰優(yōu)雅，易于實現(xiàn)，計算復(fù)雜度低，這一事實幾乎無關(guān)緊要。更多的是關(guān)于理論結(jié)果，為接下來的研究帶來重要意義。"另外，Ziv還促成了錯誤校正代碼的低計算復(fù)雜性解碼理論。并于：- 1993年，因精確科學(xué)而被授予以色列獎（Israel Prize）；
- 1995年，因其“對信息理論、數(shù)據(jù)壓縮的理論和實踐的貢獻(xiàn)”獲得 IEEE 理查德 · 漢明獎?wù)拢?/span>
- 1997年，獲得IEEE信息論學(xué)會的克勞德 · 香農(nóng)獎；
- 2008年，獲得BBVA基金會知識前沿獎。
下載文檔
