Accept-Encoding之gzip压缩

​ HTTP 请求头 Accept-Encoding 会将客户端能够理解的内容编码方式——通常是某种压缩算法——进行通知(给服务端)。通过内容协商的方式,服务端会选择一个客户端提议的方式,使用并在响应头Content-Encoding 中通知客户端该选择。

​ 今天我们就来看一看最常见的gzip压缩方式

​ 压缩原理

gzip使用deflate算法进行压缩。具体就是将要压缩的文件先使用LZ77算法的一个变种进行压缩,对得到的结果再使用Huffman编码的方法进行压缩。

首先介绍下LZ77算法,如果文件中有两块相同的内容,那么只要知道前一块的位置和大小,我们就可以确定后一块的内容。所以我们可以利用两者之间的距离,内容的长度来替换后一块的内容,文件也就因此得到了压缩。重复内容越多,压缩率也越高。

压缩时,从文件的开始到文件的结束,一个字节一个字节的向后开始处理。用当前处理字节开始的串,和滑动窗口中的每个串进行匹配,寻找最长的匹配串。如果当前处理字节开始的串在窗口中有匹配串,就先输出一个标志位,表明下面是匹配对,并输出该匹配对,然后从刚才处理完的串之后的下一个字节急需处理。如果当前处理字节开始的串在窗口中没有匹配串,就先输出一个标志位,表明下面是一个没有改动的字节,然后不做改动地输出当前处理字节,之后继续处理当前处理字节的下一个字节。

解压缩时,从文件开始到文件结束,每次先读一个标志位,通过这个标志位来判断下面的匹配对。如果是一个队,就独处固定位数的对,然后将匹配串输出到当前位置。如果是一个没有改动的字节,就输出该字节即可。

相比压缩而言,解压缩时间消耗较少。

Huffman编码使用Huffman树来产生编码

要进行Huffman编码,首先要把整个文件读一遍,在读的过程中,统计每个符号(我们把字节的256种值看作是256种符号)的出现次数。然后根据符号的出现次数,建立Huffman树,通过Huffman树得到每个符号的新的编码。对于文件中出现次数较多的符号,它的Huffman编码的位数比较少。对于文件中出现次数较少的符号,它的Huffman编码的位数比较多。然后把文件中的每个字节替换成他们新的编码。

建立Huffman树:

把所有符号看成是一个结点,并且该结点的值为它的出现次数。进一步把这些结点看成是只有一个结点的树。

每次从所有树中找出值最小的两个树,为这两个树建立一个父结点,然后这两个树和它们的父结点组成一个新的树,这个新的树的值为它的两个子树的值的和。如此往复,直到最后所有的树变成了一棵树。我们就得到了一棵Huffman树。

通过Huffman树得到Huffman编码:

这棵Huffman树,是一棵二叉树,它的所有叶子结点就是所有的符号,它的中间结点是在产生Huffman树的过程中不断建立的。

我们在Huffman树的所有父结点到它的左子结点的路径上标上0,右子结点的路径上标上1。

现在我们从根节点开始,到所有叶子结点的路径,就是一个0和1的序列。我们用根结点到一个叶子结点路径上的0和1的序列,作为这个叶子结点的Huffman编码。

总结:

压缩:

读文件,统计每个符号的出现次数。根据每个符号的出现次数,建立Huffman树,得到每个符号的Huffman编码。将每个符号的出现次数的信息保存在压缩文件中,将文件中的每个符号替换成它的Huffman编码,并输出。

解压缩:

得到保存在压缩文件中的,每个符号的出现次数的信息。根据每个符号的出现次数,建立Huffman树,得到每个符号的Huffman编码。将压缩文件中的每个Huffman编码替换成它对应的符号,并输出。

你可能感兴趣的