HTTP请求之gzip压缩知多少( 二 ) _gzip压缩

文章插图

那么解压过程呢？其实解压过程是非常快速的，如下：

文章插图

可以看出， LZ77算法的耗时，主要在于压缩阶段中，判断前向缓冲区和滑动窗口中的最长字符串匹配，也就是说，选择滑动窗口大小，以及前向缓冲区大小，对你的LZ77算法的时间复杂度有着关键的影响，其次，合适的滑动窗口大小、缓冲区大小能帮助你对文件进行更好的压缩，提高压缩率。
而在整个解压的过程，只需要通过简单的字符读取，根据偏移量复用子字符串，就完成了解压过程，整个过程没有复杂的算法耗时，这也正符合了我们在网络请求中的适用场景，通过在服务端对文件的一次压缩，提供给所有的用户使用，在客户端对数据进行解压，而解压基本没有什么耗时，因此能大大提高我们的页面资源加载速度。
2、huffman编码当你对文件中的文本进行压缩后，接下来其实就是文本的存储了， ASCII编码中，一个字符对应一个字节，通过8位来表示，但是我们真的不能在优化了吗？huffman编码告诉我们，我们还能再压缩！huffman的原理，本质是通过判断字符在文本中的出现频次，规定每个字符的编码，而非固定8位编码，举个简单的栗子：
字符串：AAABCB
按照以往的存储方式需要6个字节， 48bits 。
但是我们可以看到， A出现了3次， B出现了2次， C仅仅出现了1次，于是我们换一种存储方式，
用0来表示A ， 10来表示B ， 11来表示C
最后的压缩结果是000101110 ，最后我们只用了9个bits来存储了这个字符串！
这就是huffman的根本原理。
可以看到我们的关键在于，为字符生成相应的编码，所以这个过程需要我们构造一个哈弗曼树，什么是哈夫曼树呢？哈弗曼树是通过一系列值，将这些值作为叶子节点，注意是叶子节点，构造成一个树，这个树要求，（叶子节点的权重叶子节点的深度）所有叶子节点总数n 的值达到最小。具体的构造过程如下：（图片引自 http://www.360doc.com/content... ）

文章插图

其中，节点值表示字符出现的频次，叶子节点的层级变相意味着字符编码的长度，其实这也很好理解，我们希望出现频次越多的字符，编码越短越好，频次较少的字符，编码长度较长也无所谓。这也和哈夫曼树的定义完美契合。
可以看到字符串：
abbbbccccddde
a b c d e
1 4 4 3 1
经过我们的huffman编码后，分别表示如下：
a 为 110
b 为 00
c 为 01
d 为 10
e 为 111
聪明的你可能还留意到了，通过huffman编码后的二进制字符，是没有二义性的。
可以看到我们上述的案例，动态生成了huffman编码，所以最后传输数据的时候，还需要把huffman树的信息一起传递过去，当然，这里还存在静态huffman和动态huffman的区别：
静态Huffman编码就是使用gzip自己预先定义好了一套编码进行压缩，解压缩的时候也使用这套编码，这样不需要传递用来生成树的信息。
动态Huffman编码就是使用统计好的各个符号的出现次数，建立Huffman树，产生各个符号的Huffman编码，用这产生的Huffman编码进行压缩，这样需要传递生成树的信息。
Gzip 在为一块进行Huffman编码之前，会同时建立静态Huffman树，和动态Huffman树，然后根据要输出的内容和生成的Huffman树，计算使用静态Huffman树编码，生成的块的大小，以及计算使用动态Huffman树编码，生成块的大小。然后进行比较，使用生成块较小的方法进行Huffman编码。