你發(fā)表情包全靠他，GIF壓縮算法發(fā)明者之一獲IEEE最高榮譽(yù)獎(jiǎng)

曉查 發(fā)自 凹非寺?
量子位 報(bào)道 | 公眾號(hào) QbitAI

現(xiàn)年90歲的以色列科學(xué)家Jacob Ziv，獲得了2021年IEEE榮譽(yù)獎(jiǎng)?wù)?/strong>（IEEE Medal of Honor），以此表彰他“對(duì)信息論和數(shù)據(jù)壓縮技術(shù)的基本貢獻(xiàn)，以及杰出的研究領(lǐng)導(dǎo)地位”。

△?Jacob Ziv

IEEE榮譽(yù)獎(jiǎng)?wù)掠蒊EEE每年評(píng)選頒發(fā)，是世界電氣電子工程學(xué)界的最高榮譽(yù)。

在1977年和1978年，Jacob Ziv與另一名以色列科學(xué)家Abraham Lempel發(fā)明了以他們名字命名的通用無損壓縮算法LZ77和LZ78.

這套算法在2004年被評(píng)為IEEE里程碑。

LZ算法后來形成了許多無損壓縮算法的變體，比如LZW、LZSS、LZMA等。

這些衍生算法至今仍在我們的計(jì)算機(jī)上使用，包括GIF、PNG圖像壓縮和RAR、ZIP文件壓縮。

一位支持Ziv獲得該獎(jiǎng)項(xiàng)的工程師表示：“LZ算法是第一個(gè)成功的通用壓縮算法?！薄斑@些算法，以及雅各布對(duì)這些算法的分析，構(gòu)成了之后大多數(shù)通用算法工作的基礎(chǔ)。”

LZ算法能使壓縮數(shù)據(jù)能夠?qū)崿F(xiàn)數(shù)據(jù)的完全重建，并且比之前的壓縮算法更有效率。

與其他算法相比，Ziv首創(chuàng)的這種通用源碼編碼，無需了解數(shù)據(jù)的固有信息，即可壓縮數(shù)據(jù)，降低了從數(shù)據(jù)中重建圖像所需的數(shù)據(jù)率要求。

此外，Ziv還為錯(cuò)誤校正碼的低計(jì)算復(fù)雜度解碼理論做出了貢獻(xiàn)。

LZ壓縮算法簡(jiǎn)介

LZ77和LZ78是Abraham Lempel和Jacob Ziv二人在1977和1978年的論文中發(fā)表的兩種無損數(shù)據(jù)壓縮算法。它們也分別被稱為L(zhǎng)Z1和LZ2。

LZ算法的工作原理是將字符串替換為單個(gè)token碼。算法每識(shí)別到一個(gè)新字符串時(shí)，都會(huì)輸出該字符串，然后將其添加到表或字典中。

△?LZW壓縮算法

下次再遇到該字符串時(shí)，則用表中的token碼代替。這樣就達(dá)到了數(shù)據(jù)壓縮和提高傳輸效率的目的。

舉一個(gè)簡(jiǎn)單的例子：

I am an engineer therefore I am an engineer, and only if I am an engineer.

經(jīng)過壓縮后，這句話變?yōu)椋?/p>

I am an engineer?there&fo& *, and only if *.

在上面這段話中，第一次出現(xiàn)的I am an engineer被壓縮成*，第一次出現(xiàn)的re被壓縮成&，因此后面再出現(xiàn)相同字符串后，只需要用*和&兩個(gè)字符代替即可。

如果原來字符串越長(zhǎng)越冗余，實(shí)現(xiàn)的壓縮率就越高。

由于LZ算法首先發(fā)送字符串和token碼，反向解壓縮算法可以重建原始消息，因此無需任何附加信息（如字典本身）。

LZ算法的簡(jiǎn)單與易用性使其具有廣泛的應(yīng)用。時(shí)至今日，其重要的用途之一是存儲(chǔ)和發(fā)送GIF圖像文件。

Jacob Ziv生平

Jacob Ziv于1931年出生在以色列的太巴列，分別在1954年和1957年獲得以色列理工學(xué)院的電氣工程學(xué)士和碩士學(xué)位，之后赴美留學(xué)于1962年獲得麻省理工學(xué)院博士學(xué)位。

1968年，Ziv加入AT&T貝爾實(shí)驗(yàn)室，擔(dān)任技術(shù)人員。1970年，他回到以色列，成為母校以色列理工學(xué)院的教授，后又成為該校電氣工程學(xué)院院長(zhǎng)。

此前，Ziv已獲得過IEEE頒發(fā)的多項(xiàng)榮譽(yù)。

1995年，他因“對(duì)信息理論以及數(shù)據(jù)壓縮的理論和實(shí)踐的貢獻(xiàn)”而獲得IEEE漢明獎(jiǎng)。1997年，他獲得了通信理論領(lǐng)域最高獎(jiǎng)——由IEEE信息論學(xué)會(huì)頒發(fā)的香農(nóng)獎(jiǎng)。

參考鏈接：
https://spectrum.ieee.org/the-institute/ieee-member-news/ieee-medal-of-honor-goes-to-data-compression-pioneer-jacob-ziv
https://ethw.org/Milestones:Lempel-Ziv_Data_Compression_Algorithm,_1977

程序員專欄
?掃碼關(guān)注填加客服?
長(zhǎng)按識(shí)別下方二維碼進(jìn)群

近期精彩內(nèi)容推薦：??

?阿里徹底拆中臺(tái)了！

?程序員相親圖鑒

?21 歲理工男開源的這個(gè)編輯器火了！

?996 違法？？？

在看點(diǎn)這里好文分享給更多人↓↓