犀牛的心

gzip压缩的LZ77算法和哈夫曼编码实现原理

元芳 -

前端在性能优化那块有提到过gzip，但是gzip 的实现原理只是简单提了一下是基于deflate的算法，使用的是LZ77 + huffman Code。今天就来详细的总结下原理，不过有些问题还是没搞清楚，什么问题后面再说。
在这之前有个问题要先说下，nginx 和 webpack 中都是能做 gzip 压缩的，那有什么区别呢？
web 服务器（nginx）在向客户端发送gzip文件的时候，会先在本地文件系统查找 .gz 的文件，如果没有，则会去生成一份。生成的时候肯定会占用cpu的资源，所以当请求量比较大的时候，会占用较多的cpu来生成gz文件。而 webpack 的 gzip 则是在编译阶段就生成，所以服务器不用再生成，可以达到减少cpu资源占用的目的。

LZ77

LZ77 这个算法是两个以色列的大神 Lempel 和 Ziv 于1977 年提出的，所以简称为LZ77。

LZ77原理：

压缩原理其实很简单，就是找出那些重复出现的字符串，然后用更短的符号代替， 从而达到缩短字符串的目的。比如 某个js文件出现了大量的 let 关键字，我们就可以用�前面 let 的坐标值代替。事实上， 只要保证对应关系，可以用任意字符代替那些重复出现的字符串。

如果一个文件的重复率越高，那么压缩率就越高；相反，如果一个文件毫无重复，那么就无法被压缩。

LZ77 压缩算法采用字典的方式进行压缩，把数据中一些可以组织成短语(最长字符)的字符加入字典，然后再有相同字符出现采用标记来代替字典中的短语，如此通过标记代替多数重复出现的方式以进行压缩。

关键词术语：

  • 前向缓冲区：每次读取数据的时候，先把一部分数据预载入前向缓冲区。为移入滑动窗口做准备，大小可以自己设定
  • 滑动窗口：一旦数据通过缓冲区，那么它将移动到滑动窗口中，并变成字典的一部分。滑动窗口的大小也可以自己设定的
  • 短语字典：从字符序列 S1...Sn，组成n个短语。比如字符(A,B,D)，可以组合的短语为 {(A)，(A,B)，(A,B,D)，(B)，(B,D)，(D)}，如果这些字符在滑动窗口里面，就可以记为当前的短语字典，因为滑动窗口不断的向前滑动，所以短语字典也是不断的变化。

LZ77的主要算法逻辑就是，先通过前向缓冲区预读数据，然后再向滑动窗口移入（滑动窗口有一定的长度），不断的寻找能与字典中短语匹配的最长短语，然后通过标记符标记。我们还以字符ABD为例子，看如下图:

目前从前向缓冲区中可以和滑动窗口中可以匹配的最长短语就是（A,B）,然后向前移动的时候再次遇到（A,B）的时候采用标记符代替。

压缩

当压缩数据的时候，前向缓冲区与移动窗口之间在做短语匹配的是后会存在2种情况:

  1. 找不到匹配时：将未匹配的符号编码成符号标记（多数都是字符本身）
  2. 找到匹配时:将其最长的匹配编码成短语标记。
  3. 短语标记包含三部分信息:（滑动窗口中的偏移量（从匹配开始的地方计算）、匹配中的符号个数、匹配结束后的前向缓冲区中的第一个符号）。

一旦把n个符号编码并生成响应的标记，就将这n个符号从滑动窗口的一端移出，并用前向缓冲区中同样数量的符号来代替它们，如此，滑动窗口中始终有最新的短语。

我们采用图例来看:

1、开始

2、滑动窗口中没有数据，所以没有匹配到短语，将字符A标记为A

3、滑动窗口中有A,没有从缓冲区中字符（BABC）中匹配到短语，依然把B标记为B

4、缓冲区字符（ABCB）在滑动窗口的位移6位置找到AB,成功匹配到短语AB,将AB编码为(6,2,C)

5、缓冲区字符（BABA）在滑动窗口位移4的位置匹配到短语BAB,将BAB编码为(4,3,A)

6、缓冲区字符（BCAD）在滑动窗口位移2的位置匹配到短语BC，将BC编码为（2,2,A）

7、缓冲区字符D,在滑动窗口中没有找到匹配短语，标记为D

8、缓冲区中没有数据进入了，结束

解压

解压类似于压缩的逆向过程，通过解码标记和保持滑动窗口中的符号来更新解压数据。

当解码字符标记:将标记编码成字符拷贝到滑动窗口中

解码短语标记:在滑动窗口中查找响应偏移量，同时找到指定长短的短语进行替换。

我们还是采用图例来看下:

1、开始

2、符号标记A解码

3、符号标记B解码

4、短语标记(6,2,C)解码

5、短语标记(4,3,A)解码

6、短语标记(2,2,A)解码

7、符号标记D解码

优缺点

大多数情况下LZ77压缩算法的压缩比相当高，当然了也和你选择滑动窗口大小，以及前向缓冲区大小，以及数据熵有关系。其压缩过程是比较耗时的，因为要花费很多时间寻找滑动窗口中的短语匹配，不过解压过程会很快，因为每个标记都明确告知在哪个位置可以读取了。

Huffman

哈夫曼设计了一个贪心算法来构造最优前缀码，被称为哈夫曼编码（Huffman code）， 其正确性证明依赖于贪心选择性质和最优子结构。哈夫曼编码可以很有效的压缩数据，具体压缩率依赖于数据本身的特性

这里我们先介绍几个概念：

  • 码字：每个字符可以用一个唯一的二进制串表示，这个二进制串称为这个字符的码字
  • 码字长度：这个二进制串的长度称为这个码字的码字长度
  • 定长编码：码字长度固定就是定长编码。
  • 变长编码：码字长度不同则为变长编码。

变长编码可以达到比定长编码好得多的压缩率，其思想是赋予高频字符（出现频率高的字符）短（码字长度较短）码字，赋予低频字符长码字。例如，我们 用 ASCII 字符编辑一个文本文档，不论字符在整个文档中出现的频率，每个字符都要占 用一个字节。如果我们使用变长编码的方式，每个字符因在整个文档中的出现频率不同导致码字长度不同，有的可能占用一个字节，而有的可能只占用一比特，这个时候，整 文档占用空间就会比较小了。当然，如果这个文本文档相当大，导致每个字符的出现频率基本相同，那么此时所谓变长编码在压缩方面的优势就基本不存在了（这点要十分明确，这是为什么压缩要分块的原因之一）

构造过程

哈夫曼编码会自底向上构造出一棵对应最优编码的二叉树，我们使用下面这个例子来说明哈夫曼树的构造过程

首先，我们已知在某个文本中有如下字符及其出现频率：

构造过程如下图所示：

  • 在一开始，每个字符都已经按照出现频率大小排好顺序
  • 在后续的步骤中，每次都将频率最低的两棵树合并，然后用合并后的结果再次排序（注意，排序不是目的，目的是找到这时出现频率最低的两项，以便下次合并。gzip 源码中并没有专门去“排序”，而是使用专门的数据结构把频率最低的两项找到即可）
  • 叶子节点用矩形表示，每个叶子节点包含一个字符及其频率。中间节点用圆圈表示，包含其孩子节点的频率之和。中间节点指向左孩子的边标记为 0， 指向右孩子的边标记为 1。一个字符的码字对应从根到其叶节点的路径上的边的标签序列
  • 图1为初始集合，有六个节点，每个节点对应一个字符；图2到图5为中间步骤， 图6为最终哈夫曼树。此时每个字符的编码都是前缀码

利用库中的优先级队列实现哈夫曼树，最后基于哈夫曼树最终实现文件压缩。

未搞清楚的问题，希望有知道的小伙伴帮我解惑：

  1. 文件中重复的内容可能相隔比较远，滑动窗口和前向缓冲区设置的大小没办法让他们同时出现，所以这种内容是不是没法压缩？
    如果字典集是整个文件的字典集（随滑动窗口递增），那搜索效率会不会变的很慢？如果文件很大，字典集会不会很占用内存资源？如果不是全部字典集，感觉很难做到平均70%的压缩率。（猜测应该是递增）
  2. 看资料说 png 图片无损压缩是用的LZ77 + Huffman，而压缩过的是不能再压缩了，那只要是 png 都是压缩过的吗？否则为什么gzip压缩不建议再给图片压缩？
  3. png 图片能有损压损吗？有损压缩是转图片格式吗（PNG 8、PNG 24、PNG 32）？因为以前 png 压缩是用的browser-image-compression，简单看了下挺复杂，没看懂原理，I'am so vegetable。
  4. jpeg 用的canvas 的 toDataUrl('image/png',quality)来处理的，输出base64（关于base64，再写一篇文章单独介绍，因为base64会变大33%），属于有损压缩，quality用来控制色差的力度，值越小力度越大，颜色相差较大的两个像素也会被处理，自然被压缩后文件就越小，画质就越烂。简单来说，通过算法减少一张图片上的颜色差异，牺牲图片画质。比如紧挨着的颜色相近的四个像素的颜色信息压缩前大概占16个字节，压缩后变成一个颜色就能减少近4倍。所以toDataUrl是基于DCT（即离散余弦变换是与傅里叶变换相关的一种变换）实现的吗?
  5. jpeg 无损压缩是基于空间DPCM的无损压缩，即采用预测法和哈夫曼编码，既然没有用LZ77，为啥gzip没法再压缩了？

参考：
数据流压缩原理（Deflate压缩算法、gzip、zlib）
图解LZ77压缩算法
图片压缩知识梳理(1) - PNG 原理
PNG图片压缩原理--屌丝的眼泪
常用图片的构造及其压缩原理