引入
go 里的 gzip 打包 大小和c++ 调用的gzip 不一样
找了下go的 gzip是这个 https://github.com/klauspost/compress
go + zip -> gzip
c++的gzip https://ftp.gnu.org/gnu/gzip/
gnu + zip -> gzip
但是两者都是用了 DEFLATE 算法
DEFLATE算法基础
在比较两种实现前，让我们先了解它们共同的基础——DEFLATE算法：
DEFLATE是一种结合了LZ77和哈夫曼编码的无损压缩算法：
- LZ77压缩：通过滑动窗口技术寻找重复数据，用(距离,长度)对替代重复内容
- 哈夫曼编码：根据字符出现频率分配变长编码，频率高的字符获得更短的编码
这种组合使DEFLATE成为一种平衡了压缩率和性能的经典算法，被广泛应用于ZIP、gzip、PNG等格式中。
+----------------------+ DEFLATE算法流程 +-------------------------+
| | | |
| 原始数据流 | | 压缩后数据流 |
| | | |
+----------+-----------+ +-----------+-------------+
| ^
| |
v |
+----------+-----------+ +-----------------+ +--------+-------------+
| | | | | |
| 分块处理(最大64KB) +------->+ 基于块类型选择 +--->+ 生成DEFLATE数据块 |
| | | | | |
+----------------------+ +-------+---------+ +----------------------+
|
v
+------------------------------+-+--------------------------------+
| | |
v v v
+------+--------+ +--------+----------+ +---------+---------+
| | | | | |
| 不压缩块 | | 静态哈夫曼块 | | 动态哈夫曼块 |
| (直接复制) | | (固定编码表) | | (自定义编码表) |
| | | | | |
+---------------+ +-------------------+ +-------------------+
+-----------------------------------------------------------------------------------------------+
| DEFLATE块结构 |
+---------------+----------------+----------------+----------------+--------------------------+--+
| 块头部(3位) | 块类型(2位) | [可选]长度字段 | [可选]哈夫曼表 | 实际压缩数据 |
| BFINAL | BTYPE | | | |
| 0: 非最后块 | 00: 不压缩 | 不压缩块: | 动态哈夫曼: | 基于当前编码表的 |
| 1: 最后一块 | 01: 固定哈夫曼 | LEN + NLEN | 哈夫曼表定义数据 | 压缩后内容 |
| | 10: 动态哈夫曼 | | | |
| | 11: 保留(错误) | | | |
+---------------+----------------+----------------+----------------+--------------------------+--+
LZ77 滑动窗口匹配过程
原始文本: "abcdefgabcxyz"
| |
| +-- 当前处理位置
+---------- 历史数据 (窗口)
+------------------+ +------------------+ +-------------------+
| | | | | |
| 滑动窗口(历史数据) | | 前向缓冲区(待压缩) | | 压缩结果输出 |
| | | | | |
+------------------+ +------------------+ +-------------------+
32KB最大 最大258字节
步骤1: 查找最长匹配
"abcdefg|abcxyz"
|
+-- 当前位置
找到匹配: "abc" 在距离当前位置7个字符处
步骤2: 输出(距离,长度)对
输出: (7,3) <- 表示"向前看7个字符，复制3个字符"
步骤3: 移动窗口并继续
"abcdefgabc|xyz"
|
+-- 新的当前位置
哈夫曼编码流程
哈夫曼编码构建过程
1. 统计频率
+--------+--------+
| 符号 | 频率 |
+--------+--------+
| A | 5 |
| B | 2 |
| C | 1 |
| D | 3 |
+--------+--------+
2. 构建哈夫曼树
+----+
| 11 |
+----+
/ \
/ \
+----+ +----+
| 5 | | 6 |
+----+ +----+
| / \
| / \
+----+ +----+ +----+
| A:5| | D:3| | 3 |
+----+ +----+ +----+
/ \
/ \
+----+ +----+
| B:2| | C:1|
+----+ +----+
3. 生成编码表
+--------+----------+
| 符号 | 编码 |
+--------+----------+
| A | 0 |
| B | 110 |
| C | 111 |
| D | 10 |
+--------+----------+
完整DEFLATE压缩过程示例
原始数据: "ABRACADABRA"
1. LZ77处理
+-------------------------------+
| A | B | R | A | C | A | D | A | B | R | A |
+-------------------------------+
|
v
+-------------------------------+
| A | B | R | A | C | A | D | (5,3) | A |
+-------------------------------+
找到ABR重复 指向前面的"ABR"
2. 分类为字面量与(距离,长度)对
字面量: A,B,R,A,C,A,D,A
匹配引用: (5,3) - 指向前面5个位置处的3个字符
3. 哈夫曼编码
+--------+----------+ +-------------+----------+
| 字面量 | 编码 | | 长度码 | 编码 |
+--------+----------+ +-------------+----------+
| A | 0 | | 3 | 10 |
| B | 110 | +-------------+----------+
| C | 1110 |
| D | 1111 | +--------------+----------+
| R | 10 | | 距离码 | 编码 |
+--------+----------+ +--------------+----------+
| 5 | 01 |
+--------------+----------+
4. 最终输出
块类型(动态哈夫曼) + 哈夫曼表 + 压缩数据(编码后的字面量和长度-距离对)
DEFLATE算法的强大之处在于将LZ77的字典压缩与哈夫曼的熵编码结合，既能捕获数据中的重复模式，又能根据字符频率优化编码长度，是一种经典而高效的压缩技术。
Go的klauspost/compress库
klauspost/compress是Go语言中高性能压缩库的代表作，它不仅提供了gzip实现，还包含多种压缩算法：
主要特点
- 多算法统一框架：
- 支持gzip、zlib、deflate、s2、zstandard等多种压缩格式
- 提供一致的API接口设计
- 性能优先：
- 相较于标准库通常提供2-5倍的速度提升
- 针对AMD64和ARM64架构的汇编优化
- 支持并发压缩，最大化多核CPU利用率
- 灵活的压缩策略：
- 重新平衡的压缩级别设计
- 提供无状态压缩选项，适合高并发场景
- 内存使用优化，减少大量并发压缩时的内存占用
版本迭代
从库的更新日志可以看出，klauspost/compress持续进行了大量优化：
- 改进哈希表实现
- 优化匹配查找算法
- 增加缓冲区复用机制
- 针对不同数据类型的特殊优化
GNU gzip实现
作为Unix/Linux世界的经典工具，GNU gzip有着悠久的历史：
特点与设计理念
- 稳定可靠：
- 历经数十年验证的实现
- 从1.2.4版本(1993年)到现在的1.13版本(2023年)保持格式兼容性
- 压缩率优先：
- 相对保守的算法实现，倾向于更高的压缩率
- 优化设计更关注压缩结果质量
- C语言实现：
- 通过经典C语言实现，针对底层系统优化
- 内存管理更为精细
为什么输出大小不同？
同样是实现DEFLATE算法，为什么两种库产生的压缩文件大小会不同？这主要源于以下几点：
1. 算法实现差异
-
窗口管理策略不同： klauspost实现可能使用不同的滑动窗口大小和策略
-
匹配查找算法差异： 两者在查找重复字符串时使用的启发式算法不同，导致找到的匹配模式不同
-
哈希表实现： Go库使用现代的哈希算法，而GNU可能保留较为经典的实现
2. 优化目标不同
-
klauspost更注重速度： 为了实现更高的吞吐量，可能牺牲了一些压缩率
-
GNU gzip注重压缩率： 传统实现更关注文件最终大小，对时间效率要求相对较低
3. 块边界决策
-
块分割策略： 两种实现在决定数据块边界时采用不同策略
-
动态/静态哈夫曼表选择： 对于何时使用静态或动态哈夫曼表的决策逻辑不同
实际应用建议
根据不同场景，选择适合的压缩实现：
适合使用klauspost/compress的场景
- Web服务器：需要实时压缩HTTP响应
- 高并发应用：同时需要处理多个压缩/解压任务
- 速度敏感场景：对响应时间要求较高的系统
- Go语言项目：与现有Go代码无缝集成
适合使用GNU gzip的场景
- 离线压缩：备份、归档等不急于立即完成的任务
- 存储优先：云存储计费按容量的场景
- 系统集成：与传统Unix/Linux工具链配合
- 最大兼容性：需要与各种系统互操作的场景