2023年8月3日发(作者：)

Linux（程序设计）：28---数据流压缩原理（Deflate压缩算法、gzip、zlib）⼀、压缩原理压缩原理其实很简单，就是找出那些重复出现的字符串，然后⽤更短的符号代替， 从⽽达到缩短字符串的⽬的。⽐如，有⼀篇⽂章⼤量使⽤"中华⼈民共和国"这个词语， 我们⽤"中国"代替，就缩短了 5 个字符，如果⽤"华"代替，就缩短了6个字符。事实上， 只要保证对应关系，可以⽤任意字符代替那些重复出现的字符串本质上，所谓"压缩"就是找出⽂件内容的概率分布，将那些出现概率⾼的部分代替成更短的形式。所以：内容越是重复的⽂件，就可以压缩地越⼩。⽐如，"ABABABABABABAB"可以压缩成"7AB"相应地，如果内容毫⽆重复，就很难压缩。极端情况就是，遇到那些均匀分布的随机字符串，往往连⼀个字符都压缩不了。⽐如，任意排列的10个阿拉伯数字 （5271839406），就是⽆法压缩的；再⽐如，⽆理数（⽐如π）也很难压缩压缩极限概念：当每⼀个字符都不重复的时候，就不能再去压缩了，也就是不能⽆限的压缩⾹农极限：下⾯是⼀个例⼦。假定有两个⽂件都包含1024个符号，在ASCII码的情况下，它们的长度是相等的，都是1KB。甲⽂件的内容50%是a，30%b，20%是c，⽂本⾥⾯只有abc，则平均每个符号要占⽤1.49个⼆进制位⽐如每个字节的数值概率是0~255，均匀分布每个数值出现的概率 1/256，如果⼀ 段⽂字的字节数值是平均分布，则Pn =1/256，计算出极限为8关注 字节的数值附加，的计算⽹址：⼆、Deflate压缩算法deflate压缩算法⽤来很多地⽅：例如其是zip压缩⽂件的默认算法、在zip⽂件中，在7z， xz 等其他的压缩⽂件中都⽤gzip压缩算法、zlib压缩算法等都是对defalte压缩算法的封装（下⾯会介绍）gzip、zlib等压缩程序都是⽆损压缩，因此对于⽂本的压缩效果⽐较好，对视频、图⽚等压缩效果不是很好(视频⼀般都是采⽤有损压缩算法)，所以对于视频、图⽚这种已经是⼆进制形式的⽂件可以不需要压缩，因为效果也不是很明显实际上deflate只是⼀种压缩数据流的算法。 任何需要流式压缩的地⽅都可以⽤Deflate压缩算法=LZ77算法+哈夫曼编码deflate算法下的压缩器有三种压缩模型：不压缩数据，对于已经压缩过的数据，这是⼀个明智的选择。 这样的数据会会稍稍增加，但是会⼩于在其上再应⽤⼀种压缩算法压缩，先⽤LZ77压缩，然后⽤huffman编码。 在这个模型中压缩的树是Deflate规范规定定义的， 所以不需要额外的空间来存储这个树压缩，先⽤LZ77压缩，然后⽤huffman编码。 压缩树是由压缩器⽣成的，并与数据 ⼀起存储数据被分割成不同的块，每个块使⽤单⼀的压缩模式。 如过压缩器要在这三种压缩模式中相互切换，必须先结束当前的块，重新开始⼀个新的块信息熵数据为何是可以压缩的，因为数据都会表现出⼀定的特性，称为熵。绝⼤多数的数据所表现出来的容量往往⼤于其熵所建议的最佳容量。⽐如所有的数据都会有⼀定的冗余性，我们可以把冗余的数据采⽤更少的位对频繁出现的字符进⾏标记，也可以基于数据的⼀些特性基于字典编码，代替重复多余的短语三、LZ77算法原理Ziv和Lempel于1977年发表题为“顺序数据压缩的⼀个通⽤算法（A Universal Algorithm for Sequential Data Compression）。LZ77 压缩算法采⽤字典的⽅式进⾏压缩， 是⼀个简单但⼗分⾼效的数据压缩算法。其⽅式就是把数据中⼀些可以组织成短语(最长字符)的字符加⼊字典，然后再有相同字符出现采⽤标记来代替字典中的短语，如此通过标记代替多数重复出现的⽅式以进⾏压缩关键词术语：前向缓冲区：每次读取数据的时候，先把⼀部分数据预载⼊前向缓冲区。为移⼊滑动窗⼝做准备，⼤⼩可以⾃⼰设定滑动窗⼝：⼀旦数据通过缓冲区，那么它将移动到滑动窗⼝中，并变成字典的⼀部分。滑动窗⼝的⼤⼩也可以⾃⼰设定的短语字典：从字符序列 S1...Sn，组成n个短语。⽐如字符(A,B,D)，可以组合的短语为 {(A)，(A,B)，(A,B,D)，(B)，(B,D)，(D)}，如果这些字符在滑动窗⼝⾥⾯，就可以记为当前的短语字典，因为滑动窗⼝不断的向前滑动，所以短语字典也是不断的变化优缺点：⼤多数情况下LZ77压缩算法的压缩⽐相当⾼，当然了也和你选择滑动窗⼝⼤⼩， 以及前向缓冲区⼤⼩，以及数据熵有关系缺点：其压缩过程是⽐较耗时的，因为要花费很多时间寻找滑动窗⼝中的短语匹配优点：不过解压过程会很快，因为每个标记都明确告知在哪个位置可以读取了算法的主要逻辑LZ77 的主要算法逻辑就是，先通过前向缓冲区预读数据，然后再向滑动窗⼝移⼊（滑动窗⼝有⼀定的长度），不断的寻找能与字典中短语匹配的最长短语，然后通过标记符标记我们还以字符ABD为例⼦，看如下图:⽬前从前向缓冲区中可以和滑动窗⼝中可以匹配的最长短语就是（A，B），然后向前移动的时候再次遇到（A，B）的时候采⽤标记符代替LZ77压缩原理当压缩数据的时候，前向缓冲区与滑动窗⼝之间在做短语匹配的是后会存在2种情况：（1）找不到匹配时：将未匹配的符号编码成符号标记（多数都是字符本⾝）（2）找到匹配时：将其最长的匹配编码成短语标记短语标记包含三部分信息：（1）滑动窗⼝中的偏移量（从匹配开始的地⽅计算）（2）匹配中的符号个数（3）匹配结束后的前向缓冲区中的第⼀个符号⼀旦把 n 个符号编码并⽣成相应的标记，就将这 n 个符号从滑动窗⼝的⼀端移出， 并⽤前向缓冲区中同样数量的符号来代替它们，如此，滑动窗⼝中始终有最新的短语演⽰案例演⽰案例初始化：如下所⽰，滑动窗⼝的初始化⼤⼩为8，向前缓冲区的⼤⼩为4压缩A：滑动窗⼝中没有数据，所以没有匹配到短语，将字符A标记为A压缩B：滑动窗⼝中有 A，没有从缓冲区中字符（BABC）中匹配到短语，依然把B标记为B压缩ABC：缓冲区字符（ABCB）在滑动窗⼝的位移6位置找到AB，成功匹配到短语AB，将AB编码为(6,2,C)6：重复的字符串的起始位置。此处为滑动窗⼝索引[6]处2：重复的字符串长度为2，也就是ABC：重复的字符串的下⼀个字符是C压缩BABA：缓冲区字符（BABA）在滑动窗⼝位移4的位置匹配到短语 BAB，将 BAB 编码为(4,3,A)4：重复的字符串的起始位置。此处为滑动窗⼝索引[4]处3：重复的字符串长度为3，也就是BABA：重复的字符串的下⼀个字符是A压缩BCA：缓冲区字符（BCAD）在滑动窗⼝位移 2 的位置匹配到短语BC，将BC编码为 （2,2,A）2：重复的字符串的起始位置。此处为滑动窗⼝索引[2]处2：重复的字符串长度为3，也就是BCA：重复的字符串的下⼀个字符是A最后压缩D：缓冲区字符 D，在滑动窗⼝中没有找到匹配短语，标记为D缓冲区中没有数据进⼊了，结束LZ77解压原理解压类似于压缩的逆向过程，通过解码标记和保持滑动窗⼝中的符号来更新解压数据当解码字符标记：将标记编码成字符拷贝到滑动窗⼝中解码短语标记：在滑动窗⼝中查找相应偏移量，同时找到指定长短的短语进⾏替换演⽰案例以上⾯最终压缩的样⼦为例，起始如下所⽰解压A：标记为A，直接将A解压解压B：标记为B，直接将B解压解压(6,2,C)：标记为(6,2,C)，通过在滑动窗⼝中找到索引[6]处，然后找到2个字符（AB），最后加上⼀个C，所以最终解压出来的就是ABC解压(4,3,A)：标记为(4,3,C)，通过在滑动窗⼝中找到索引[4]处，然后找到3个字符（BAB），最后加上⼀个A，所以最终解压出来的就是BABA解压(2,2,A)：标记为(2,2,A)，通过在滑动窗⼝中找到索引[2]处，然后找到2个字符（BC），最后加上⼀个A，所以最终解压出来的就是BCA解压D：标记为D，直接将D解压四、Huffman算法原理哈夫曼设计了⼀个贪⼼算法来构造最优前缀码，被称为哈夫曼编码（Huffman code）， 其正确性证明依赖于贪⼼选择性质和最优⼦结构。哈夫曼编码可以很有效的压缩数据，具体压缩率依赖于数据本⾝的特性这⾥我们先介绍⼏个概念：码字：每个字符可以⽤⼀个唯⼀的⼆进制串表⽰，这个⼆进制串称为这个字符的码字码字长度：这个⼆进制串的长度称为这个码字的码字长度定长编码：码字长度固定就是定长编码。变长编码：码字长度不同则为变长编码。变长编码可以达到⽐定长编码好得多的压缩率，其思想是赋予⾼频字符（出现频率⾼的字符）短（码字长度较短）码字，赋予低频字符长码字。例如，我们 ⽤ ASCII 字符编辑⼀个⽂本⽂档，不论字符在整个⽂档中出现的频率，每个字符都要占 ⽤⼀个字节。如果我们使⽤变长编码的⽅式，每个字符因在整个⽂档中的出现频率不同导致码字长度不同，有的可能占⽤⼀个字节，⽽有的可能只占⽤⼀⽐特，这个时候，整 ⽂档占⽤空间就会⽐较⼩了。当然，如果这个⽂本⽂档相当⼤，导致每个字符的出现频率基本相同，那么此时所谓变长编码在压缩⽅⾯的优势就基本不存在了（这点要⼗分明确，这是为什么压缩要分块的原因之⼀，源码分析会详细讲解）构造过程哈夫曼编码会⾃底向上构造出⼀棵对应最优编码的⼆叉树，我们使⽤下⾯这个例⼦来说明哈夫曼树的构造过程⾸先，我们已知在某个⽂本中有如下字符及其出现频率：构造过程如下图所⽰：在⼀开始，每个字符都已经按照出现频率⼤⼩排好顺序在后续的步骤中，每次都将频率最低的两棵树合并，然后⽤合并后的结果再次排序（注意，排序不是⽬的，⽬的是找到这时出现频率最低的两项，以便下次合并。gzip 源码中并没有专门去“排序”，⽽是使⽤专门的数据结构把频率最低的两项找到即可）叶⼦节点⽤矩形表⽰，每个叶⼦节点包含⼀个字符及其频率。中间节点⽤圆圈表⽰，包含其孩⼦节点的频率之和。中间节点指向左孩⼦的边标记为 0， 指向右孩⼦的边标记为 1。⼀个字符的码字对应从根到其叶节点的路径上的边的标签序列图1为初始集合，有六个节点，每个节点对应⼀个字符；图2到图5为中间步骤， 图6为最终哈夫曼树。此时每个字符的编码都是前缀码哈夫曼编码编码实现利⽤库中的优先级队列实现哈夫曼树，最后基于哈夫曼树最终实现⽂件压缩代码结构为：1.统计⽂件中字符出现的次数，利⽤优先级队列构建Haffman树，⽣成Huffman编码。构造过程可以使⽤ priority_queue辅助，每次()都可以取出权值（频数）最⼩ 的节点。每取出两个最⼩权值的节点，就new出⼀个新的节点，左右孩⼦分别指向它 们。然后把这个新节点 push 进优先队列。2.压缩：利⽤ Haffman 编码对⽂件进⾏压缩，即在压缩⽂件中按顺序存⼊每个字符 的 Haffman 编码。 码表（实际存储是对应数值的概率，然后调⽤程序⽣成码表） + 编码3.将⽂件中出现的字符以及它们出现的次数写⼊配置⽂件中，以便后续压缩使⽤4.解压缩：利⽤配置⽂件重构 Haffman 树，对⽂件进⾏减压缩源码链接为：⽬录结构为：、、三个⽂件是哈夫曼编码的主要代码，testfile/⽬录下是⼀些测试的代码（⽤来压缩和解压缩的）代码讲解Compress()函数：会构造⼀棵哈夫曼树，然后读取⽂件，将⽂件中的每个字符进⾏编码形成⼀个⼆进制值，然后打印出来Compress()函数：码表的相关信息，info._ch打印的是每个字符，info._count是这个字符出现的频率，就是上⾯“构造过程”对应的第⼀张图。然后会将这个码表的信息写⼊压缩⽂件中Compress()函数：压缩完成之后会打印相关信息，其中“huffman code table size”是码表的⼤⼩，就是Uncompress()函数：读取码表（写⼊字符的信息）Uncompress()函数：然后重构哈夫曼树编码测试先编译程序g++ -o huffman 现在我们想将./testfile/下的test_file1⽂件进⾏压缩，输⼊下⾯的命令即可，效果如下图所⽰：红框圈出来的部分：每⼀个字符的信息，以红框为例，[105868]代表该字符在⽂件中的偏移(seek)，125代表该字符的ASCII值，01111101代表哈夫曼编码(值越⼤说明出现的次数越少，值越⼩说明出现的次数越多)下⾯箭头是打印的程序总的运⾏信息./huffman ./testfile/test_file1程序运⾏之后会⽣成⼀个压缩⽂件(.huffman)和⼀个解压缩⽂件(.unhuffman)。通过下图可以看出test_file1压缩之后由104K变为了65K，解压之后⼜回到了104K，压缩⽐为0.625现在我们对视频进⾏压缩看看，因为视频⽂件⼤⼩⽐较⼤，所以在进⾏解压缩的时候⼤量的打印信息会导致程序运⾏很久才会结束，因此在对视频进⾏解压缩之前将⽂件中的⼀处打印语句注释掉（如下图所⽰）注释掉之后重新编译，运⾏，然后查看解压缩信息，如下所⽰，可以看出视频在压缩之后只减少了1M，因此视频的压缩效率⽐较低g++ -o huffman ./huffman ./testfile/

现在我们使⽤Windows⾃带的.zip压缩⼯具来对⽐⼀下，可以看到其压缩效率⽐我们上⾯的哈夫曼解压缩的效率要⾼这种哈夫曼解压缩的效率⽐较低，在Zlib库⽂章中我们有调⽤Zlib库API编写的解压缩程序，因为是直接调⽤库函数，所以解压缩的效率⽐较⾼，可以参阅：五、gzip压缩算法gzip压缩算法是对deflate进⾏的封装。gzip本⾝只是⼀种⽂件格式，其内部通常采⽤Deflate数据格式，⽽Deflate采⽤LZ77压缩算法来压缩数据gzip=gzip头+deflate 编码的实际内容+gzip尾gzip⽂件由1到多个“块”组成，实际上通常只有1块。每个块包含头、数据和尾3部分。块的概貌如下：头部分ID1 与 ID2：各 1 字节。固定值，ID1 = 31 (0x1F)，ID2 = 139(0x8B)，指⽰ GZIP 格式CM：1 字节。压缩⽅法。⽬前只有⼀种：CM = 8，指⽰ DEFLATE ⽅法FLG：1 字节。标志：bit 0 FTEXT - 指⽰⽂本数据bit 1 FHCRC - 指⽰存在 CRC16 头校验字段bit 2 FEXTRA - 指⽰存在可选项字段bit 3 FNAME - 指⽰存在原⽂件名字段bit 4 FCOMMENT - 指⽰存在注释字段 bit 5-7 保留MTIME：4 字节。更改时间。UINX 格式XFL：1 字节。附加的标志。当 CM = 8 时， XFL = 2 - 最⼤压缩但最慢的算法；XFL = 4 - 最快但最⼩压缩的算法OS：1 字节。操 作系统，确切地说应该是⽂件系统。有下列定义：0 - FAT ⽂件系统 (MS-DOS, OS/2, NT/Win32)1 - Amiga2 - VMS/OpenVMS3 - Unix4 - VM/CMS5 - Atari TOS6 - HPFS ⽂件系统 (OS/2, NT)7 - Macintosh8 - Z-System9 - CP/M10 - TOPS-2011 - NTFS ⽂件系统 (NT)12 - QDOS13 - Acorn RISCOS255 - 未知额外的头字段存在额外的可选项时，SI1 与 SI2 指⽰可选项 ID，XLEN 指⽰可选项字节数。如 SI1 = 0x41 ('A')，SI2 = 0x70 ('P')，表⽰可选项是 Apollo ⽂件格式的额外数据(若 = 1)(若 = 1)(若 NT = 1)(若 = 1)数据部分BFINAL：1 ⽐特。0 - 还有后续⼦块；1 - 该⼦块是最后⼀块BTYPE：2 ⽐特。00 - 不压缩；01 - 静态 Huffman 编码压缩；10 - 动态 Huffman 编码压缩；11 - 保留各种情形的处理过程，请参考后⾯列出的 RFC ⽂档尾部分CRC32：4 字节。原始(未压缩)数据的 32 位校验和ISIZE：4 字节。原始(未压缩)数 据的长度的低 32 位。GZIP 中字节排列顺序是 LSB ⽅式，即 Little-Endian，与 ZLIB 中的相反六、zlib压缩算法zlib压缩算法页是对deflate进⾏的封装zlib=zlib头+deflate编码的实际内容+zlib尾他也是⼀个实现库(delphi中有zlib，zlibex)，Zlib库参阅：七、Nginx中的gzip模块Nginx中有压缩数据模块(gzip模块)，可以⽤来提升⽹站速度。具体可以参阅：