作为普通人，你在浏览网页的时候，你并不会意识到，服务器发给你的网页，其实都是压缩过的。
如果你像程序员一样，在浏览器中按一下F12，就能找到这样的东西：
它的意思是：为了节省带宽提供网速，我（服务器）把内容用gzip做了压缩，你（浏览器）得解压缩一下才能看啊！
在HTTP压缩中，除了gzip之外，还有compress、deflate、br等算法，让人眼花缭乱。
但是，这些压缩算法，都有一个老祖宗：LZ算法。
LZ来自两个人的名称：Abraham Lempel，Jacob Ziv。
两个人于2023年相继去世，都很长寿，Lempel活了86岁，Ziv一个活了91岁。
01
起源
数据压缩分为两种，一种是有损压缩，如MP3、JPEG，一些不重要的数据在压缩时会被删除。
另外一种是无损压缩，二进制位神奇的消失，文件显著变小，方便存储和传输。
1948年，香农创立了信息论以后，大家一直在折腾一件事情：如何找到最优编码，压缩一段信息。
香农和法诺率先出手，提出了香农-法诺编码。
它通过符号分组的方式，自顶向下构建了一个二叉树。
但是这种方式不是最优解，并且编码不是前缀码，容易产生歧义。
法诺后来在麻省理工教信息论时，给学生们提出了一个挑战：要么参加期末考试，要么改进现有的数据压缩算法。
一个叫霍夫曼的研究生不喜欢考试，决定走后一条路。
霍夫曼并不知道，就连大名鼎鼎的香农也在这个问题上苦苦挣扎。他研究了几个月，开发了多种方法，都没有用。
就在他要放弃，把笔记扔到垃圾桶的那一刻，一个美妙而优雅的算法划过了他的脑海：按照字符出现的频率，从下往上构建二叉树，这就是著名的霍夫曼算法。
霍夫曼的算法被称为“最佳编码”，实现了两个目标：
(1) 任何一个字符编码，都不是其他字符编码的前缀。
(2) 信息编码的总长度最小。
霍夫曼算法虽然很好，但有个巨大的限制：需要先获得所有字符出现的概率，然后才能编码压缩，这在很多情况下是做不到的。
上世纪70年代，互联网出现以后，这个问题变得更为突出。
能不能实现一边读取数据，一边压缩？
02
突破
以色列理工学院的Ziv和Lempel一起向这一问题发起了挑战。
两人是很好的搭档，Ziv擅长统计学和信息论，Lempel则擅长布尔代数和计算机科学。
1977年，他们俩都来到了贝尔实验室做学术休假。
学术休假又称为“知识人才休假”，每工作几年就有一段很长的假期（比如半年），这段假期里想干什么就干什么，还是带薪的。
大佬们的学术休假很有意思，比如Unix发明人Ken Thomson在休假时就回到了母校伯克利，把Unix传播到了那里，启发Bill Joy等人开发了BSD。
Ziv和Lempel也是这样，他们到美国贝尔实验室去学术休假，在“休假”期间合作发表了一篇论文：《顺序数据压缩的通用算法》，提出了基于“滑动窗口”的算法，它不直接考虑字符频率，而是寻找重复的数据块（如字符串、字节序列等）并引用这些数据块之前出现的位置。
这算法就是LZ77，它适用于任何类型的数据，不需要做预处理（统计字符出现的概率），只需要一次遍历就可以实现极高的压缩比。
第二年，他们再接再厉，改进了LZ77，变成了LZ78，能够从压缩数据中完美实现数据解压重构，并且比以往的算法效率更高。
03
乱战
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的功能内置到了操作系统中，终结了一切。
04
结语
从LZ77开始，到LZW，compress，Deflate，gzip ...... 无损压缩算法不断地修修补补，逐渐形成了一个庞大的家族，但是无论怎么改，它们的原理和思想都和最早的LZ算法没什么差别。
这些算法帮助我们压缩图像，压缩文本，压缩互联网传输的内容，成为我们日常生活中不可或缺的一部分。
毫不夸张地说，LZ算法和它的子孙们已经统治了全世界。
全文完，如果觉得不错的话，点一个“在看”或者“赞”吧！
作者介绍：本文作者刘欣，著有畅销书《码农翻身》，《半小时漫画计算机》，前IBM架构师，领导过多个企业应用架构设计和开发工作；洞察技术本质，擅长用故事去讲解复杂技术。
- EOF -
推荐阅读点击标题可跳转
1、就删了个 printf，代码崩了！
2、Sora 的第一波受害者出现了！
3、李彦宏诚不欺我？全球首位 AI 程序员来了
4、谷歌：不建议未成年人接触 C++，太过危险
5、2024年，只有搞颜色的 P 站真正关心网站性能
关注「程序员的那些事」加星标，不错过圈内事
点赞和在看就是最大的支持❤️
继续阅读
阅读原文