Ziv与他的无损压缩算法

时间：08-19来源：作者：点击数：

无损数据压缩有点像魔术。它哥哥，有损压缩，更容易被理解。有损算法被用来把音乐转换成MP3格式，并将数字图像变成标准的JPEG文件。它们有选择地删除比特，利用科学家对我们的视听方式的了解来确定哪些比特我们最不愿意错过。但是，没有人能够证明所产生的文件是原始文件的完美复制品。

无损数据压缩则不然。比特确实被删去了，数据文件大大缩小，从而更容易存储和传输。区别则是，被剔除的比特可按指令重新出现。这就像魔术师帽子里的兔子一样。

魔术界有哈里·胡迪尼，他开创了至今仍在表演的戏法。而数据压缩有雅各布·齐夫(JacobZiv)。

1977年，齐夫与亚伯拉罕·伦佩尔AbrahamLempel合作，发表了相当于魔术界的胡迪尼开创逃生术的文章：《顺序数据压缩的通用算法》。论文中描述的算法后来被称为LZ77——分别代表作者的名字，按字母顺序排列，还有年份。LZ77并不是第一个无损压缩算法，但它是第一个散发出魔力的算法。

第二年，两位研究人员又发布了改进版，即LZ78。该算法成为80年代初使用的Unix压缩程序、90年代初诞生的WinZip和Gzip、以及GIF和TIFF图像格式的基础。如果没有这些算法，我们很可能还需要邮寄光盘来转移大型数据文件，而非在互联网上点击发送；用CD购买音乐，而非流媒体；无聊图里也不会有动态图。

齐夫继续与其他研究人员合作进行压缩方面的其他创新。正是他跨越半个多世纪的全部工作，为他赢得了2021年IEEE荣誉奖章，"表彰他对信息理论和数据压缩技术的基本贡献，以及杰出的研究领导能力"。

齐夫于1931年出生在太巴列，父母是俄罗斯移民。这个城市当时位于英国统治的巴勒斯坦，现在是以色列的一部分。电器和小玩意——以及其他一些东西——自小时候就已让他着迷不已。例如，在练习小提琴时，他想出了一个方案，将他的音乐架改造成一盏灯。他还试图用金属钢琴零件制造一个马可尼发射器。当他把这个装置插上电时，整个房子都黑了。他从未让那个发射器工作过。

1955年拿到硕士学位后，齐夫加入了以色列国防研究实验室(现在的拉斐尔先进防御系统)，开发用于导弹和其他军事系统的电子元件。齐夫回忆说，麻烦的是，包括他自己在内，小组中没有一个工程师对电子学有更多的基本了解。他们的电气工程教育更多地集中在电力系统方面。

"我们有大约六个人，必须自学。我们会挑选一本书，然后一起学习，就像犹太人学习希伯来圣经一样。但这还不够。"

该小组的目标是建立一个使用晶体管而不是真空管的遥测系统。他们不仅需要知识，还需要材料。齐夫联系了贝尔电话实验室，要求免费提供晶体管样品；该公司送来了100个。

"这满足了我们几个月的需求，"他说。"我认为自己是以色列第一个认真搞晶体管的人。"

1959年，齐夫被外派到国外学习。他说，这一计划改变了以色列科学的发展。组织者并未规划年轻工程师的特定领域。相反，他们允许年轻人在任意西方国家进行任意类型的学习。

齐夫打算留在通信领域，但他不再仅对硬件感兴趣。他当时读了斯坦福·戈德曼(StanfordGoldman)的《信息论》(Prentice-Hall，1953年)——关于该主题的最早的教材之一。他决定将信息论作为自己的重点。除了麻省理工学院，还有什么地方可以研究信息理论呢，当然是信息论的开创者克劳德·香农那里。

齐夫于1960年来到马萨诸塞州的剑桥市。

"信息理论是美丽的，它告诉你什么是你能达到的最好结果，告诉你如何逼近这个结果。因此，如果你投入计算，你就可以知道你正在接近可能的最佳结果。"

在麻省理工学院时，齐夫为美国国防承包商Melpar公司做兼职，在那里他开发纠错软件。他发现当时的工具不太理想。他回忆说："当时为了运行一个程序，必须使用打卡机，而我讨厌它们。这就是为什么我没有进入计算机科学。"

在美国呆了两年后回到国防研究实验室，齐夫负责通信部门的工作。在那里他遇到了亚伯拉罕·伦佩尔。两人讨论了如何改进原始的无损数据压缩算法。

当时，无损数据压缩技术应用哈夫曼编码。这种方法首先在数据文件中找到比特序列，然后根据它们出现的频率对它们进行排序。然后编码器建立一个字典，其中最常见的序列由最少的比特数表示。这也是摩尔斯码背后的思想。英语中出现频率最高的字母——e，由一个点表示，而较少见的字母则用点和破折号组成更复杂的组合替代。

齐夫和伦佩尔想知道他们是否能开发出一种无损的数据压缩算法，可以适用于任何类型的数据，不需要预处理，并能实现对该数据的最佳压缩——这一概念由所谓的香农熵定义。当时还不清楚他们的目标是否在理论上是可行。他们决定动手寻找答案。

齐夫认为，他们两人是解决这个问题的"完美拍档"。"我对信息理论和统计学了如指掌，而亚伯拉罕在布尔代数和计算机科学方面装备精良"。

两人想出了让算法在压缩数据的同时寻找独特的比特序列的想法，使用指针来记录之前看到的序列。这种方法只需要解析一次文件，所以它比哈夫曼编码快。

"你看一下传入的比特，找到之前匹配的最长的比特段。比方说，第一个传入的比特是1。现在，由于你只有一个比特，你在过去从未见过它，所以你没有选择，只能按原样传输。但随后你得到了另一个比特，说那也是一个1。所以你在你的字典里输入1-1。说下一个位是0，所以在你的字典里现在有1-1和1-0。"

指针的作用就在这里。下一次比特流包括1-1或1-0时，软件并不传送这些比特。相反，它发送一个指向该序列首次出现的位置的指针，以及匹配序列的长度。你为这个指针所分配的比特数是非常小的。

这种算法更加简单，因为解码器不需要识别独特的序列。相反，它通过跟踪指针找到序列的位置，然后用相关序列的副本替换每个指针。

该算法实现了齐夫和亚伯拉罕所要求的一切——它证明了无需预处理的普遍最佳无损压缩是可能的。

最终，研究人员认识到该算法的实际意义，"当我们开始处理超过10万或甚至100万个字符的更大的文件时，该算法本身变得非常有用。"

齐夫和伦佩尔继续研究，试图使小型数据文件更接近完美压缩。这项工作导致了LZ78的出现。齐夫说，LZ78似乎与LZ77相似，但实际上非常不同，因为它预测了下一个比特。他解释说："比方说，第一个比特是1，所以你在字典中输入两个代码，1-1和1-0。你可以把这两个序列想象成一棵树的第一个分支。当第二位到来时，如果它是1，你就把指针送到第一个代码，即1-1，如果它是0，你就指向另一个代码，即1-0。然后你通过在树的选定分支上再添加两种可能性来扩展字典。当你反复这样做的时候，出现频率更高的序列会生长出更长的分支。"

"事实证明，"他说，"这不仅是最佳，而且如此简单，以至于它马上就变得有用。"

他们知道自己的成果具备商业价值，他们想为它申请专利。

"我当时在贝尔实验室，"齐夫回忆说，"所以我认为专利应该属于贝尔实验室。但他们说，除非是硬件，否则不可能获得专利，而且他们也没有兴趣去尝试。"(美国最高法院直到20世纪80年代才为软件的直接专利保护打开大门。)

然而，伦佩尔的雇主，SperryRand公司，愿意尝试。它通过制造实现算法的硬件并为该设备申请专利(LZW)来绕过对软件专利的限制。

齐夫对未能直接为LZ78申请专利感到遗憾，但是，他说："我们很享受非常流行的事实。它使我们出名，我们也享受它所带来的。"

随之而来的一个概念被称为Lempel-Ziv复杂性，这是衡量一串比特中包含的唯一子串数量的标准。唯一的子串越少，一个序列就越能被压缩。

这一定义后来被用于检查加密代码的安全性；如果一个代码是真正随机的，它就不能被压缩。Lempel-Ziv复杂性也被用来分析脑电图。研究人员甚至将其用于分析流行歌词，以确定流行趋势。

在他的职业生涯中，齐夫发表了大约100篇经同行评审的论文。虽然1977年和1978年的论文是最著名的，但在信息领域，齐夫之后也有令其他研究人员赞叹不已的文章。

如1976年的论文介绍了Wyner-Ziv算法。

近年来，青光眼已经夺走了齐夫的大部分视力。他说，今年1月发表在IEEE《信息论》上的一篇论文是他学术生涯里最后一篇文章。他今年已经89岁。

该论文讨论了需要将大型信息文件快速传输到远程数据库的情况。

分析新病毒的研究人员可能希望将其DNA序列与已知病毒的DNA数据库进行比较。