以色列理工学院|90 岁程序员：他的压缩算法改变了世界！

整理 | 苏宓出品 |
CSDN（ID：CSDNnews）
近日，国际电气与电子工程学会（Institute of Electrical and Electronics Engineers，简称 IEEE）宣布，授予 IEEE 终身 Fellow Jacob Ziv2021 年度 IEEE 荣誉勋章。

文章插图
Jacob Ziv
这位如今已 90 岁的前辈，是一位以色列科学家，他开发了通用无损压缩算法 Lempel-Ziv，为后来的 GIF、PNG 和 ZIP 文件的开发奠定了坚实的基础。
无损压缩算法发展史
20 世纪 70 年代，随着互联网及 PC 时代的来临，如何在有限内存空间的设备上节省出更多的空间，并减少对带宽的占用，让文件在较低的网络带宽下实现更快的传输，成为彼时 IT 行业亟需解决的一大难题。
正因此，数据压缩技术也从背后逐渐走入大众视野，并开始在计算机领域扮演重要角色。
现如今，想必很多人都知道，数据压缩主要有两种类型：一种是有损压缩，一种是无损压缩。
所谓有损压缩，主要是利用了人类对图像或声波中的某些频率成分不敏感的特性，允许压缩过程中损失一定的信息，日常生活中，我们常见的语言、图像、视频压缩其实都是有损压缩的方式。
与有损压缩相比，无损压缩要更为复杂一些，对此，IEEE 官方使用了「魔术」一词来形容这门技术，其中原因主要是因为无损压缩技术是利用数据的统计冗余进行压缩，在解压之后，可完全恢复原始数据而不引起任何失真。这就像一位魔术师拿着魔术棒一挥，手中的东西不见了，再一挥，又原封不动地出现了，无损压损技术就像表演魔术一样。
而 Jacob Ziv 就是这位在数据压缩领域拿着魔术棒的大师。
不过，在 Jacob Ziv这位魔术师带来奇特的魔术之前，压缩算法也经历了百年的发展历程（https://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 算法，这也是第一个使用字典来压缩数据的算法。