無(wú)損數(shù)據(jù)壓縮有點(diǎn)像魔術(shù)。

有損壓縮是與無(wú)損數(shù)據(jù)壓縮相近的一個(gè)詞，它更容易理解。有損算法用于將音樂(lè)轉(zhuǎn)換成流行的MP3格式和將數(shù)字圖像轉(zhuǎn)換成標(biāo)準(zhǔn)的JPEG文件。這種算法會(huì)有選擇地去除一些數(shù)據(jù)位來(lái)完成轉(zhuǎn)換，利用科學(xué)家們對(duì)視聽方式的了解來(lái)確定哪些數(shù)據(jù)位是我們最不會(huì)錯(cuò)過(guò)的，但沒(méi)有人能保證生成的文件可以完美復(fù)刻原始文件。

無(wú)損數(shù)據(jù)壓縮則不然。其中的數(shù)據(jù)位確實(shí)消失了，數(shù)據(jù)文件因此大大縮小，變得更易存儲(chǔ)和傳輸。它與有損壓縮的重要區(qū)別在于，這些數(shù)據(jù)位會(huì)根據(jù)命令重新出現(xiàn)。就像魔術(shù)表演中的兔子一樣，它們?cè)谀д鹊膿]動(dòng)下從帽子里消失，然后又重新出現(xiàn)。

魔術(shù)界有胡迪尼，他創(chuàng)造的魔術(shù)至今仍在表演，而數(shù)據(jù)壓縮界則有雅各布?齊夫。

1977年，齊夫與亞伯拉罕?倫佩爾合作，在《IEEE信息理論學(xué)報(bào)》上發(fā)表了一篇論文，題目是《順序數(shù)據(jù)壓縮通用算法》，該論文與《胡迪尼說(shuō)魔術(shù)》一樣具有重要地位。 按照作者姓名的字母順序和發(fā)表年份，論文所述算法被稱為L(zhǎng)Z77。 LZ77并不是第一種無(wú)損壓縮算法，但卻是第一種可以一步就發(fā)揮魔力的算法。

接下來(lái)的一年，這兩位研究人員發(fā)布了改進(jìn)版算法——LZ78。該算法成為了20世紀(jì)80年代使用的Unix壓縮程序的基礎(chǔ)，也是90年代初誕生的WinZip和Gzip的基礎(chǔ)，以及GIF和TIFF圖像格式的基礎(chǔ)。如果沒(méi)有這些算法，我們可能還在以光盤形式郵寄大型數(shù)據(jù)文件而不是通過(guò)互聯(lián)網(wǎng)點(diǎn)擊發(fā)送，可能還在購(gòu)買CD聽音樂(lè)而不是享受流式播放音樂(lè)，可能還在查看沒(méi)有跳動(dòng)動(dòng)畫圖像的臉譜網(wǎng)訂閱消息。

之后，齊夫繼續(xù)與其他研究人員合作進(jìn)行壓縮方面的其他創(chuàng)新。正是他橫跨半個(gè)多世紀(jì)的工作，讓他因“對(duì)信息理論和數(shù)據(jù)壓縮技術(shù)的重要貢獻(xiàn)和杰出的研究領(lǐng)導(dǎo)”獲得了2021年IEEE榮譽(yù)勛章。

1931年，齊夫出生在提比利亞的一個(gè)俄羅斯移民家庭。提比利亞當(dāng)時(shí)是英國(guó)統(tǒng)治下的一個(gè)巴勒斯坦城市，現(xiàn)在屬于以色列。孩童時(shí)期，齊夫就對(duì)電和小工具（以及其他小型裝置）很感興趣。比如，在練小提琴時(shí)，他設(shè)法把他的樂(lè)譜架變成了一盞燈。他還試圖用鋼琴的金屬零件來(lái)制造馬可尼發(fā)射機(jī)。不過(guò)把裝置接通電源后，整座房子都斷電了，于是那臺(tái)發(fā)射機(jī)未能發(fā)揮作用。

1948年阿以戰(zhàn)爭(zhēng)爆發(fā)時(shí)，齊夫還在上中學(xué)。他被征召加入以色列國(guó)防軍并在前線短暫服役，后來(lái)，一群母親舉行了有組織的抗議活動(dòng)，要求把最年輕的士兵送到別處。隨后，齊夫被調(diào)到以色列空軍，接受了雷達(dá)技術(shù)員的訓(xùn)練。戰(zhàn)爭(zhēng)結(jié)束后，他進(jìn)入了以色列理工學(xué)院學(xué)習(xí)電氣工程。

1955年完成碩士學(xué)位的學(xué)習(xí)后，齊夫重返國(guó)防界，加入了以色列國(guó)防研究實(shí)驗(yàn)室（現(xiàn)為拉斐爾先進(jìn)防御系統(tǒng)公司），開發(fā)用于導(dǎo)彈和其他軍事系統(tǒng)的電子元件。齊夫回憶道，小組里的工程師（包括他自己）對(duì)電子學(xué)都學(xué)只有基本的了解。他們的電氣工程教育更側(cè)重于電力系統(tǒng)。

“我們有6個(gè)人，我們必須得自學(xué)。 ”他說(shuō)，“我們會(huì)選一本書，然后一起學(xué)習(xí)，就像虔誠(chéng)的猶太人學(xué)習(xí)《希伯來(lái)圣經(jīng)》一樣，但這還不夠。 ”

該小組的目標(biāo)是建立一個(gè)使用晶體管而非真空管的遙測(cè)系統(tǒng)。他們不僅需要知識(shí)，還需要零件。齊夫聯(lián)系了貝爾電話實(shí)驗(yàn)室，請(qǐng)求對(duì)方免費(fèi)提供一份晶體管樣品；隨后該公司提供了100份樣品。

“這滿足了我們幾個(gè)月的需求?！彼f(shuō)，“我認(rèn)為自己是以色列第一批認(rèn)真研究晶體管的人?！?/p>

1959年，齊夫成為以色列國(guó)防實(shí)驗(yàn)室少數(shù)幾位被選派出國(guó)留學(xué)的研究人員之一。他說(shuō)，這個(gè)項(xiàng)目改變了以色列的科學(xué)發(fā)展。項(xiàng)目的組織者沒(méi)有將入選的年輕工程師和科學(xué)家引入特定領(lǐng)域。相反，他們?cè)试S入選者選擇任一西方國(guó)家攻讀任何類型的研究生課程。

齊夫計(jì)劃繼續(xù)從事通信工作，但他不再只對(duì)硬件感興趣了。他讀了斯坦福?戈德曼的《信息理論》（Information Theory，普倫蒂斯?霍爾出版社，1953年），這是與該主題有關(guān)的最早的書作之一，于是他決定把信息理論作為自己的研究重點(diǎn)。麻省理工學(xué)院是學(xué)習(xí)信息理論的不二選擇，這一領(lǐng)域的先驅(qū)克勞德?香農(nóng)就是從那里開始的。

1960年，齊夫抵達(dá)馬薩諸塞州的劍橋市。他的博士研究方向是要找到一種方法來(lái)對(duì)通過(guò)噪聲信道發(fā)送的消息進(jìn)行編碼和解碼，盡量降低概率和減少錯(cuò)誤，同時(shí)保持解碼的簡(jiǎn)單性。

“信息理論很美，”他說(shuō)，“它會(huì)告訴你你所能取得的最好結(jié)果，還會(huì)告訴你如何接近這個(gè)結(jié)果。因此，如果投入計(jì)算工作量，你就可以知道自己正在接近可能的最佳結(jié)果。”

齊夫?qū)⑦@種確定性與深度學(xué)習(xí)算法的不確定性進(jìn)行了對(duì)比。顯然，深度算法是有效的，但是沒(méi)有人真正知道它是否是最好的結(jié)果。

在麻省理工學(xué)院期間，齊夫還在美國(guó)國(guó)防承包商Melpar兼職，從事糾錯(cuò)軟件的研究工作。他發(fā)現(xiàn)這項(xiàng)工作并不美好。“當(dāng)時(shí)為了運(yùn)行一個(gè)計(jì)算機(jī)程序，我們必須使用穿孔卡，”他回憶道，“我討厭它們，因此我沒(méi)有進(jìn)入真正的計(jì)算機(jī)科學(xué)研究領(lǐng)域。”

在美國(guó)待了兩年后，齊夫回到了以色列國(guó)防研究實(shí)驗(yàn)室，負(fù)責(zé)通信部門。1970年，他和其他幾位同事加入了以色列理工學(xué)院。

在那里他遇到了亞伯拉罕?倫佩爾。兩人對(duì)改進(jìn)無(wú)損數(shù)據(jù)壓縮進(jìn)行了討論。

當(dāng)時(shí)最先進(jìn)的無(wú)損數(shù)據(jù)壓縮技術(shù)是哈夫曼編碼。 這種方法首先會(huì)在數(shù)據(jù)文件中查找數(shù)據(jù)位的序列，然后按它們出現(xiàn)的頻率進(jìn)行排序。 之后，編碼器會(huì)建立一個(gè)字典，其中用最小的數(shù)據(jù)位數(shù)字表示最常見的序列。 摩爾斯電碼也是同樣的原理： 英語(yǔ)中最常見的字母e用一個(gè)點(diǎn)表示，而不太常見的字母則用點(diǎn)和破折號(hào)等更復(fù)雜的組合來(lái)表示。

雖然目前MPEG-2壓縮格式和無(wú)損形式的JPEG中仍然使用哈夫曼編碼，但它有自身的缺點(diǎn)。它需要對(duì)一個(gè)數(shù)據(jù)文件瀏覽兩次：一次是計(jì)算文件的統(tǒng)計(jì)特征，另一次對(duì)數(shù)據(jù)進(jìn)行編碼。而且，將字典與編碼數(shù)據(jù)一起存儲(chǔ)會(huì)讓壓縮文件更大。

齊夫和倫佩爾希望能開發(fā)出一種可以處理任何類型數(shù)據(jù)的無(wú)損數(shù)據(jù)壓縮算法，它不需要預(yù)處理，并且可以實(shí)現(xiàn)對(duì)數(shù)據(jù)的最佳壓縮。這也是“香農(nóng)熵”定義的目標(biāo)。雖然不清楚目標(biāo)是否能實(shí)現(xiàn)，但他們決定試一試。

齊夫說(shuō)，他和倫佩爾是解決這個(gè)問(wèn)題的“完美搭檔”?！拔覍?duì)信息理論和統(tǒng)計(jì)學(xué)了如指掌，而亞伯拉罕精通布爾代數(shù)和計(jì)算機(jī)科學(xué)?！?/p>

他們提出了一個(gè)想法：讓算法在壓縮數(shù)據(jù)的同時(shí)尋找唯一的數(shù)據(jù)位序列，使用指針來(lái)指向之前看到的序列。這種方法只需要對(duì)文件進(jìn)行一次瀏覽，因此比哈夫曼編碼更快。

齊夫解釋說(shuō)：“我們查看輸入的數(shù)據(jù)位，找到過(guò)去匹配的最長(zhǎng)的數(shù)據(jù)位段。假設(shè)第一個(gè)輸入數(shù)據(jù)位是1?，F(xiàn)在，由于只有一個(gè)數(shù)據(jù)位，過(guò)去從未見過(guò)它，所以我們別無(wú)選擇，只能按原樣傳輸它?！?/p>

“然后，我們得到了另一個(gè)數(shù)據(jù)位，”他繼續(xù)說(shuō)，“假如也是1，那么我們會(huì)向字典輸入1-1。假設(shè)下一位是0，那么我們的字典里就有了1-1和1-0?！?/p>

此時(shí)指針開始發(fā)揮作用。下次，當(dāng)位流包含1-1或1-0時(shí)，軟件不會(huì)傳輸這些數(shù)據(jù)位。相反，它會(huì)發(fā)送一個(gè)指向該序列最初出現(xiàn)的位置的指針，以及匹配的序列的長(zhǎng)度。該指針需要的數(shù)據(jù)位數(shù)非常小。

“過(guò)去出版《電視指南》（TV Guide）時(shí)基本上就是這樣做的。”齊夫說(shuō)，“他們會(huì)把每個(gè)節(jié)目的梗概發(fā)布一次。如果某個(gè)節(jié)目出現(xiàn)了不止一次，他們就不會(huì)重新發(fā)布其梗概。他們會(huì)說(shuō)，請(qǐng)回看第x頁(yè)?！?/p>

以這種方式解碼甚至更簡(jiǎn)單，因?yàn)榻獯a器不必識(shí)別唯一的序列。相反，它通過(guò)跟隨指針來(lái)找到序列的位置，然后用相關(guān)序列的副本替換每個(gè)指針。

該算法完成了齊夫和倫佩爾的既定目標(biāo)。它證明，無(wú)需預(yù)處理的普遍最優(yōu)無(wú)損壓縮是可以實(shí)現(xiàn)的。

“在他們發(fā)表研究成果時(shí)，這種算法簡(jiǎn)潔明了、易于實(shí)現(xiàn)且計(jì)算復(fù)雜度較低的優(yōu)點(diǎn)其實(shí)幾乎都無(wú)關(guān)緊要了?！彼固垢４髮W(xué)從事信息理論研究的電氣工程學(xué)教授查希?維斯曼（Tsachy Weissman）說(shuō)，“更重要的是理論結(jié)果?！?/p>

不過(guò)，維斯曼說(shuō)，研究人員最終承認(rèn)了這種壓縮算法的實(shí)際意義?！拔覀兊募夹g(shù)開始處理超過(guò)10萬(wàn)甚至100萬(wàn)字符的更大的文件時(shí)，算法本身真的非常有用。”

“他們的故事是一個(gè)關(guān)于基礎(chǔ)理論研究的力量的故事?！本S斯曼補(bǔ)充說(shuō)，“你可以設(shè)立一個(gè)理論結(jié)果，說(shuō)明什么應(yīng)該是可以實(shí)現(xiàn)的，幾十年后，人類將因執(zhí)行了以這些結(jié)果為基礎(chǔ)的算法而獲益?！?/p>

齊夫和倫佩爾繼續(xù)研究這項(xiàng)技術(shù)，試圖讓小數(shù)據(jù)文件更接近熵。他們的努力推動(dòng)了LZ78的誕生。齊夫說(shuō)，LZ78看起來(lái)和LZ77很相似，但實(shí)際上大有不同，因?yàn)樗梢灶A(yù)測(cè)下一個(gè)數(shù)據(jù)位?！凹僭O(shè)第一個(gè)數(shù)據(jù)位是1，那么你會(huì)在字典中輸入兩個(gè)代碼，1-1和1-0，”他解釋說(shuō)，“你可以把這兩個(gè)序列想象成一棵樹的第一組分枝。”

齊夫說(shuō)：“當(dāng)?shù)诙€(gè)數(shù)據(jù)位出現(xiàn)時(shí)，如果是1，你就把指針指向第一個(gè)代碼1-1，如果是0，你就指向另一個(gè)代碼1-0。然后就可以通過(guò)向這棵樹的選定分枝再添加兩個(gè)可能性來(lái)擴(kuò)展字典。重復(fù)執(zhí)行這個(gè)操作，出現(xiàn)頻率更高的序列將長(zhǎng)出更長(zhǎng)的分枝?！?/p>

“事實(shí)證明，”他說(shuō)，“這不僅是最佳（方法），而且非常簡(jiǎn)單，馬上就變得有用了?！?/p>

齊夫和倫佩爾在開發(fā)LZ78時(shí)都在停教休假，不在以色列理工學(xué)院，而是在美國(guó)公司工作。他們知道他們的算法將在商業(yè)上大放光彩，所以想申請(qǐng)專利。

“我當(dāng)時(shí)在貝爾實(shí)驗(yàn)室，”齊夫回憶道，“所以我以為專利應(yīng)該屬于他們。但他們說(shuō)，除非是硬件，否則不可能獲得專利，而且他們也沒(méi)有興趣嘗試。”（美國(guó)最高法院直到20世紀(jì)80年代才向軟件直接專利保護(hù)敞開了大門。）

不過(guò)，倫佩爾的雇主斯佩里蘭德公司（Sperry Rand Corp.）愿意嘗試。它繞過(guò)了軟件專利的限制，開發(fā)了執(zhí)行該算法的硬件，并為該設(shè)備申請(qǐng)了專利。緊隨第一項(xiàng)專利之后，斯佩里蘭德推出了一個(gè)由研究員特里?韋爾奇（Terry Welch）改編的版本，稱為L(zhǎng)ZW算法。LZW版本傳播最為廣泛。

不能直接為L(zhǎng)Z78申請(qǐng)專利，齊夫感到很遺憾，但他說(shuō)：“我們很高興（LZW算法）非常受歡迎。它使我們成名，我們也很喜歡它帶來(lái)的研究?！?/p>

隨之也產(chǎn)生了一個(gè)概念，稱為“倫佩爾-齊夫復(fù)雜度”，它衡量的是一個(gè)數(shù)據(jù)位序列中包含的唯一子串的數(shù)量。唯一子串越少，序列就越可以被進(jìn)一步壓縮。

該方法后來(lái)被用于檢查加密代碼的安全性；如果一個(gè)代碼真的是隨機(jī)代碼，它就不能被壓縮。倫佩爾-齊夫復(fù)雜度也被用于分析腦電活動(dòng)的腦電圖記錄，以確定麻醉深度、診斷抑郁癥以及其他用途。研究人員甚至用它來(lái)分析流行歌詞，確定重復(fù)的趨勢(shì)。

在齊夫的職業(yè)生涯中，他發(fā)表了大約100篇同行評(píng)議論文。雖然1977年和1978年的論文最為出名，但齊夫之后的信息理論家們也有自己最愛的論文。

以色列理工學(xué)院的著名教授什洛莫?沙邁（Shlomo Shamai）最喜歡的是齊夫1976年的一篇論文，論文介紹了懷納-齊夫算法，這是一種描述解碼器而不是編碼器的可用補(bǔ)充信息的使用限制的方法。比如，有的視頻應(yīng)用利用了解碼器已破譯前一幀畫面的事實(shí)，其中就會(huì)出現(xiàn)這個(gè)問(wèn)題，因此可以將其用作編碼下一幀的邊信息。

普林斯頓大學(xué)電氣工程學(xué)教授文森特?普爾（Vincent Poor）最喜歡的是齊夫1969年的一篇論文，論文介紹了齊夫-扎凱界限，這是一種確定信號(hào)處理器是否能從給定信號(hào)中獲得最準(zhǔn)確信息的方法。

齊夫于1985年之前在以色列理工學(xué)院教授的課程也啟發(fā)了許多一流數(shù)據(jù)壓縮專家。維斯曼曾是其中一名學(xué)生，他說(shuō)齊夫“充滿了激情，醉心于把壓縮作為量化信息的一種方式所體現(xiàn)的數(shù)學(xué)之美。1999年我上過(guò)他的課，這對(duì)我走上自己的研究道路產(chǎn)生了很大影響。”

他不是唯一深受啟發(fā)的人?！?979年開始碩士研究學(xué)習(xí)的時(shí)候，我上了一門齊夫的信息理論課，”沙邁說(shuō)，“40多年過(guò)去了，我仍然記得那門課。它讓我渴望了解這些題，進(jìn)行研究，并攻讀博士學(xué)位深造。”

近年來(lái)，青光眼奪走了齊夫的大部分視力。他說(shuō)，今年1月在《IEEE信息理論學(xué)報(bào)》上發(fā)表的論文是他的最后一篇論文。他已89歲高齡了。

“兩年半前我開始寫這篇論文，那時(shí)以我的視力還可以用電腦，”他說(shuō)，“最后，以色列理工學(xué)院的年輕教員尤瓦爾?卡蘇托（Yuval Cassuto）完成了這個(gè)項(xiàng)目。 ”這篇論文討論了在哪些情況下，需要將大型信息文件快速傳輸?shù)竭h(yuǎn)程數(shù)據(jù)庫(kù)。

正如齊夫解釋的那樣，當(dāng)醫(yī)生想要將一位患者的DNA樣本和該患者過(guò)去的樣本進(jìn)行比較以確定是否發(fā)生突變時(shí)，或是與一個(gè)DNA庫(kù)進(jìn)行比較以確定患者是否有遺傳病時(shí)，就可能產(chǎn)生這樣的需求?；蛘咭环N新病毒的研究人員可能想將其DNA序列與已知病毒的DNA數(shù)據(jù)庫(kù)進(jìn)行比較，也可以應(yīng)用這種技術(shù)。

“問(wèn)題是，DNA樣本中的信息量巨大，”齊夫說(shuō)，“大到今天的網(wǎng)絡(luò)花幾個(gè)小時(shí)甚至幾天都無(wú)法發(fā)送。比如說(shuō)，你正試圖識(shí)別那些變化很快的病毒，花費(fèi)的時(shí)間可能會(huì)很多。”

他和卡蘇托描述的方法會(huì)使用數(shù)據(jù)庫(kù)里常見的已知序列來(lái)幫助壓縮新數(shù)據(jù)，而不會(huì)首先檢查新數(shù)據(jù)和已知序列之間有沒(méi)有特定匹配。