我对数据压缩以及Zip文件格式的好奇已经不是一天两天了，后来我终于下定决心打算彻底把它搞明白然后写一个自己的Zip压缩程序。现在想想，这个实现过程还是相当有趣的：不管是什数据，要将它们的二进制组织成为一种更有效的表示形式，然后还要能恢复成原来的数据，实现这个功能的过程还要考虑怎么更好地设计程序和代码。庆幸的是，这些代码读起来也相当有趣。
本文详细解释了Zip文件格式以及各种压缩方案的工作原理：LZ77压缩、霍夫曼编码、Deflate等。本文还介绍一些历史，并用C语言从零实现了一个相当有效的压缩程序。源代码在hwzip-2.0.zip中。
我已经尽力保证代码中没有错误。如果您发现任何问题，请及时告诉我。
非常感谢 Ange Albertini, Gynvael Coldwind, Fabian Giesen, Jonas Skeppstedt (web), Primiano Tucci, 以及 Nico Weber ，他们对于这篇文章最终成型给予了我许多帮助。
历史
PKZip
早在80年代和90年代初，在Internet变得广泛可用之前，家庭计算机爱好者就使用拨号调制解调器通过电话网络连接到电子公告板(BBS)。BBS是一种交互式计算机系统，通常允许用户发送消息、玩游戏和共享文件。上网所需要的只是一台电脑、一个调制解调器和一个好的BBS号码，号码可以在计算机杂志和其他BBS发布的列表中找到。
存档器(Archiver，也叫归档器)是使文件分享变得更便捷的工具。存档器将一个或多个文件打包进一个文件，即存档文件(Archive)，它允许多个文件作为一个单元进行存储或传输，并且理想情况下还可以压缩它们以节省存储空间和传输时间。在BBS的使用场景中，一个流行存档器的是Arc，它是由System Enhancement Associates (SEA)的Thom Henderson编写，SEA是Thom Henderson与他的姐夫创立的一家小公司。
八十年代后期，一位名叫Phil Katz的程序员发布了他自己的Arc程序PKArc。它与SEA的Arc兼容，但由于是使用汇编编写因而速度更快，并且Katz在程序中添加了新的压缩方法。这个程序开始流行的时候，Katz辞去了工作，创立了PKWare并专注研发PKArc。据说，Katz大部分工作都是在他母亲厨房的餐桌上完成的。
Milwaukee Sentinel文章中的一张照片，Phil Katz，1994.9.19
然而，SEA并没有被Katz吓到，SEA对Katz提起商标和版权侵权的诉讼。在BBS和PC世界中的争议和与之有关的争论被称为Arc Wars。最后，这个案件的解决偏袒SEA一方。
从Arc开始，在1989年，Katz创建了一种新的存档格式Zip并将其贡献给公众使用:
邮件原文：The file format of the files created by these programs, which file format is original with the first release of this software, is hereby dedicated to the public domain. Further, the filename extension of ".ZIP", first used in connection with data compression software on the first release of this software, is also hereby dedicated to the public domain, with the fervent and sincere hope that it will not be attempted to be appropriated by anyone else for their exclusive use, but rather that it will be used to refer to data compression and librarying software in general, of a class or type which creates files having a format generally compatible with this software.
邮件译文：程序以及由程序所创建的文件格式均是原创，特此贡献给公众使用。文件名 后缀".ZIP"随着软件发布首次同文件压缩软件相关联，与此一并贡献给公众, 同时也 热烈和真诚地希望其不被任何人挪用以专用，而是将其用于指代数据压缩和软件打包一 般的类或类型，该类或类型的文件格式通常与该软件兼容。
Katz 用于创建此类文件的程序称为 PKZip，很快就被 BBS 和 PC 采用。
促使 Zip 格式成功的一个非常重要的原因可能是因为 PKZip 附带了一份说明文档，即 Application Note，它准确地解释了该格式的工作原理。这允许其他人研究该格式并创建程序以创建、提取或以其他方式与 Zip 文件交互。
Zip 是一种无损（lossless） 压缩格式: 解压缩之后的数据与压缩之前的数据相同。 它的工作原理是在源数据中查找冗余内容并用更有效地方式表示它。这与 JPEG 和 MP3 等图像和声音格式中使用的有损（lossy）压缩不同，后者通过从数据中删除人眼或耳朵等不易察觉的特征来实现压缩。
PKZip 作为共享软件分发：可以自由使用和复制，但也鼓励用户“注册（register）”该程序。只需 47 美元，即可获得印刷手册、高级支持和软件的增强版本。
对后来影响最大的 PKZip 版本是1992年12月28日发布的2.04c版本(紧随其后的是 2.04g 版本). Deflate方法作为这个版本中默认的压缩方法，并且定义了 Zip 文件压缩如何具体工作。 (从Boardwatch 文章中了解release信息。)
Zip 格式已被许多其他文件格式采用。例如，Java 档案（.jar 文件）和 Android 应用程序包 （.apk 文件）以及 Microsoft Office 的 .docx 文件都使用 Zip 格式。还有一些其他文件格式和协议使用 Zip 文件中的 Deflate 压缩算法。例如，此网页很可能作为 gzip 文件传输到您的 Web 浏览器，这是一种使用 Deflate 压缩算法的格式。
Phil Katz 于2000年去世。PKWare公司仍然存在，现在这家公司主要专注于数据安全类软件。
Info-ZIP 和 zlib
1989 年 PKZip 发布后不久，其他提取 Zip 文件的程序开始出现，特别是一个名为 unzip 的程序， 它可用于在 Unix 系统上提取 Zip 文件。在1990 年 3 月，一个名为 Info-ZIP 的邮件组被建立了。
Info-ZIP 组织发布了免费且开源的 unzip 和 zip 程序, 用于提取和创建 zip 文件。代码被移植到了许多系统上，直到现在它们 仍然是 Unix 系统上使用的标准 Zip 程序。这进一步提高了 Zip 文件的流行程度。
后来，Info-ZIP 中执行 Deflate 压缩以及解压缩的代码被提取到 zlib 库中，该库由Jean-loup Gailly（压缩）和Mark Adler（解压缩）编写。
2009年，Jean-loup Gailly (左) 和 Mark Adler (右) 获得 USENIX STUG Award 奖项
创建这个库的原因之一是这样可以方便其他应用程序或文件格式使用Deflate压缩方法，例如新的gzip 文件压缩格式以及 PNG 图像压缩格式. 提出这些新文件格式是为了取代使用受专利保护的 LZW 算法的Compress和GIF文件格式。
作为开发的一部分，L Peter Deutsch 编写了 Deflate 方法的规范，并于1996年5月作为Internet RFC 1951发布。这份提议提供了比原始 PKZip 说明文档更易于理解的描述。
在今天 zlib 早已无处不在。它可能负责在 Web 服务器上压缩此页面，并在您的 Web 浏览器中解压缩。 现在大多数 Zip 和 Zip 类文件的压缩和解压缩都是使用 zlib 完成的。
WinZip
许多没有使用 PKZip 的人应该会记得 WinZip。随着 PC 用户从 DOS 迁移到 Windows， 他们也从 PKZip 迁移到 WinZip。
它最初是由程序员 Nico Mak 发起的一个项目，他在康涅狄格州斯托尔斯的一家名为 Mansfield Software Group 的公司从事 OS/2 操作系统的软件开发。他使用 OS/2 中的图形用户界面 Presentation Manager，让他感到难过的是，每当他想 创建或提取 Zip 文件时必须从图形用户界面切换到 DOS 命令提示符。
于是，Mak 编写了一个简单的图形程序直接在 Presentation Manager 中管理 Zip 文件， 并将其命名为PMZip， 之后于 1990 年作为共享软件发布。
OS/2 并没有在真正意义上获得成功。在 PC 世界转向拥抱 Microsoft Window 之后， 1991年，Mak决定学习如何书写 Windows 程序，他的第一个项目就是将他的 Zip 程序移植到新的操作系统上。 1991年4月 WinZip 1.00 作为拥有21天试用期的共享软件发布，注册价格为29美元，它的界面像下面这个样子：
第一版 WinZip 中使用 PKZip 相关程序，但从 1993 年的 5.0 版开始，它使用来自 Info-ZIP 的代码直接管理 Zip 文件。从最初的简陋的用户界面演变为以下用户界面。
运行在 Windows 3.11（Workgroups）上的 WinZip 6.3 截图
WinZip 是 90 年代最流行的共享软件程序之一，但随着操作系统获得对 Zip 文件的内置支持，它最终变得不那么重要了。 自 Windows ME（或Windows 98以及Plus! 98）以来，Windows 使用名为 DynaZip 的库将 Zip 文件作为“压缩文件夹（compressed floders）”进行管理。 Windows 中这部分代码是由 Dave Plummer 编写，在微软收购它之前曾作为共享软件分发（关于这部分的故事，请查看 Dave 的视频）。
Mak 的公司原名为 Nico Mak Computing。2000 年，它更名为 WinZip Computing， 而 Mak 似乎在这个时候离开了。2005 年，该公司被 出售给 Vector Capital，最终归Corel所有， Corel仍将 WinZip 作为产品发布。
Lempel-Ziv Compression (LZ77)
Zip 压缩中有两个主要方法：Lempel-Ziv压缩和Huffman编码。本节介绍前者。
压缩文本的一种方法是维护一个常用词或或短语的列表，并用在字典中的引用替换文本中出现的这些词。例如， “compression”这个词可以用#1234表示，1234指的是这个词在列表（字典）中的位置。这种方法称为基于字典的压缩 （dictionary-based compression）。
在通用压缩目的中使用基于字典的压缩方法，就不得不考虑许多问题。首先，什么东西应该放到字典中？原始数据可能不是英文，甚至 可能不是人类可读的文本。并且如果压缩和解压缩事先没有约定一致的字典，则需要将字典与压缩数据一起存储和传输，这减少了基于 字典压缩方法的优势。
一种优雅的解决方式是使用原始数据本身作为字典。在他们1977年的论文 "A Universal Algorithm for Sequential Data Compression"中, Jacob Ziv 和 Abraham Lempel (均在以色列理工学院), 提出了一种将原始数据表示为三元组序列的压缩模式。
(pointer, length, next)
pointer 和 length 是对原文中前面位置的子字符串的反向引用， next 是下一个将要输出的字符。
Abraham Lempel (photo from Wikipedia, by Staelin, CC BY 3.0) and Jacob Ziv (photo from Wikipedia).
例如，考虑下面的文本片段。For example, consider the snippet below.
It was the best of times,
it was the worst of times,
第二行中的"t was the w"可以被表示为(26, 10, w), 因为它可以通过从后退26步的位置 拷贝10个字符后跟一个"w"重新生成。没有出现过的字符使用零长反向引用（zero-length back referednce）。例如，开头的"I"字符表示为(0, 0, I)。
这种压缩形式称为Lemple-Ziv或LZ77压缩。然而，现实世界的实现通常不使用三元组中的next部分， 而是直接输出单个字符，并且使用(distance, length) 来表示反向引用. (这种变体称为 LZSS 压缩) 数据和反向引用如何编码是一个单独的问题，我们将在后面Deflate部分讨论。
以下面的文本为例：
It was the best of times,
it was the worst of times,
it was the age of wisdom,
it was the age of foolishness,
it was the epoch of belief,
it was the epoch of incredulity,
it was the season of Light,
it was the season of Darkness,
it was the spring of hope,
it was the winter of despair,
we had everything before us,
we had nothing before us,
we were all going direct to Heaven,
we were all going direct the other way
可以压缩成
It was the best of times,
i(26,10)wor(27,24)age(25,4)wisdom(26,20)
foolishnes(57,14)epoch(33,4)belief (28,22)incredulity
(33,13)season(34,4)Light(28,23)Dark(120,17)
spring(31,4)hope(231,14)inter(27,4)despair,
we had everyth(57,4)before us(29,9)no(26,20)
we(12,3)all go(29,4)direct to Heaven
(36,28)(139,3)(83,3)(138,3)way
反向引用一个令人兴奋的地方是它可以与自身重叠（overlap），当二元组中的length大于distance时候就 会发生自身重叠。下面通过这个例子来说明：
Fa-la-la-la-la
可以被压缩成
Fa-la(3,9)
这看起来很奇怪，但却是有效的：一旦前三个"-la"字节完成复制，复制将继续使用最近输出的字节。
这实际上是一种游程编码(run-length encoding), 一段数据被重复复制直到达到指定长度。
参见Colin Morris的Are Pop Lyrics Getting More Repetitive? 这篇文章是使用Lemple-Ziv压缩歌词的交互性示例。
用C表示，反向引用可以像下面这样实现复制。注意，因为复制过程有可能发生自身重叠，因此不能使用memcpy 以及 memmove方法。
字面值的输出不那么重要，但是为了完整我们也提供一个函数。
注意，调用者应该保证dst 有足够的空间存放输出，并且反向引用不能引用到buffer开始之前的部分。
最难的部分不是解压时如何解析反向引用，而是压缩原始数据时如何找到他们。 这里有很多方法可以实现，但是我们将遵循zilb基于哈希表的方法，这也是RFC 1951所建议的。
有一个办法是维护"4字节"前缀的哈希值到其出现位置的哈希列表（再短的反向引用不被认为是有益的）。（译者注：哈希值作为索引，列表保存的是被哈希的内容在原始数据中所出现的位置）.对于 Deflate 方法，只允许反向引用最近窗口大小为 32,768 之内的字符。 这实际上是流式压缩（streaming compression）: 只要具有最新字节的窗口保留在内存中，我们就可以一点点处理输入数据。 本文中我们的实现假设所有的输入都是可以利用的，即窗口大小能够容纳全部数据，这样我们就可以从头到尾一遍处理完。 我们这里关注的重点是压缩本身而不是如何实现滑动窗口。
我们使用两个列表：head 列表映射四字节的哈希值到其在输入数据中出现的位置。 prev 列表通过位置找到具有相同哈希值的四字符上一次出现的位置。实际上, head[h] 是具有哈希值h的链表的头节点。prev[x] 从链表中获取在 x 之前出现的元素的位置。
为了将出现的字符串的位置插入到哈希表中，首先将prev更新为当前的头节点值，然后再将head进行更新：
注意这里在更新prev时候对pos进行的取模运算，因为我们只关心落在当前窗口大小中的数据。
一个简单的函数用于计算哈希值： (read32le 以小端顺序读取 32 位值，方法在 bits.h中实现)
建立好哈希表之后，我们就可以使用哈希映射有效地搜索具有子字符串的先前匹配项，如下所示。搜索匹配项是压缩中计算量最大的部分，因此我们限制了搜索潜在匹配项的后退距离（译者注，即代码中的max_match_steps，初始值为4096）。
更改传入的参数是一种用更少的压缩换取更快的速度的方法，例如使搜索的前缀列表向后距离更小（以及是否进行延迟匹配，将在下面进一步描述）。我们代码中的设置匹配了 zlib 的最大压缩级别。
有了查找先前匹配项的代码，我们就可以完成lz77_compress函数：
该代码查找在当前位置所能找到的最长反向引用。 但是，在输出该反向引用之前，也会考虑是否可以在下一个 位置找到更长的匹配项。zlib 将此称为延迟匹配评估（lazy match evaluation）。 这是一个贪心算法：它选择最长的匹配，因为考虑到稍后可能会有更长的匹配从而使总体上能够更好地压缩。
Lempel-Ziv 压缩可以快也可以慢。 Zopfli花费大量时间试图找到最佳的反向引用， 以提高压缩百分比。这对于压缩一次并多次使用的数据非常有用，例如 Web 服务器 上的静态内容。另一方面例如像Snappy 和LZ4压缩工具，它们与 4 字节前缀匹配保持一致并且运 行速度非常快。这种压缩在数据库或 RPC 系统 中很有用，在这些场景中，更快的压缩意味着更快地通过网络传递数据或从/往磁盘读取/写入。
Lempel-Ziv 使用源数据本身作为字典的想法非常优雅，但使用静态字典仍然是有许多好处的。 Brotli 是一种基于 LZ77 的压缩算法，但它也使用了由网络上经常出现的字符串组成的大型静态字典（static dictionary）。
{测试窝原创译文，译者：lukeaxu}
