两个老头儿写的神奇算法，统治了全世界！

作为普通人，你在浏览网页的时候，你并不会意识到，服务器发给你的网页，其实都是压缩过的。

如果你像程序员一样，在浏览器中按一下F12，就能找到这样的东西：

它的意思是：为了节省带宽提供网速，我（服务器）把内容用gzip做了压缩，你（浏览器）得解压缩一下才能看啊！

在HTTP压缩中，除了gzip之外，还有compress、deflate、br等算法，让人眼花缭乱。

但是，这些压缩算法，都有一个老祖宗：LZ算法。

LZ来自两个人的名称：Abraham Lempel，Jacob Ziv。

两个人于2023年相继去世，都很长寿，Lempel活了86岁，Ziv一个活了91岁。

数据压缩分为两种，一种是有损压缩，如MP3、JPEG，一些不重要的数据在压缩时会被删除。

另外一种是无损压缩，二进制位神奇的消失，文件显著变小，方便存储和传输。

1948年，香农创立了信息论以后，大家一直在折腾一件事情：如何找到最优编码，压缩一段信息。

香农和法诺率先出手，提出了香农-法诺编码。

它通过符号分组的方式，自顶向下构建了一个二叉树。

但是这种方式不是最优解，并且编码不是前缀码，容易产生歧义。

法诺后来在麻省理工教信息论时，给学生们提出了一个挑战：要么参加期末考试，要么改进现有的数据压缩算法。

一个叫霍夫曼的研究生不喜欢考试，决定走后一条路。

霍夫曼并不知道，就连大名鼎鼎的香农也在这个问题上苦苦挣扎。他研究了几个月，开发了多种方法，都没有用。

就在他要放弃，把笔记扔到垃圾桶的那一刻，一个美妙而优雅的算法划过了他的脑海：按照字符出现的频率，从下往上构建二叉树，这就是著名的霍夫曼算法。

霍夫曼的算法被称为“最佳编码”，实现了两个目标：

(1) 任何一个字符编码，都不是其他字符编码的前缀。

(2) 信息编码的总长度最小。

霍夫曼算法虽然很好，但有个巨大的限制：需要先获得所有字符出现的概率，然后才能编码压缩，这在很多情况下是做不到的。

上世纪70年代，互联网出现以后，这个问题变得更为突出。

能不能实现一边读取数据，一边压缩？

以色列理工学院的Ziv和Lempel一起向这一问题发起了挑战。

两人是很好的搭档，Ziv擅长统计学和信息论，Lempel则擅长布尔代数和计算机科学。

1977年，他们俩都来到了贝尔实验室做学术休假。

学术休假又称为“知识人才休假”，每工作几年就有一段很长的假期（比如半年），这段假期里想干什么就干什么，还是带薪的。

大佬们的学术休假很有意思，比如Unix发明人Ken Thomson在休假时就回到了母校伯克利，把Unix传播到了那里，启发Bill Joy等人开发了BSD。

Ziv和Lempel也是这样，他们到美国贝尔实验室去学术休假，在“休假”期间合作发表了一篇论文：《顺序数据压缩的通用算法》，提出了基于“滑动窗口”的算法，它不直接考虑字符频率，而是寻找重复的数据块（如字符串、字节序列等）并引用这些数据块之前出现的位置。

这算法就是LZ77，它适用于任何类型的数据，不需要做预处理（统计字符出现的概率），只需要一次遍历就可以实现极高的压缩比。

第二年，他们再接再厉，改进了LZ77，变成了LZ78，能够从压缩数据中完美实现数据解压重构，并且比以往的算法效率更高。

LZ算法这样的宝贝，居然停留在理论界好几年，没有大规模使用。

直到1984年，DEC公司的Terry  Welch在LZ基础上，创造了LZW算法，用到了Unix的compress程序中。

伴随着Unix的广泛传播，LZ算法开始进入飞速发展的快车道。

但是，也进入了群雄并启的乱战时代。

1985年，Thom Henderson在BBS下载文件时，发现总得一个一个地下载，拨号上网太慢了，于是他写了一个叫做ARC的软件，可以将多个文件压缩成一个，这就方便多了。

1986年，Phillip  Katz发现了ARC，喜欢的同时又觉得这玩意儿压缩速度太慢，于是就卷起袖子把关键的压缩和解压缩用汇编重写，形成了PKARC，开始卖钱。

Thom Henderson看到自己的生意被抢，一气之下把Phillip  Katz告上法庭，理由很充分：你PKARC中的注释、拼写错误都和我的ARC一样，你这是在抄袭！还有，我的ARC虽然是开源的，但是协议规定只能看，不能改！

最终ARC胜诉，Phillip  Katz赔了几万美元。

天才Phillip  Katz当然不服，他研究了LZ77算法和Huffman算法，将二者结合，创造了新的压缩算法(deflate)和新的文件格式(zip)，以及新软件PKZIP。

PKZIP无论是在压缩比，还是在解压缩速度上都把ARC打得找不着北，迅速统治了DOS时代。

由于ZIP格式是公开的，开源界info-zip小组也发布了开源、免费的unzip和zip，实现了deflate算法。

随后，Jean-loup Gailly和 Mark Adler基于deflate又开发了著名的gzip（文件格式+实用程序），替换了Unix上的compress。

gzip就是在文章开头看到的那个HTTP压缩格式。

1991年，Nico Mak 觉得PKZIP的命令行实在是不爽，他就基于PKZIP开发了一个Winodws3.1的前端（后来用开源的info-zip替换了PKZIP），让大家可以用图形界面的方式来压缩文件，这就是著名的WinZip。

用户发现WinZip界面精美，操作友好，根本不用记忆那些烦人的参数，点几下鼠标就完成压缩了。

WinZip迅速占据了所有的PC，成为成为90年代最流行的共享软件之一。

不过WinZip再辉煌，毕竟是“寄生”在Windows平台上。

Windows出手，干脆把Zip的功能内置到了操作系统中，终结了一切。

从LZ77开始，到LZW，compress，Deflate，gzip ...... 无损压缩算法不断地修修补补，逐渐形成了一个庞大的家族，但是无论怎么改，它们的原理和思想都和最早的LZ算法没什么差别。

这些算法帮助我们压缩图像，压缩文本，压缩互联网传输的内容，成为我们日常生活中不可或缺的一部分。

毫不夸张地说，LZ算法和它的子孙们已经统治了全世界。

作者介绍：本文作者刘欣，著有畅销书《码农翻身》，《半小时漫画计算机》，前IBM架构师，领导过多个企业应用架构设计和开发工作；洞察技术本质，擅长用故事去讲解复杂技术。

- EOF -

关注「程序员的那些事」加星标，不错过圈内事

点赞和在看就是最大的支持❤️