90岁程序员：他嘅压缩算法改变‌世界

转载：本文来自微信公众号“程序人生”（ID:coder_life），整理：苏宓，转载经授权发布。

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

Jacob Ziv

这位而家已 90 岁嘅前辈，系一位以色列科学家，他开发‌通用无损压缩算法 lempel-Ziv，为后来嘅 GIF、PNG 和 ZIP 文件嘅开发奠定‌坚实嘅基础。

无损压缩算法发展史

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

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

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

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

同有损压缩相比，无损压缩要更为复杂一啲，对此，IEEE 官方使用‌「魔术」一词来形容这门技术，其中原因主要是因为无损压缩技术是利用数据嘅统计冗余进行压缩，喺解压之后，可完全恢复原始数据而唔引起任何失真。这好似一位魔术师拿住魔术棒一挥，手中嘅嘢唔见嘎啦，再一挥，又原封唔动地出现咗，无损压损技术好似表演魔术一样。

而 Jacob Ziv 就是这位喺数据压缩领域拿住魔术棒嘅大师。

唔过，喺 Jacob Ziv 这位魔术师带来奇特嘅魔术之前，压缩算法也经历‌百年嘅发展历程（ 链接

• 事实上，发明于 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》（顺序数据压缩嘅一个通用算法 ， 链接 LZ77 算法，呢都系第一个使用字典来压缩数据嘅算法。

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

如果没有呢啲算法嘅存喺，而家嘅我哋唔一定能够使用更为便捷嘅网络就可以发送大型数据文件，或还停留喺将大型数据文件拷贝到光盘上进行传输时代；听音乐时，仲有可能需要 CD 而唔系通过流式传输……

Ziv 嘅过往经历

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

“LZ 算法是第一个成功嘅通用压缩算法”，一位支持 Ziv 获奖嘅工程师如是说。呢啲算法以及 Jacob Ziv 对佢们嘅分析，为后续关于通用算法嘅大多数工作奠定‌基础。

回顾 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 荣誉勋章，可谓实至名归，向依然奋战喺研究一线嘅前辈致敬！

参考

链接

链接