你发表情包全靠他,GIF压缩算法发明者之一获IEEE最高荣誉奖

90岁以色列高龄学者获奖

晓查 发自 凹非寺  

量子位 报道 | 公众号 QbitAI

现年90岁的以色列科学家 Jacob Ziv ,获得了2021年 IEEE荣誉奖章 (IEEE Medal of Honor),以此表彰他“对信息论和数据压缩技术的基本贡献,以及杰出的研究领导地位”。

△ Jacob Ziv

IEEE荣誉奖章由IEEE每年评选颁发,是世界电气电子工程学界的最高荣誉。

在1977年和1978年,Jacob Ziv与另一名以色列科学家 Abraham Lempel 发明了以他们名字命名的通用无损压缩算法 LZ77 LZ78 .

这套算法在2004年被评为 IEEE里程碑

LZ算法后来形成了许多无损压缩算法的变体,比如LZW、LZSS、LZMA等。

这些衍生算法至今仍在我们的计算机上使用,包括 GIF PNG 图像压缩和 RAR ZIP 文件压缩。

一位支持Ziv获得该奖项的工程师表示:“LZ算法是第一个成功的通用压缩算法。”“这些算法,以及雅各布对这些算法的分析,构成了之后大多数通用算法工作的基础。”

LZ算法能使压缩数据能够实现数据的完全重建,并且比之前的压缩算法更有效率。

与其他算法相比,Ziv首创的这种通用源码编码,无需了解数据的固有信息,即可压缩数据,降低了从数据中重建图像所需的数据率要求。

此外,Ziv还为错误校正码的低计算复杂度解码理论做出了贡献。

LZ压缩算法简介

LZ77和LZ78是Abraham Lempel和Jacob Ziv二人在1977和1978年的论文中发表的两种无损数据压缩算法。它们也分别被称为LZ1和LZ2。

LZ算法的工作原理是将字符串替换为单个token码。算法每识别到一个新字符串时,都会输出该字符串,然后将其添加到表或字典中。

△ LZW压缩算法

下次再遇到该字符串时,则用表中的token码代替。这样就达到了数据压缩和提高传输效率的目的。

举一个简单的例子:

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

经过压缩后,这句话变为:

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

在上面这段话中,第一次出现的I am an engineer被压缩成 *, 第一次出现的re被压缩成 &, 因此后面再出现相同字符串后,只需要用*和&两个字符代替即可。

如果原来字符串越长越冗余,实现的压缩率就越高。

由于LZ算法首先发送字符串和token码,反向解压缩算法可以重建原始消息,因此无需任何附加信息(如字典本身)。

LZ算法的简单与易用性使其具有广泛的应用。时至今日,其重要的用途之一是存储和发送GIF图像文件。

Jacob Ziv生平

Jacob Ziv于1931年出生在以色列的太巴列,分别在1954年和1957年获得以色列理工学院的电气工程学士和硕士学位,之后赴美留学于1962年获得麻省理工学院博士学位。

1968年,Ziv加入AT&T贝尔实验室,担任技术人员。1970年,他回到以色列,成为母校以色列理工学院的教授,后又成为该校电气工程学院院长。

此前,Ziv已获得过IEEE颁发的多项荣誉。

1995年,他因“对信息理论以及数据压缩的理论和实践的贡献”而获得 IEEE汉明奖 。1997年,他获得了通信理论领域最高奖——由IEEE信 息论 学会颁发的 香农奖

参考链接: 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

版权所有,未经授权不得以任何形式转载及使用,违者必究。