1. 压缩原理deflate算法

压缩的本质就是去冗余，去除信息冗余，使用最短的编码保存最完整的数据信息。所以对于不同的场景，压缩采用的算法也因时制宜，比如视频和图片可以采用有损压缩，而文本数据采用无损压缩。压缩率又取决于信息的冗余度，也就是内容中重复的比例。那些均匀分布的随机字符串，压缩率会降到最低，即香农限

1.1 Deflate压缩算法

deflate的概念

deflate是zip文件的默认算法。它更是一种数据流压缩算法。

deflate的三种压缩模型

• 不压缩数据
• 压缩，先用LZ77，再用huffman编码。压缩树是被Deflate规范定义的，不需要额外的空间存储这个树
• 压缩，采用LZ，然后使用huffman算法。压缩树是压缩器生成的，并与数据一起存储。

数据被分割成不同的块，每一个不同的块使用的单一的压缩模式。

1.2. LZ77算法原理

概念

LZ77压缩算法采用字典的方式进行压缩，是一种简单但是很高效的数据压缩算法。其方式就是把数据中一些可以组织成短语的字符加入字典。维护三个概念：短语字典、滑动窗口、向前缓冲区

• 前向缓冲区：数据预载入
• 滑动窗口：一个定长的用于处理当前数据的窗口
• 短语字典：用窗口去更新字典，并去匹配前向缓冲区的数据
  算法逻辑：先通过前向缓冲区预读数据，然后再向滑动窗口移入，不断的寻找能与字典中短语匹配的最长短语，然后通过标记符标记

LZ77压缩

• 压缩数据的时候，前向缓冲区和滑动窗口之间做短语匹配会存在两种情况，找不到匹配时，将未匹配的符号编码成符号标记，反之编码即可。
• 短语标记包含滑动窗口的偏移量（匹配开始的地方计算）、匹配中的符号个数、匹配结束后的前向缓冲区中的第一个符号
• 匹配步骤：

1. 寻找当前窗口内字符串在前向缓冲区中有没有匹配项，没有继续推进窗口和预读区
2. 如果有匹配项，使用三元组标记当前字符串，并向前移动匹配的符号个数+1位
3. 继续在窗口中寻找匹配项（注意滑动窗口中寻找匹配字串，预设窗口中寻找截止位），回到1
4. 重复直至匹配完毕

LZ77解压

压缩的逆过程，通过解码标记和保持滑动窗口中的符号来更新解压数据。当解码字符被标记:将标记编码成字符拷贝到滑动窗口中，一步一步直到全部翻译完成

• 优缺点：大多数情况下压缩比比较高，和你选择的各种参数配置以及数据的熵有关。压缩过程较为耗时，解压过程较快。

deflate采用的改进版LZ77算法

• 三个字节以上的重复串才进行编码。

为什么是三个字节？
这是由于，gzip中 <len,offset>标记的长度是23位长，如果重复长度小于这个值则压缩失效

• 原始数据被转换成长度距离标记后，再由huffman编码表示。这过程中，首先生成编码表（Huffman编码的对应关系），具体压缩大小在于精细分配结构体的位域。
• 解压：读取二进制文件，构建huffman表，根据表生成字符串，用LZ77解码。

1.3. Huffman算法原理

前缀码

在流式传输中，不定长编码数据的解码想要保持唯一性，必须满足唯一可以码的条件。而异前缀码就是一种唯一可译码的候选，当然这样会增加编码的长度，却可以简化解码。

哈夫曼编码

huffman编码是一种基于概率分布的贪心策略最优前缀码。huffman编码可以有效的压缩数据，压缩率取决于数据本身的信息冗余度

策略

计算数据中各符号出现的概率，根据概率从小到大，从下往上反向构建构造码树，这样最终得到的编码的平均长度是最短的。同时也是唯一可译的

1.4. huffman算法实例测试

算法举例

image.png

解读：在一开始，每一个字符已经按照出现概率的大小排好顺序，在后续的步骤中，每一次将概率最低的两棵树合并，然后用合并后的结果再次排序（为了找出最小的两棵树）。在gzip源码中并没有专门去排序，而是使用专门的数据结构（比如最小堆或者红黑树）。

编码实现

使用优先队列实现huffman树，最后基于Huffman树最终实现文件压缩。
具体步骤：

• 统计文件中符号个数
• 持久化文件字符信息（个数）
• 压缩
• 解压缩

2.gzip的格式分析

gzip = gzip 头 + deflate 编码的实际内容 + gzip 尾

3. zlib库函数API分析

zlib = zlib 头 + deflate 编码的实际内容 + zlib 尾

zlib库API分析

基本数据结构

typedef struct gz_header_s{
  int text;/* true if compressed data believed to be text*/
  uLong time; /* modification time*/
  int xflags;/* extra flags*/
  int os; /* operating system*/
  Bytef *extra;/* pointer to extra field or Z_NULL if none*/
  uInt extra_len;/* extra field length*/
  uInt extra_max;
  Bytef *name;
  uInt name_max;
  Bytef *comment;
  uInt comm_max;
  int hcrc;
  int done;
}

压缩之前：初始化各种输入输出缓冲区；
压缩：我们可以不断往这些缓冲区中填充内容，然后由deflate函数进行压缩或者indeflate函数进行解压

• deflate尽可能的压缩数据，当输入缓冲区为空或者输出缓冲区满了的时候会停止，它会带来输出延迟，除非强行刷新缓冲区
• deflate的语义如下：

1. 从next_in开始压缩数据从而更新next_in和avail_in.如果不是所有数据都可以被处理，next_in和avail_in会更新，当再次调用deflate函数的时候会从这一点继续处理

2. 从next_out开始提供更多输出数据从而更新next_out和avail_out,如果flush参数不为零，则这个动作是强制性的，经常性的刷新会降低压缩比例，所以只有必要的时候才会设置这个参数。

   
   image.png

总结：在调用deflate函数之前，应用程序必须保证至少一个动作被执行（avail_in或者avail_out被设置），用提供更多数据或者消耗更多的数据的方式。avail_out在函数调用之前千万不能为零。应用程序可以随时消耗被压缩的输出数据

4. zlib库实战(压缩文件和解压文件)