聊聊字符集编码与数据压缩( 四 ) _数据压缩

码字:每个字符可以用一个唯一的二进制串表示，这个二进制串称为这个字符的码字。
码字长度:这个二进制串的长度称为码字长度。码字长度不变就是固定编码，否则就是变长编码。变长编码可以达到比定长编码好得多的压缩率。其核心思想就是赋予高频字符（出现频率高的字符）短（码字长度较短）码字，赋予低频字符长码字。
如果一个文档中，每个字符出现的频率基本一样，那变长编码的优势在压缩方面的优势就不存在了。
哈弗曼会自底向上构造出一棵对应最优编码的二叉树，下面举例来说明。某个文件中有如下字符及其概率。
字符 a b c d e f
概率 45 13 12 16 9 5
构造过程如下图所示：
每个字符都已
经按照出现频率大小排好顺序，在后续的步骤中，每次都将频率最低的两棵树合并，然后用合并后的结果再次排序。注意，排序不是目的，目的是找到这时出现频率最低的两项，以便下次合并， gzip 源码中并没有专门去“排序” ，而是使用专门的数据结构把频率最低的两项找到即可。
在叶子节点用矩形表示，每个叶子节点包含一个字符及其频率。中间节点用圆圈表示，包含其孩子节点的频率之和。中间节点指向左孩子的边标记为 0 ，指向右孩子的边标记为 1 。第6步骤的每个字符的编码都是前缀码。
(1) 按照频率大小先排序

文章插图

(2)把f和e拿出来组成一个子树，并相加，再把子树相加的结果，再次进行排序

文章插图

(3)在重复前面的排序和最小的两个概率相加操作

文章插图

(4)依次重复之前的操作

文章插图

(5)依次重复之前的操作

文章插图

(6)依次重复之前的操作

文章插图

代码思想:
利用库中的优先级队列实现哈夫曼树，最后基于哈夫曼树最终实现文件压缩。
(1)统计文件中字符出现的次数，利用优先级队列构建 Haffman 树，生成 Huffman 编码。构造过程中可以使用priority_queue 辅助，每次 pq.top()都可以取出权值（频数）最小的节点。每取出两个最小权值的节点，就 new 出一个新的节点，左右孩子分别指向它们。然后把这个新节点 push 进优先队列。
(2)压缩，实际就是存入压缩编码。利用 Haffman 编码对文件进行压缩，即在压缩文件中按顺序存入每个字符的 Haffman 编码。

文章插图

（3）将文件中出现的字符以及它们出现的次数写入配置文件中，以便后续压缩使用。
（4）解压缩：利用配置文件重构 Haffman 树，对文件进行减压缩
后面的文章会来详细分析代码:
7.deflate 采用的改进版 LZ77 算法
三个字节以上的重复串才进行编码，否则不进行编码：
为什么最小匹配3个字节？
gzip 中， <匹配长度,到匹配串开头的距离>对中， "匹配长度"的范围为 3-258 ，也就是 256 种可能值，需要 8bit来保存。"到匹配串开头的距离"的范围为 0-32K ，需要 15bit 来保存。所以一个<匹配长度,到匹配串开头的距离>对需要 23 位，差一位 3 个字节。如果匹配串小于 3 个字节的话，使用<匹配长度,到匹配串开头的距离>对进行替换，不但没有压缩，反而还会增大。所以保存<匹配长度,到匹配串开头的距离>对所需要的位数，决定了最小匹配长度至少要为 3 个字节。
deflate 无损压缩解压算法
先 LZ77 压缩，再用huaffman编码。
deflate 中的 huffman 编码：
对 LZ77 得到的压缩后结果，需要统计字符生成编码表 huffmantree(指示每个编码代表什么字符）,根据码表对内容进行编码，具体的压缩大小在于精细分配结构体的位域来实现 Huffman 编码的压缩效果的。编码表huffmantree和编码后的data都一起放置在文件中。