gzip的原理主要包含以下几个方面:
- 压缩算法:gzip使用DEFLATE算法进行压缩。DEFLATE是LZ77算法的变种,它通过字符串匹配和哈夫曼编码来实现无损数据的压缩。
- 字符串匹配:DEFLATE算法会查找文本中最长的重复字符串,使用前后出现位置的差异来表示这个字符串,而不是重复记录字符串本身,这样可以实现压缩。
- 哈夫曼编码:DEFLATE使用可变长的哈夫曼编码来编码匹配后的串。哈夫曼编码会根据字符出现的频率为每个字符分配不同长度的二进制码,最常见的字符编码更短。这可以进一步提高压缩效率。
- 块区分:gzip将待压缩文件以块为单位进行处理,每个块可以由不同的哈夫曼树表示,适用于文件中字符分布的局部变化。
- 预定义字典:在编码过程中使用预定义的字典进行字符串匹配,减少编码后的二进制串长度。
- 文件头:压缩文件以标准格式开始,包含方式、选项、大小等元数据。
- 压缩后再校验:使用CRC32码对压缩数据进行校验,可以检测解压后是否与原始文件一致。
通过这些建立在DEFLATE算法基础上的技术手段,gzip实现了无损数据压缩的目的。解压时按过程反向还原即可完成解压。
分块
在gzip压缩算法中,如何区分不同的块主要有以下几点:
- 每个块以固定长度结束。默认块长度是32K字节,但可以通过参数调整。当压缩的数据量达到一个块的长度时,就结束当前块处理。
- 每个块使用自己的哈夫曼树。哈夫曼树的结构取决于块内字符的频率分布,不同块频率不同就会产生不同的哈夫曼树。
- 在块头中记录哈夫曼树信息。开始每个新块时,会记录该块对应的哈夫曼树结构,用于后续解码时重建正确的树。
- 块间加入间隔码。压缩完成每个块后,会加入一个间隔码,标识下一个块的数据开始。这使得解压时能准确划分不同块。
- 文件头记录总块数。文件头里会记录整个文件包含多少个块,解压时知道需要处理的总块数。
- 块编号顺序递增。每个块会根据顺序赋予一个编号,保证解压时块解析顺序的一致性。
- 数据校验和跨块无关。每个块内数据使用CRC32校验,但校验范围不包括块头和间隔码,因此块与块互不影响。
所以主要通过块长度、哈夫曼树、间隔码等手段,使得gzip能够明确划分出不同数据块,实现局部优化的压缩效果。
Note
因为是分块，所以最大的效果是压缩成 1/32 ？