胡正明|90 岁程序员：他的压缩算法改变了世界！( 二 )

文章插图
次年，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 信息论学会的克劳德 · 香农奖；
- 上一页
- 1
- 2
- 3
- 下一页