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为例子,看如下图:

image

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

压缩

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

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

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

我们采用图例来看:

1、开始
image

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

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

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

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

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

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

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

解压

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

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

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

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

1、开始
image

2、符号标记A解码
image

3、符号标记B解码
image

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

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

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

7、符号标记D解码
image

优缺点

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

Huffman

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

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

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

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

构造过程

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

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

构造过程如下图所示:

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

image

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

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

  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图片压缩原理--屌丝的眼泪
常用图片的构造及其压缩原理