深入理解gzip原理

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

LZ77算法的压缩原理

如果文件中有两块内容相同的话,那么只要知道前一块的位置和大小,我们就可以确定后一块的内容。所以我们可以用(两者之间的距离,相同内容的长度)这样一对信息,来替换后一块内容。由于(两者之间的距离,相同内容的长度)这一对信息的大小,小于被替换内容的大小,所以文件得到了压缩。

举一个例子

有一个文件的内容如下
http://jiurl.yeah.net http://jiurl.nease.net

其中有些部分的内容,前面已经出现过了,下面用()括起来的部分就是相同的部分。
http://jiurl.yeah.net (http://jiurl.)nease(.net)
我们使用 (两者之间的距离,相同内容的长度) 这样一对信息,来替换后一块内容。(22,13)中,22为相同内容块与当前位置之间的距离,13为相同内容的长度。(23,4)中,23为相同内容块与当前位置之间的距离,4为相同内容的长度。由于(两者之间的距离,相同内容的长度)这一对信息的大小,小于被替换内容的大小,所以文件得到了压缩。

LZ77算法使用"滑动窗口"的方法,来寻找文件中的相同部分,也就是匹配串.

解压缩:
从文件开始到文件结束,每次先读一位标志位,通过这个标志位来判断下面是一个(之间的距离,匹配长度) 对,还是一个没有改动的字节。如果是一个(之间的距离,匹配长度)对,就读出固定位数的(之间的距离,匹配长度)对,然后根据对中的信息,将匹配串输出到当前位置。如果是一个没有改动的字节,就读出一个字节,然后输出这个字节。

LZ77压缩时需要做大量的匹配工作,而解压缩时需要做的工作很少,也就是说解压缩相对于压缩将快的多。这对于需要进行一次压缩,多次解压缩的情况,是一个巨大的优点。

深入理解
要理解这种算法,我们先了解3个关键词:短语字典,滑动窗口和向前缓冲区。
前向缓冲区
每次读取数据的时候,先把一部分数据预载入前向缓冲区。为移入滑动窗口做准备
滑动窗口
一旦数据通过缓冲区,那么它将移动到滑动窗口中,并变成字典的一部分。

短语字典
从字符序列S1...Sn,组成n个短语。比如字符(A,B,D) ,可以组合的短语为{(A),(A,B),(A,B,D),(B),(B,D),(D)},如果这些字符在滑动窗口里面,就可以记为当前的短语字典,因为滑动窗口不断的向前滑动,所以短语字典也是不断的变化。

LZ77的主要算法逻辑就是,先通过前向缓冲区预读数据,然后再向滑动窗口移入(滑动窗口有一定的长度),不断的寻找能与字典中短语匹配的最长短语,然后通过标记符标记。

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

  • 找不到匹配时:将未匹配的符号编码成符号标记(多数都是字符本身)
  • 找到匹配时:将其最长的匹配编码成短语标记。

短语标记包含三部分信息:(滑动窗口中的偏移量(从匹配开始的地方计算)、匹配中的符号个数、匹配结束后的前向缓冲区中的第一个符号)。

我们采用图例来看:

1、开始


image.png

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

image.png

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

image.png

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

image.png

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

image.png

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

image.png

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

image.png

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

image.png

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

  • 当解码字符标记:将标记编码成字符拷贝到滑动窗口中
  • 解码短语标记:在滑动窗口中查找响应偏移量,同时找到指定长短的短语进行替换

我们还是采用图例来看下:
1、开始


image.png

2、符号标记A解码

image.png

3、符号标记B解码


image.png

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

image.png

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

image.png

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

image.png

7、符号标记D解码

image.png

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

Huffman编码简介

哈夫曼树也叫最优二叉树(哈夫曼树)

问题:什么是哈夫曼树?

例:将学生的百分制成绩转换为五分制成绩:≥90 分: A,80~89分: B,70~79分: C,60~69分: D,<60分: E。

if (a < 60){
        b = 'E';
    }
    else if (a < 70) {
        b = ‘D’;
    }
    else if (a<80) {
        b = ‘C’;
    }
    else if (a<90){
        b = ‘B’;
    }
    else {
      b = ‘A’;
    }

判别树:用于描述分类过程的二叉树。


image.png

如果每次输入量都很大,那么应该考虑程序运行的时间

image.png

如果学生的总成绩数据有10000条,则5%的数据需 1 次比较,15%的数据需 2 次比较,40%的数据需 3 次比较,40%的数据需 4 次比较,因此 10000 个数据比较的

次数为: 10000 (5%+2×15%+3×40%+4×40%)=31500次

image.png

此种形状的二叉树,需要的比较次数是:10000 (3×20%+2×80%)=22000次,显然:两种判别树的效率是不一样的。

问题:能不能找到一种效率最高的判别树呢?

那就是哈夫曼树

树的带权路径长度:树中所有叶子结点的带权路径长度之和,通常记作:


image.png

其中,n表示叶子结点的数目,wi和li分别表示叶子结点ki的权值和树根结点到叶子结点ki之间的路径长度。
赫夫曼树(哈夫曼树,huffman树)定义:
在权为w1,w2,…,wn的n个叶子结点的所有二叉树中,带权路径长度WPL最小的二叉树称为赫夫曼树或最优二叉树。

例:有4 个结点 a, b, c, d,权值分别为 7, 5, 2, 4,试构造以此 4 个结点为叶子结点的二叉树。

image.png

WPL=7´2+5´2+2´2+4´2= 36

image.png

WPL=7´3+5´3+2´1+4´2= 46

哈夫曼树的构造(哈夫曼算法)
1.根据给定的n个权值{w1,w2,…,wn}构成二叉树集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树为空.
2.在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树根结点的权值之和.
3.在F中删除这两棵树,同时将新的二叉树加入F中.
4.重复2、3,直到F只含有一棵树为止.(得到哈夫曼树)

哈夫曼编码

哈夫曼树的应用很广,哈夫曼编码就是其在电讯通信中的应用之一。广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。在电讯通信业务中,通常用二进制编码来表示字母或其他字符,并用这样的编码来表示字符序列。

例:如果需传送的电文为 ‘ABACCDA’,它只用到四种字符,用两位二进制编码便可分辨。假设 A, B, C, D 的编码分别为 00, 01,10, 11,则上述电文便为 ‘00010010101100’(共 14 位),译码员按两位进行分组译码,便可恢复原来的电文。

能否使编码总长度更短呢?

实际应用中各字符的出现频度不相同,用短(长)编码表示频率大(小)的字符,使得编码序列的总长度最小,使所需总空间量最少

数据的最小冗余编码问题

在上例中,若假设 A, B, C, D 的编码分别为 0,00,1,01,则电文 ‘ABACCDA’ 便为 ‘000011010’(共 9 位),但此编码存在多义性:可译为: ‘BBCCDA’、‘ABACCDA’、‘AAAACCACA’ 等。

译码的惟一性问题

要求任一字符的编码都不能是另一字符编码的前缀,这种编码称为前缀编码(其实是非前缀码)。 在编码过程要考虑两个问题,数据的最小冗余编码问题,译码的惟一性问题,利用最优二叉树可以很好地解决上述两个问题

以电文中的字符作为叶子结点构造二叉树。然后将二叉树中结点引向其左孩子的分支标 ‘0’,引向其右孩子的分支标 ‘1’; 每个字符的编码即为从根到每个叶子的路径上得到的 0, 1 序列。如此得到的即为二进制前缀编码。

image.png

编码: A:0, C:10,B:110,D:111

任意一个叶子结点都不可能在其它叶子结点的路径中。

用哈夫曼树设计总长最短的二进制前缀编码

例:如果需传送的电文为 ‘ABACCDA’,即:A, B, C, D 的频率(即权值)分别为 0.43, 0.14, 0.29, 0.14,试构造哈夫曼编码。

image.png

编码: A:0, C:10, B:110, D:111 。电文 ‘ABACCDA’ 便为 ‘0110010101110’(共 13 位)。

译码
从哈夫曼树根开始,对待译码电文逐位取码。若编码是“0”,则向左走;若编码是“1”,则向右走,一旦到达叶子结点,则译出一个字符;再重新从根出发,直到电文结束。

image.png

电文为 “1101000” ,译文只能是“CAT”

推荐阅读更多精彩内容