理解 zip 和 gzip 压缩格式背后的压缩算法 _压缩算法

文章插图

众所周知，通过网络上传或者下载数据的每一个字节都是要花流量的，即需要花钱的。尽管现存的压缩算法已经有几十上百种，但其中最流行的压缩算法可能还是 zip 。gzip 压缩算法虽然和 zip 有着相似的名字，但却是另一种不同的算法。gzip 算法应用也相当广泛，它被 HTTP 三种标准压缩规范之一（译者注：属于端到端压缩技术，参见 HTTP 协议中的数据压缩）所采用。虽然各种压缩算法适用于不同场景，但是它们的底层都是基于 DEFLATE 。 DEFLATE是同时使用了 LZ77 算法与哈夫曼编码（Huffman Coding）的一种无损数据压缩算法。
LZ77DEFLATE基于 LZ77 算法——这是一种用于文本压缩的无损压缩技术。
压缩LZ77算法通过使用编码器或者解码器中已经出现过的相应匹配数据信息替换当前数据从而实现压缩功能。
此算法并非同时在整个文本中查找重复的字母，一般会先设定一个固定大小的搜索缓冲区，例如 20（在真实场景中，这个缓冲区的大小一般是几十 kB ）。接着在逐一对文本中字母进行编码时，首先会判断当前字母是否有出现在前面缓冲区的 20 个字母中。如果能找到匹配的字母，就记录下当前字母与找到的字母的偏移量 d ，这样就完成了一个字母编码的第一阶段。接来下，用当前在编码字母邻近的下一个字母与缓冲区中匹配上字母邻近的下一字母进行匹配，如果匹配上就继续进行下一个字母的匹配，如此循环往复直到缓冲区 20 个字母匹配完或者邻近的字母未匹配上，就结束匹配过程。结束上述过程后，将当前位置匹配上的连续字母替换成与缓冲区字母的偏移量以及这段连续字母的个数 l。这样，字母编码的第二阶段就完成了。
让我们用这个例子来看看它是如何工作的:
ERTOORTORR首先能想到的最简单做法就是直接替换第二次出现的 O 为指向第一次出现的 O 的一个标记，或者替换第二次出现的 RTO 为指向第一次出现的 RTO。
下面更具体地描述一下这个过程，假定我们设置的缓冲区大小是 4，把这 4 个长度的缓冲区看成是一个滑动窗口沿着正文文本向右滑动：

1) [....E]RTOORTORR2) [...ER]TOORTORR3) [..ERT]OORTORR4) [.ERTO]ORTORR5) [ERTOO]RTORR -> ERTO(1, 1)RTOORR6) E[RTOOR]TORR -> ERTO(1, 1)(4, 3)RR7) ERTO[ORTOR]R -> ERTO(1, 1)(4, 3)(3, 1)R8) ERTOO[RTORR] -> ERTO(1, 1)(4, 3)(3, 1)(1, 1)

滑动窗口随着随着编码的迭代一步步向右移动，前面 4 步中滑动窗口内的字母都没有发现重复。到了第 5 步，滑动窗口内字母 O 已经出现重复了，然后查看字母 O 右侧的 R 发现在滑动窗口中匹配字母 O 右侧相邻的字母并非 R ，便不再继续向右进行匹配，将第 2 个 O 替换成 (1, 1) （表示：滑动窗口中匹配的字母离当前字母偏移距离为 1，匹配上的连续字母长度为 1）。在第 6 步中，滑动窗口中字母 R 与其左边第 4 个字母匹配上了，继续检查下一个字母 T 的匹配情况，然后发现滑动窗口中 RT 也匹配上了。然后继续下一个字母 O ，在滑动窗口中匹配 RTO 也匹配上了，并且到此为止，因为下一个字母匹配上了。滑动窗口中匹配上的字母与当前字母的偏移距离为 4，同时有连续 3 个字母匹配上了，所以这里将匹配上的 3 个字母替换成 (4, 3)。接着在第 7 步中，字母 R 与偏移距离 3 出的字母匹配上，但是接下来的 RR 并未匹配上，在第 8 步中发现最近的匹配上的 R 的偏移距离为 1 。最终整段文本经过编码的结果如下：
ERTO(1, 1)(4, 3)(3, 1)(1, 1)解压压缩过的文本其实是由一系列的这种 (d, 1) 标记对和字母组成，标记对无法直接找到相匹配的字母。在解压过程中，字母保持不变，这种标记对转换为其指向位置的字母。下面看一个解压的例子：
abc(3, 2)(1, 1)字母 abc 保持不变，标记对 (3, 2) 表示从当前位置向左移动 3 个单位，然后取出 2 个字母，因此其转换为 ab。现在原始文本变成了这样 abcab(1, 1) ，最后的一个标记对表示从当前位置向左移动 1 个单位，然后取出 1 个字母，因此转换为 b。最终解压完成的文本为 abcabb。
哈夫曼编码在用 LZ77 消除了文本中重复的字母后，再使用哈夫曼编码进行第二次压缩。这种方法用较短的编码代替较常用的字母，用较长的编码代替较少用的字母，从而减少了文本的总长度。
让我们用一个简单的示例文本来看看它是如何工作的。