compression - Gzip/Deflate 是否识别模式

Question

我正在研究 Gzip 的内部工作原理，我知道它使用了Huffman Coding和LZ77的组合。

我也意识到一个 Gzip 文件被分成多个块，每个块都有一个为它构建的字典。然后，频繁出现的相似数据被指向字典中位置的指针替换。

因此，短语“horses race other horses”将用指针代替horses一词。

但是，如果我有一个 32 位整数数组，但它只存储最多 24 位的数字呢？为了争论，可以说这些 24 位数字是非常随机的，很难压缩，也很难找到重复。

这将使每个整数的前 8 位成为易于压缩的 0 字符串，但每个字符串都需要一个指针，并且每个指针仍然占用一定量的数据。即使是 1 位指针（我知道它比实际可能的要小）仍然会占用原始空间的 12.5%。

当阵列可以很容易地简化为具有基本模式识别的“24 位”阵列时，这似乎有些多余。

所以我的问题是：

Gzip 是否包含比字典指针更好地压缩文件的机制？

Gzip 对少量重复数据的压缩效果如何，其次是少量难以压缩的数据？

标签： compressiongzipdeflate

Answer 1

每个放气块都没有“为其构建的字典”。为每个 deflate 块构建的是一组用于文字/长度符号和距离符号的 Huffman 代码。

您所指的字典只是紧接当前正在压缩的字节之前的 32K 字节未压缩输入。而已。每个长度/距离对可以引用最后 32K 中 3 到 258 个字节的字符串。这与 deflate 块无关，并且此类引用通常会返回一个或多个块。

Deflate 将无法很好地尝试压缩三个随机字节、零字节、三个随机字节、零字节的序列......将没有有用的重复字符串，其中 deflate 只能对文字进行 Huffman 编码，零是更频繁。它将零编码为两位，因为它们出现的几率略高于 25%，而其余的文字每个至少有 8.25 位。对于这个数据，平均每字节大约 6.7 位或 0.85 的压缩比。事实上 gzip 在这个数据上给出了大约 0.86。

如果要压缩该序列，只需删除零字节！然后你就完成了，不能以 0.75 的比率进一步压缩。