从winzip到猫动图，雅各布·齐夫的算法为几十年的压缩提供了动力

无损数据压缩看起来有点像魔术。它的兄弟，有损压缩，更容易理解。有损算法用于将音乐转换为流行的MP3格式，并将数字图像转换为标准的JPEG文件。他们通过有选择性地删除部分来做到这一点，利用科学家们对我们看和听的方式的了解，来确定哪些部分是我们最不会漏掉的。但没有人能证明，最终生成的文件是原始文件的完美复制品。

无损数据压缩就不是这样了。位确实消失了，使得数据文件大大变小，从而更容易存储和传输。重要的区别是，比特在命令下重新出现。这就像魔术师表演中的兔子一样，只要魔杖一挥，它们就会从帽子里消失，然后又出现。

魔术界有胡迪尼，他开创了至今仍在表演的魔术。数据压缩有Jacob Ziv。

1977年，齐夫和亚伯拉罕·伦佩尔合作，发表了相当于胡迪尼谈魔术的一篇论文IEEE信息论汇刊题为顺序数据压缩的通用算法论文中描述的算法后来被称为lz77——根据作者的名字(按字母顺序)和年份命名。LZ77不是第一个无损压缩算法，但它是第一个可以在一个步骤中发挥魔力的算法。

第二年，两位研究人员发布了改进版本LZ78。这个算法成为了80年代早期使用的Unix压缩程序的基础;90年代初诞生的WinZip和Gzip;以及GIF和TIFF图像格式。如果没有这些算法，我们可能会把大的数据文件装在光盘上，而不是通过互联网点击发送;我们可能会买cd上的音乐，而不是用流媒体播放;我们可能会看Facebook上没有跳动的动画图像的feeds。

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

齐夫出生了1931年，俄罗斯移民来到泰比利亚，这座城市当时在英国统治下的巴勒斯坦，现在是以色列的一部分。孩提时代，他对电和小玩意很感兴趣。例如，在练习小提琴时，他想出了一个把乐谱架变成灯的方案。他还试图用钢琴演奏的金属零件制造一个马可尼发射器。当他把这个装置插上电源时，整个房子都黑了。他一直没能修好发射机。

1948年阿以战争爆发时，齐夫正在上高中。他被征召加入以色列国防军(Israel Defense Forces)，在前线服役了一段时间，直到一群母亲举行了有组织的抗议，要求把最年轻的士兵送到其他地方。齐夫被重新分配到以色列空军，在那里他接受了雷达技术人员的培训。战争结束后，他进入以色列理工学院学习电气工程。

在1955年完成硕士学位后，齐夫回到了国防领域，这一次他加入了以色列国防研究实验室(现为国防研究实验室)拉斐尔先进防御系统)开发用于导弹和其他军事系统的电子元件。齐夫回忆说，问题在于，团队里的工程师，包括他自己在内，对电子学都只有基本的了解。他们的电气工程教育更侧重于电力系统。

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

该小组的目标是用晶体管代替真空管建立一个遥测系统。他们不仅需要知识，还需要零件。Ziv联系贝尔电话实验室，要求免费提供晶体管样品;公司寄了100张。

他说:“这足以满足我们几个月的需求。”“我为自己是以色列第一个认真研究晶体管的人而感到自豪。”

1959年，齐夫被选为以色列国防实验室为数不多的出国学习的研究人员之一。他说，这个项目改变了以色列科学的发展。它的组织者并没有引导被选中的年轻工程师和科学家进入特定的领域。相反，他们允许他们在任何西方国家从事任何类型的研究生学习。

齐夫打算继续在通信领域工作，但他不再只对硬件感兴趣了。他最近读到信息理论(Prentice-Hall, 1953)这方面最早的书籍他决定把研究重点放在信息论上。此外，除了该领域的先驱克劳德•香农(Claude Shannon)开始研究信息论的麻省理工学院，还能去哪里学习呢?

齐夫抵达马萨诸塞州坎布里奇。1960年。他的博士研究涉及一种确定如何编码和解码通过噪声信道发送的信息的方法，最大限度地减少概率和错误，同时保持解码简单。

“信息论是美丽的，”他说。“它告诉你你能做到的最好是什么，(它)告诉你如何接近结果。因此，如果你投入计算工作，你就会知道你正在接近最好的结果。”

齐夫将这种确定性与深度学习算法的不确定性进行了对比。很明显，算法是有效的，但没有人真正知道这是否是最好的结果。

在麻省理工学院时，齐夫在美国国防承包商做兼职工作Melpar他在那里从事纠错软件的工作。他觉得这件作品不那么漂亮了。他回忆道:“当时，为了运行计算机程序，你必须使用打孔卡。”“我恨他们。这就是为什么我没有进入真正的计算机科学领域。”

回到在美国国防研究实验室工作两年后，齐夫开始负责通讯部门。1970年，他和其他几位同事一起加入了理工学院．

在那里他遇到了亚伯拉罕·伦佩尔。两人讨论了如何改进无损数据压缩。

当时最先进的无损数据压缩技术是霍夫曼编码。这种方法首先在数据文件中找到比特序列，然后根据它们出现的频率对它们进行排序。然后编码器构建一个字典，其中最常见的序列由最小位数表示。这与莫尔斯电码的原理相同:英语中最常用的字母e由一个点表示，而更罕见的字母则由更复杂的点和破折号组合而成。

霍夫曼编码，虽然今天仍然在MPEG-2压缩格式和JPEG无损形式中使用，但也有它的缺点。它需要对数据文件进行两次遍历:一次计算文件的统计特征，第二次对数据进行编码。并且将字典与编码数据一起存储会增加压缩文件的大小。

Ziv和Lempel想知道他们是否能开发出一种无损数据压缩算法，适用于任何类型的数据，不需要预处理，并能实现数据的最佳压缩，这是由香农熵定义的目标。目前还不清楚他们的目标是否可能实现。他们决定一探究竟。

齐夫说，他和兰佩尔是解决这个问题的“完美搭档”。“我对信息论和统计学了如指掌，亚伯拉罕在布尔代数和计算机科学方面也很有造诣。”

两人提出了一个想法，让算法在压缩数据的同时寻找唯一的比特序列，使用指针引用先前看到的序列。这种方法只需要遍历一次文件，因此比Huffman编码要快。

Ziv是这样解释的:“你查看传入的比特，以找到在过去有匹配的比特的最长延伸。假设第一个输入位是1。现在，因为你只有一个比特，你以前从来没有见过它，所以你别无选择，只能照原样传输。”

他继续说道:“但接下来你会发现另一点。假设这也是1。在字典中输入1-1。假设下一位是0。所以在你的字典里你现在有1-1和1-0。”

这就是指针的用武之地。下一次比特流包含1-1或1-0时，软件就不传输这些比特了。相反，它发送一个指向该序列第一次出现的位置的指针，以及匹配的序列的长度。指针需要的比特数非常少。

“这基本上是他们过去在出版业的做法电视指南齐夫说。“他们会播放一遍每个节目的概要。如果节目出现了不止一次，他们就不会重新发布大纲。他们只是说，回到那一页x”。

以这种方式解码甚至更简单，因为解码器不需要识别唯一的序列。相反，它通过跟踪指针来查找序列的位置，然后用相关序列的副本替换每个指针。

该算法做到了Ziv和Lempel所要做的一切——它证明了不经过预处理的普遍最优无损压缩是可能的。

斯坦福大学专攻信息论的电气工程教授Tsachy Weissman说:“在他们发表研究成果的时候，这种算法简洁优雅，易于实现，计算复杂度低，这一点几乎是无关紧要的。”“更重要的是理论结果。”

韦斯曼说，尽管如此，研究人员最终还是认识到了这种算法的实际意义。“当我们的技术开始处理超过10万甚至100万个字符的更大文件时，算法本身变得非常有用。”

“他们的故事是一个关于基础理论研究力量的故事，”韦斯曼补充道。“你可以建立关于应该实现什么的理论结果，几十年后，人类将从基于这些结果的算法实现中受益。”

齐夫和伦佩尔继续研究这项技术，试图更接近小数据文件的熵值。这项工作导致了LZ78的诞生。Ziv说LZ78看起来和LZ77很相似，但实际上非常不同，因为它能预测下一个比特。“假设第一个比特是1，那么你在字典中输入两个代码，1-1和1-0，”他解释道。你可以把这两个序列想象成一棵树的第一个分支。”

“当第二个比特到来时，”齐夫说，“如果它是1，你就把指针发送到第一个代码，即1-1，如果它是0，你就指向另一个代码，即1-0。然后，通过向树的选定分支添加另外两种可能性来扩展字典。当你重复这样做时，出现频率更高的序列将会长出更长的分支。”

“事实证明，”他说，“这不仅是最优的(方法)，而且非常简单，马上就有用了。”

Jacob Ziv(左)和Abraham Lempel分别于1977年和1978年在《IEEE信息理论学报》上发表了无损数据压缩算法。这种方法被称为LZ77和LZ78，至今仍在使用。图片来源:Jacob Ziv/Technion

齐夫和当时Lempel正在研究LZ78，他们都在以色列理工学院休假，在美国公司工作。他们知道他们的开发将在商业上有用，他们想要申请专利。

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

然而，兰佩尔的雇主斯佩里兰德公司(Sperry Rand Corp.)愿意尝试。它通过构建实现算法的硬件并为该设备申请专利来绕过软件专利的限制。斯佩里·兰德(Sperry Rand)继第一个专利之后，又推出了一个由研究人员特里·韦尔奇(Terry Welch)改编的版本，称为LZW算法。传播最广泛的是LZW变体。

齐夫很遗憾未能直接为LZ78申请专利，但他说:“我们很高兴看到(LZW)非常受欢迎。它让我们出名，我们也很喜欢它引领我们进行的研究。”

随之而来的一个概念被称为伦佩尔-齐夫复杂性，是一种衡量比特序列中包含的唯一子字符串数量的方法。唯一子字符串越少，序列就越能压缩。

这一措施后来被用于检查加密代码的安全性;如果一个代码是真正随机的，它就不能被压缩。Lempel-Ziv复杂性也被用于分析脑电图(记录大脑电活动)确定麻醉深度,诊断抑郁症，以及作其他用途。研究人员甚至将其应用于分析流行歌词，以确定重复的趋势。

在他的职业生涯中，齐夫发表了大约100篇同行评议论文。虽然1977年和1978年的论文是最著名的，但在齐夫之后出现的信息理论家们也有自己的最爱。

对于以色列理工学院的著名教授Shlomo Shamai来说，这是1976年的论文Wyner-Ziv算法，一种描述使用解码器可用而编码器不可用的补充信息的限制的方法。例如，在视频应用程序中，解码器已经破译了前一帧，因此可以将其用作编码下一帧的辅助信息，这就出现了这个问题。

对于普林斯顿大学电气工程教授文森特·普尔来说，这是1969年的一篇描述齐夫-扎凯边界一种了解信号处理器是否从给定信号中获得尽可能准确的信息的方法。

直到1985年，Ziv还通过他在Technion教授的课程启发了许多领先的数据压缩专家。魏斯曼曾是齐夫的学生，他说齐夫“对压缩作为一种量化信息的方法的数学之美充满热情。1999年，我选修了他的一门课程，这对我走上自己的研究道路有很大帮助。”

他不是唯一一个受到启发的人。沙迈说:“1979年，在我硕士学习的开始阶段，我上了齐夫的信息论课。“40多年过去了，我仍然记得那门课。这让我渴望去研究这些问题，去做研究，去攻读博士学位。”

近年来，青光眼夺走了齐夫的大部分视力。他说一篇论文发表在IEEE信息论汇刊今年一月是他的最后一个一月。他今年89岁。

他说:“我在两年半前创办了这份报纸，当时我的视力还足以使用电脑。”“最后，以色列理工学院的年轻教员尤瓦尔·卡苏托完成了这个项目。”本文讨论了需要将大型信息文件快速传输到远程数据库的情况。

正如齐夫解释的那样，当医生想要将病人的DNA样本与同一病人过去的样本进行比较，以确定是否发生了突变，或者与DNA库进行比较，以确定病人是否患有遗传疾病时，这种需求可能会出现。或者，研究一种新病毒的研究人员可能希望将其DNA序列与已知病毒的DNA数据库进行比较。

“问题是DNA样本中的信息量太大了，”齐夫说，“今天的网络无法在几个小时甚至几天内发送太多信息。如果你试图及时识别变化非常快的病毒，时间可能太长了。”

他和Cassuto描述的方法包括使用数据库中常见的已知序列来帮助压缩新数据，而无需首先检查新数据和已知序列之间的特定匹配。

“我真的希望这项研究可以在未来得到应用，”齐夫说。如果他的过往记录有任何迹象，那么卡苏托-齐夫——或者也许是cz21——将为他的遗产锦上添花。

本文以“魔术师压缩”为题发表在2021年5月的印刷版上。