90 岁程序员：他的压缩算法改变了世界！

近日，国际电气与电子工程学会（Institute of Electrical and Electronics Engineers，简称IEEE）宣布，授予IEEE终身Fellow Jacob Ziv 2021度IEEE荣誉勋章。

20世纪70年代，随着互联网及PC时代的来临，如何在有限内存空间的设备上节省出更多的空间，并减少对带宽的占用，让文件在较低的网络带宽下实现更快的传输，成为彼时IT行业亟需解决的一大难题。

正因此，数据压缩技术也从背后逐渐走入大众视野，并开始在计算机领域扮演重要角色。

现如今，想必很多人都知道，数据压缩主要有两种类型：一种是有损压缩，一种是无损压缩。

所谓有损压缩，主要是利用了人类对图像或声波中的某些频率成分不敏感的特性，允许压缩过程中损失一定的信息，日常生活中，我们常见的语言、图像、视频压缩其实都是有损压缩的方式。

与有损压缩相比，无损压缩要更为复杂一些，对此，IEEE 官方使用了「魔术」一词来形容这门技术，其中原因主要是因为无损压缩技术是利用数据的统计冗余进行压缩，在解压之后，可完全恢复原始数据而不引起任何失真。这就像一位魔术师拿着魔术棒一挥，手中的东西不见了，再一挥，又原封不动地出现了，无损压损技术就像表演魔术一样。

而Jacob Ziv就是这位在数据压缩领域拿着魔术棒的大师。

不过，在Jacob Ziv这位魔术师带来奇特的魔术之前，压缩算法也经历了百年的发展历程

http://ethw.org/History_of_Lossless_Data_Compression_Algorithms

• 事实上，发明于1838年的Morse code，是最早的数据压缩实例。
• 随着大型机的兴起，数学家香农和Robert Fano（CSAIL的计算先驱和创始人）发明了Shannon-Fano（香农-范诺）编码算法。他们的算法基于符号(symbol)出现的概率来给符号分配编码(code)。一个符号出现的概率大小与对应的编码成反比，从而用更短的方式来表示符号。
• 1951年，作为麻省理工的一名学生，David Huffman选择写学期论文而非期末考试的方式来完成学业任务，彼时他的论文题目是寻找二叉编码的最优算法。不过，遗憾的是，经过几个月的努力后依然没有任何成果，Huffman 决定放弃所有论文相关的工作，开始学习为参加期末考试做准备。就在那时，Huffman 偶然间找到一个与Shannon-Fano编码相类似但是更有效的编码算法，这种编码方式效率高、运算速度快。
• 后来到了20世纪70年代，随着在线存储的出现，哈夫曼编码得到了广泛应用。不过，经过不断地尝试，不少科学家发现哈夫曼编码所得的编码长度只是对信息熵（描述信源的不确定度）计算结果的一种近似，还无法真正逼近信息熵的极限。同时，它需要两次通过数据文件：一次计算文件的统计特征，第二次编码数据。将字典与编码数据一起存储，增加了压缩文件的大小。

1977年，来自以色列的Jacob Ziv和Abraham Lempel两位技术大神打破传统的设计思想，创造出一种哈夫曼编码更有效的压缩算法，并以两个人名字来命名。同时，他们还发表了一篇名为《A Universal Algorithm for Sequential Data Compression》（顺序数据压缩的一个通用算法 ，https://www2.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1977_universal_algorithm.pdf）的论文，揭晓了独创的LZ77算法，这也是第一个使用字典来压缩数据的算法。

次年，Jacob Ziv和Abraham Lempel再次发表一篇改进版的论文（《Compression of Individual Sequences via Variable Rate Coding》），并带来了LZ78的压缩算法。与LZ77不同，LZ78解析输入数据，生成一个静态字典，不像LZ77动态产生。该算法成为80年代初使用的 Unix 压缩程序的基础；影响了90年代的WinZip和Gzip，为GIF、TIFF图片格式的开发带来了一定的指引。

这一切都需要感谢Jacob Ziv和Abraham Lempel。

回顾Ziv的过往经历，其跨越了半个世纪，将自己全身心地投入到压缩算法领域中。

1931年，出生在当时由英国统治的巴勒斯坦城市Tiberias（现属于以色列）的Ziv，在很小的时候，Ziv就对电力和电子产品有着浓厚的兴趣，譬如，在练习小提琴的时候，他会尝试把乐谱架变成一盏灯。此外，他还试图用钢琴弹奏的金属零件制作一个马可尼发射机。

1948年，第一次阿以战争爆发时他在读高中，后来被征召到前线短暂地服过役。由于一群母亲组织抗议，他才从前线回到了后方，在空军受训担任雷达技师。战争结束后，他进入以色列理工学院学习电气工程。

在1955年完成硕士学位后，Ziv重返国防界，并加入了以色列国防研究实验室（现为拉斐尔先进防御系统），开发用于导弹和其他军事系统的电子元件。

1959年，Ziv被选为以色列国防实验室为数不多的出国留学的研究人员之一。那时，Ziv计划继续从事通信工作，但他不再只对硬件感兴趣。偶然机遇之下，他阅读了《信息理论》（Prentice-Hall，1953年）的书籍，他决定将信息理论作为他关注的焦点。然而，除了麻省理工学院之外，还有什么地方可以研究信息理论呢？

当然还是麻省理工！于是，1960年，Ziv进入MIT读博，在信息理论方面深造，在毕业返回以色列后进入了国防部担任通信部门主管。

1968年，他返回美国，进入了贝尔实验室。

两年后，Ziv和几个同事一起加入了以色列理工学院。就是在这里，他遇到了Abraham Lempel，两个人共同讨论了如何改进无损数据压缩。

Ziv和Lempel都想知道他们是否可以开发一种无损数据压缩算法，该算法适用于任何类型的数据，不需要预处理，并且能够实现数据的最佳压缩，这个目标被称为Shannon熵的对象定义。在设想时，他们并不清楚是否可以实现他们的目标。于是，他们决定找出答案。

在深入研究几年后，随着LZ77和LZ78的出现，代表了其研究成功。Ziv和Lempel开创了通用源编码，一系列无需知道固有信息压缩数据的算法，减少了从不失真和失真数据重建图像所需的数据率。

对此，斯坦福大学从事信息理论的电气工程教授Tsachy Weissman表示："在他们发表作品时，算法清晰优雅，易于实现，计算复杂度低，这一事实几乎无关紧要。更多的是关于理论结果，为接下来的研究带来重要意义。"

另外，Ziv还促成了错误校正代码的低计算复杂性解码理论。并于：

• 1993年，因精确科学而被授予以色列奖（Israel Prize）；
• 1995年，因其“对信息理论、数据压缩的理论和实践的贡献”获得 IEEE 理查德 · 汉明奖章；
• 1997年，获得IEEE信息论学会的克劳德 · 香农奖；
• 2008年，获得BBVA基金会知识前沿奖。

如今，凭借「其对信息理论和数据压缩技术的重要贡献和杰出的研究领导地位」，被授予2021年度IEEE荣誉勋章，可谓实至名归，向依旧奋战在研究一线的前辈致敬！

https://spectrum.ieee.org/geek-life/profiles/from-winzips-to-cat-gifs-jacob-zivs-algorithms-have-powered-decades-of-compression