压缩魔术师：雅各布•齐夫 无损数据压缩有点像魔术。 有损压缩是与无损数据压缩相近的一个词，它更容易理解。有损算法用于将音乐转换成流行的MP3格式和将数字图像转换成标准的JPEG文件。这种算法会有选择地去除一些数据位来完成转换，利用科学家们对视听方式的了解来确定哪些数据位是我们最不会错过的，但没有人能保证生成的文件可以完美复刻原始文件。 无损数据压缩则不然。其中的数据位确实消失了，数据文件因此大大缩小，变得更易存储和传输。它与有损压缩的重要区别在于，这些数据位会根据命令重新出现。就像魔术表演中的兔子一样，它们在魔杖的挥动下从帽子里消失，然后又重新出现。 魔术界有胡迪尼（Houdini），他创造的魔术至今仍在表演，而数据压缩界则有雅各布•齐夫（JacobZiv）。 1977年，齐夫与亚伯拉罕•伦佩尔（Abraham Lempel）合作，在《IEEE信息理论学报》（IEEE Transactions on Information Theory）上发表了一篇论文，题目是《顺序数据压缩通用算法》（A Universal Algorithm for Sequential Data Compression），该论文与《胡迪尼说魔术》（Houdini on Magic）一样具有重要地位。按照作者姓名的字母顺序和发表年份，论文所述算法被称为LZ77。LZ77并不是第一种无损压缩算法，但却是第一种可以一步就发挥魔力的算法。 接下来的一年，这两位研究人员发布了改进版算法——LZ78。该算法成为了20世纪80年代使用的Unix压缩程序的基础，也是90年代初诞生的WinZip和Gzip的基础，以及GIF和TIFF图像格式的基础。如果没有这些算法，我们可能还在以光盘形式邮寄大型数据文件而不是通过互联网点击发送，可能还在购买CD听音乐而不是享受流式播放音乐，可能还在查看没有跳动动画图像的脸谱网订阅消息。 之后，齐夫继续与其他研究人员合作进行压缩方面的其他创新。正是他横跨半个多世纪的工作，让他因“对信息理论和数据压缩技术的重要贡献和杰出的研究领导”获得了2021年IEEE荣誉勋章。 1931年，齐夫出生在提比利亚的一个俄罗斯移民家庭。提比利亚当时是英国统治下的一个巴勒斯坦城市，现在属于以色列。孩童时期，齐夫就对电和小工具（以及其他小型装置）很感兴趣。比如，在练小提琴时，他设法把他的乐谱架变成了一盏灯。他还试图用钢琴的金属零件来制造马可尼发射机。不过把装置接通电源后，整座房子都断电了，于是那台发射机未能发挥作用。 1948年阿以战争爆发时，齐夫还在上中学。他被征召加入以色列国防军并在前线短暂服役，后来，一群母亲举行了有组织的抗议活动，要求把最年轻的士兵送到别处。随后，齐夫被调到以色列空军，接受了雷达技术员的训练。战争结束后，他进入了以色列理工学院学习电气工程。 1955年完成硕士学位的学习后，齐夫重返国防界，加入了以色列国防研究实验室（现为拉斐尔先进防御系统公司），开发用于导弹和其他军事系统的电子元件。齐夫回忆道，小组里的工程师（包括他自己）对电子学都学只有基本的了解。他们的电气工程教育更侧重于电力系统。 “我们有6个人，我们必须得自学。”他说，“我们会选一本书，然后一起学习，就像虔诚的犹太人学习《希伯来圣经》一样，但这还不够。” 该小组的目标是建立一个使用晶体管而非真空管的遥测系统。他们不仅需要知识，还需要零件。齐夫联系了贝尔电话实验室，请求对方免费提供一份晶体管样品；随后该公司提供了100份样品。 “这满足了我们几个月的需求。”他说，“我认为自己是以色列第一批认真研究晶体管的人。” 1959年，齐夫成为以色列国防实验室少数几位被选派出国留学的研究人员之一。他说，这个项目改变了以色列的科学发展。项目的组织者没有将入选的年轻工程师和科学家引入特定领域。相反，他们允许入选者选择任一西方国家攻读任何类型的研究生课程。 齐夫计划继续从事通信工作，但他不再只对硬件感兴趣了。他读了斯坦福•戈德曼的《信息理论》（Information Theory，普伦蒂斯•霍尔出版社，1953年），这是与该主题有关的最早的书作之一，于是他决定把信息理论作为自己的研究重点。麻省理工学院是学习信息理论的不二选择，这一领域的先驱克劳德•香农就是从那里开始的。 1960年，齐夫抵达马萨诸塞州的剑桥市。他的博士研究方向是要找到一种方法来对通过噪声信道发送的消息进行编码和解码，尽量降低概率和减少错误，同时保持解码的简单性。 “信息理论很美，”他说，“它会告诉你你所能取得的最好结果，还会告诉你如何接近这个结果。因此，如果投入计算工作量，你就可以知道自己正在接近可能的最佳结果。” 齐夫将这种确定性与深度学习算法的不确定性进行了对比。显然，深度算法是有效的，但是没有人真正知道它是否是最好的结果。 在麻省理工学院期间，齐夫还在美国国防承包商Melpar兼职，从事纠错软件的研究工作。他发现这项工作并不美好。“当时为了运行一个计算机程序，我们必须使用穿孔卡，”他回忆道，“我讨厌它们，因此我没有进入真正的计算机科学研究领域。” 在美国待了两年后，齐夫回到了以色列国防研究实验室，负责通信部门。1970年，他和其他几位同事加入了以色列理工学院。 在那里他遇到了亚伯拉罕•伦佩尔。两人对改进无损数据压缩进行了讨论。 当时最先进的无损数据压缩技术是哈夫曼编码。这种方法首先会在数据文件中查找数据位的序列，然后按它们出现的频率进行排序。之后，编码器会建立一个字典，其中用最小的数据位数字表示最常见的序列。摩尔斯电码也是同样的原理：英语中最常见的字母e用一个点表示，而不太常见的字母则用点和破折号等更复杂的组合来表示。 虽然目前MPEG-2压缩格式和无损形式的JPEG中仍然使用哈夫曼编码，但它有自身的缺点。它需要对一个数据文件浏览两次：一次是计算文件的统计特征，另一次对数据进行编码。而且，将字典与编码数据一起存储会让压缩文件更大。 齐夫和伦佩尔希望能开发出一种可以处理任何类型数据的无损数据压缩算法，它不需要预处理，并且可以实现对数据的最佳压缩。这也是“香农熵”定义的目标。虽然不清楚目标是否能实现，但他们决定试一试。 齐夫说，他和伦佩尔是解决这个问题的“完美搭档”。“我对信息理论和统计学了如指掌，而亚伯拉罕精通布尔代数和计算机科学。” 他们提出了一个想法：让算法在压缩数据的同时寻找唯一的数据位序列，使用指针来指向之前看到的序列。这种方法只需要对文件进行一次浏览，因此比哈夫曼编码更快。 齐夫解释说：“我们查看输入的数据位，找到过去匹配的最长的数据位段。假设第一个输入数据位是1。现在，由于只有一个数据位，过去从未见过它，所以我们别无选择，只能按原样传输它。” “然后，我们得到了另一个数据位，”他继续说，“假如也是1，那么我们会向字典输入1-1。假设下一位是0，那么我们的字典里就有了1-1和1-0。” 此时指针开始发挥作用。下次，当位流包含1-1或1-0时，软件不会传输这些数据位。相反，它会发送一个指向该序列最初出现的位置的指针，以及匹配的序列的长度。该指针需要的数据位数非常小。 “过去出版《电视指南》（TV Guide）时基本上就是这样做的。”齐夫说，“他们会把每个节目的梗概发布一次。如果某个节目出现了不止一次，他们就不会重新发布其梗概。他们会说，请回看第x页。” 以这种方式解码甚至更简单，因为解码器不必识别唯一的序列。相反，它通过跟随指针来找到序列的位置，然后用相关序列的副本替换每个指针。 该算法完成了齐夫和伦佩尔的既定目标。它证明，无需预处理的普遍最优无损压缩是可以实现的。 “在他们发表研究成果时，这种算法简洁明了、易于实现且计算复杂度较低的优点其实几乎都无关紧要了。”斯坦福大学从事信息理论研究的电气工程学教授查希•维斯曼（Tsachy Weissman）说，“更重要的是理论结果。” 不过，维斯曼说，研究人员最终承认了这种压缩算法的实际意义。“我们的技术开始处理超过10万甚至100万字符的更大的文件时，算法本身真的非常有用。” “他们的故事是一个关于基础理论研究的力量的故事。”维斯曼补充说，“你可以设立一个理论结果，说明什么应该是可以实现的，几十年后，人类将因执行了以这些结果为基础的算法而获益。” 齐夫和伦佩尔继续研究这项技术，试图让小数据文件更接近熵。他们的努力推动了LZ78的诞生。齐夫说，LZ78看起来和LZ77很相似，但实际上大有不同，因为它可以预测下一个数据位。“假设第一个数据位是1，那么你会在字典中输入两个代码，1-1和1-0，”他解释说，“你可以把这两个序列想象成一棵树的第一组分枝。” 齐夫说：“当第二个数据位出现时，如果是1，你就把指针指向第一个代码1-1，如果是0，你就指向另一个代码1-0。然后就可以通过向这棵树的选定分枝再添加两个可能性来扩展字典。重复执行这个操作，出现频率更高的序列将长出更长的分枝。” “事实证明，”他说，“这不仅是最佳（方法），而且非常简单，马上就变得有用了。” 齐夫和伦佩尔在开发LZ78时都在停教休假，不在以色列理工学院，而是在美国公司工作。他们知道他们的算法将在商业上大放光彩，所以想申请专利。 “我当时在贝尔实验室，”齐夫回忆道，“所以我以为专利应该属于他们。但他们说，除非是硬件，否则不可能获得专利，而且他们也没有兴趣尝试。”（美国最高法院直到20世纪80年代才向软件直接专利保护敞开了大门。） 不过，伦佩尔的雇主斯佩里兰德公司（Sperry Rand Corp.）愿意尝试。它绕过了软件专利的限制，开发了执行该算法的硬件，并为该设备申请了专利。紧随第一项专利之后，斯佩里兰德推出了一个由研究员特里•韦尔奇（Terry Welch）改编的版本，称为LZW算法。LZW版本传播最为广泛。 不能直接为LZ78申请专利，齐夫感到很遗憾，但他说：“我们很高兴（LZW算法）非常受欢迎。它使我们成名，我们也很喜欢它带来的研究。” 随之也产生了一个概念，称为“伦佩尔-齐夫复杂度”，它衡量的是一个数据位序列中包含的唯一子串的数量。唯一子串越少，序列就越可以被进一步压缩。 该方法后来被用于检查加密代码的安全性；如果一个代码真的是随机代码，它就不能被压缩。伦佩尔-齐夫复杂度也被用于分析脑电活动的脑电图记录，以确定麻醉深度、诊断抑郁症以及其他用途。研究人员甚至用它来分析流行歌词，确定重复的趋势。 在齐夫的职业生涯中，他发表了大约100篇同行评议论文。虽然1977年和1978年的论文最为出名，但齐夫之后的信息理论家们也有自己最爱的论文。 以色列理工学院的著名教授什洛莫•沙迈（Shlomo Shamai）最喜欢的是齐夫1976年的一篇论文，论文介绍了怀纳-齐夫算法，这是一种描述解码器而不是编码器的可用补充信息的使用限制的方法。比如，有的视频应用利用了解码器已破译前一帧画面的事实，其中就会出现这个问题，因此可以将其用作编码下一帧的边信息。 普林斯顿大学电气工程学教授文森特•普尔（Vincent Poor）最喜欢的是齐夫1969年的一篇论文，论文介绍了齐夫-扎凯界限，这是一种确定信号处理器是否能从给定信号中获得最准确信息的方法。 齐夫于1985年之前在以色列理工学院教授的课程也启发了许多一流数据压缩专家。维斯曼曾是其中一名学生，他说齐夫“充满了激情，醉心于把压缩作为量化信息的一种方式所体现的数学之美。1999年我上过他的课，这对我走上自己的研究道路产生了很大影响。” 他不是唯一深受启发的人。“1979年开始硕士研究学习的时候，我上了一门齐夫的信息理论课，”沙迈说，“40多年过去了，我仍然记得那门课。它让我渴望了解这些问题，进行研究，并攻读博士学位深造。” 近年来，青光眼夺走了齐夫的大部分视力。他说，今年1月在《IEEE信息理论学报》上发表的论文是他的最后一篇论文。他已89岁高龄了。 “两年半前我开始写这篇论文，那时以我的视力还可以用电脑，”他说，“最后，以色列理工学院的年轻教员尤瓦尔•卡苏托（Yuval Cassuto）完成了这个项目。”这篇论文讨论了在哪些情况下，需要将大型信息文件快速传输到远程数据库。 正如齐夫解释的那样，当医生想要将一位患者的DNA样本和该患者过去的样本进行比较以确定是否发生突变时，或是与一个DNA库进行比较以确定患者是否有遗传病时，就可能产生这样的需求。或者一种新病毒的研究人员可能想将其DNA序列与已知病毒的DNA数据库进行比较，也可以应用这种技术。 “问题是，DNA样本中的信息量巨大，”齐夫说，“大到今天的网络花几个小时甚至几天都无法发送。比如说，你正试图识别那些变化很快的病毒，花费的时间可能会很多。” 他和卡苏托描述的方法会使用数据库里常见的已知序列来帮助压缩新数据，而不会首先检查新数据和已知序列之间有没有特定匹配。 “我真的希望这项研究能在将来得到应用。”齐夫说。如果说他的成就簿还有任何新增内容，也许卡苏托-齐夫或者CZ21将为他的遗产添砖加瓦。 |
