这套文章解释 zlib 怎样压缩和恢复数据,应用怎样使用它,以及这些实现需要证明什么。先用下面的地图认识各个组件,再选择算法概览、实现精读或具体函数的完整约定。
第一部分建立算法与接口的全局认识;第二部分按主题深入,先拆解算法和优化,再连接证明思路。各章都有前置背景和下一步,旁边的全局目录可随时展开。
压缩与解压的全局地图
先看每个组件负责什么,再进入算法或证明。悬停、聚焦或点选节点,查看它的输入、输出和阅读入口。
窗口与匹配
重复片段可以用“回退距离、复制长度”描述。压缩器保留近期历史,寻找可以复用的内容;滑动窗口限制保留的历史范围,哈希链减少需要逐字节比较的候选。
- 输入
- 原始输入与近期历史
- 得到的结果
- 字面量和长度/距离对
Huffman 编码构造
符号的出现次数不同。给常见符号更短的码字,可以降低编码成本;解码器还必须知道使用了哪套编码,因此也需要描述码长。
- 输入
- 符号及其出现次数
- 得到的结果
- 码长、码字与树描述
块与压缩输出
码字长短不一,应用接收的却是整字节。这个组件选择块的表示,把编码接成字节,暂存尚未交付的部分,再随调用者提供空间逐步交付。
- 输入
- 符号、码字与输出空间
- 得到的结果
- 压缩块与待交付字节
位输入、解码表与复制
解压器识别块和编码表,把比特还原成字面量与匹配。字面量直接成为字节;匹配则从历史逐字节复制,重新产生原来的内容。
- 输入
- 压缩比特与可用历史
- 得到的结果
- 恢复出的原文字节
流式状态与封装
应用常把大任务拆成多批输入和输出。输入暂时不够,或本轮输出空间用完时,流状态记住处理到哪里;下一次换了缓冲区仍能继续。zlib 与 gzip 的头尾信息也沿同一个任务处理。
- 输入
- 分批输入与有限输出空间
- 得到的结果
- 可暂停、可接续的状态
状态操作与资源生命周期
窗口和内部状态需要分配,也可能在中途分配失败。初始化、重置、复制和结束操作共同决定哪些内容可以保留、哪些必须清理。
- 输入
- 状态块、窗口和其他资源
- 得到的结果
- 合法活状态与精确清理
校验和与组合
zlib 与 gzip 封装记录未压缩数据的校验值。解压时重新计算并比较,帮助发现损坏。Adler 与 CRC 用很小的状态累积这些信息,也能跨缓冲区继续。
- 输入
- 未压缩的数据
- 得到的结果
- 校验值与比对结果
应用接口与外部交互
应用需要交出输入、接收输出,并处理返回结果。缓冲区、回调和文件接口提供不同的使用方式,底层仍然复用压缩与解压引擎。
- 输入
- 调用请求与应用数据
- 得到的结果
- 交付的数据与返回结果
算法与接口
从重复字节到压缩流,再回到调用者手中的字节。先建立全局认识,再查具体接口。
阅读算法概览 →查看调用与接口地图 ↗算法精读与形式化验证
沿一条实现路径深入:数据怎样布局,优化怎样工作,最后需要证明哪些事实。
选择一个精读主题 →查阅其他组件的完整论证 ↗从三个符号到五个字节
本组精读从 A、B 和一个长度 6、距离 2 的匹配开始。先选择块的表示,再写出比特,接着追踪共用内存的读写,最后把这些算法事实连接成证明。
- 01算法精读↗
块选择与符号成本
比较同一份输入的三种块表示,解释何时值得发送新编码。
- 02算法精读↗
位输出与字节缓冲
把长短不齐的码字接成字节,再交给调用者。
- 03算法精读↗
共享存储与输出前缀
理解共用一块内存时,怎样保护尚未读取的符号。
- 04证明思路↗
压缩输出的证明思路
说明从符号到输出的每次写入怎样保留正确含义。
全部精读主题
窗口与匹配 ↗
重复片段的长度与距离从哪里来,以及为什么只需保留近期字节。
Huffman 编码构造 ↗
让常见符号占更少比特,并让解码端重建同一套编码。
块与压缩输出 ↗
把选好的符号写成压缩块,并安全交给调用者。
位输入、解码表与复制 ↗
读取压缩字节、识别符号,并恢复出原来的数据。
流式状态与封装 ↗
理解同一任务为什么需要多次调用,以及暂停后怎样继续。
状态操作与资源生命周期 ↗
开始、复用、复制和结束任务,同时处理分配失败。
校验和与组合 ↗
在分批处理时核对数据,并保留支持序列合并的信息。
应用接口与外部交互 ↗
为完整缓冲区、回调和 gzip 文件选择合适的调用方式。
概览与精读的连接
| 概览中的主题 | 深入实现 | 对应论证 |
|---|---|---|
| 块类型与成本 | 符号账目与三种块的成本 | 符号与格式的含义 |
| 位序与位缓冲 | 位寄存器、有效位数与待交付字节 | 写入前后的位串关系 |
| 流式调用 | 共享存储与输出交付 | 前缀界与跨调用连接 |
完整参考
接口定义域、返回值和错误路径在函数页完整保留;引擎论证和 Lean 正文可以沿章节继续查阅。