GNU ZIP

linux中，tar.gz是一种常见的文件后缀。

其中tar就代表“打包”，gz代表Gzip压缩。

tar

打包是对文件的一种很简单的拼接（但是加入了一些元数据），将零散的文件整合在一起方便传输。

这不是我们讨论的重点。

我们重点研究gz是怎么工作的。

gz

全称GNU Zip

它是一种基于DEFLATE算法的压缩方式，大概分为两步。

1. LZ77 (Gzip 的实现版本)

LZ77 的核心思想是 “引用代替重复”。如果一段数据在前面出现过，就用一个“指针”指向过去，而不是重新存储一遍。

核心机制：滑动窗口 (Sliding Window)

Gzip 维护一个 32KB 的滑动窗口，分为两部分：

• 历史 (History)：过去处理过的最近 32KB 数据（“回头看”的范围）。
• 未来 (Look-Ahead)：当前等待压缩的数据流。

工作逻辑

算法不断扫描“未来”的数据，尝试在“历史”中寻找相同的字节序列：

1. 查找匹配：拿着当前的数据去“历史”里搜寻。

   Gzip 规定：只有重复长度 ≥ 3 字节 时，才进行压缩。

2. 贪婪匹配：总是尽可能找最长的重复片段。

输出格式

Gzip 将数据流转化为了两种元素的混合体：

• 情况 A：没找到匹配 (或长度 < 3)
  • 动作：直接输出原始字符。
• 情况 B：找到了匹配 (长度 ≥ 3)
  • 动作：输出一个指针，代替那一串字符。
  • 格式：<Length, Distance>
  • 含义：“向回倒退 Distance 字节，复制 Length 个字节”。

2. Huffman Coding (霍夫曼编码)

这是 LZ77 之后的第二步压缩，主要解决统计学上的冗余。

LZ77 处理完的数据只是消除了“重复”，但并没有解决“频率”问题。霍夫曼编码接手处理 LZ77 输出的符号流（字面量 + 长度/距离）。

核心原理

霍夫曼编码的思想可以概括为：“常用的字写得简单点，不常用的字写得复杂点。”

• 统计频率：Gzip 会统计当前数据块中，每个符号出现的次数。
• 变长编码
  • 高频符号：分配极短的二进制码（如 0 或 10，仅占 1-2 bit）。
  • 低频符号：分配很长的二进制码（如 1101011，可能占 10+ bit）。
• 结果：相比于原始的固定 8 bit 编码，整体体积大大减小。

但是还要注意！👇

动态霍夫曼树 (Dynamic Huffman Trees)

• Gzip 不是用一套固定的密码本，而是把文件切成一个个 Block (块)。
• 对于每个块，它都会重新统计频率，生成一棵新的霍夫曼树存放在块的开头。