Gzip/Deflate是否能识别模式？

Question

我正在学习Gzip的内部工作原理，了解到它使用了Huffman编码和LZ77的组合。

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

所以短语“horses race other horses”中的单词horses会被一个指针代替。

但是，如果我有一个32位整数数组，而它仅存储最多24位的数字呢？举个例子，假设这些24位数字非常随机，很难压缩，也很难找到重复的数据。

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

当数组可以轻松地缩减为具有基本模式识别的“24位”数组时，这似乎有些多余。

所以我的问题是：

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

Gzip可以将大量重复数据压缩成多少，并紧随其后的难以压缩的小量数据？

- YAHsaves

Answer 1

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

你所提到的字典只是紧接着当前被压缩字节的32K字节未压缩输入。这就是全部。每个长度/距离对可以引用最后32K中3到258个字节的字符串。这与deflate块无关，这样的引用通常会回到一个或多个块之前。

Deflate在尝试压缩三个随机字节、零字节、三个随机字节、零字节等序列时效果不佳。没有有用的重复字符串，其中deflate仅能够对文字进行Huffman编码，其中零更频繁。它将把零编码为两位，因为它们出现的次数略高于25％，而将其他文字编码至少为8.25位。对于这些数据，平均每字节约为6.7位或压缩比为0.85。实际上，gzip在这些数据上给出了约0.86。

如果要压缩该序列，请“简单地删除零字节！”然后您就完成了，无法进一步压缩，压缩比为0.75。

- Mark Adler

---

谢谢你的回答！它真的帮助我更好地理解gzip。我想使用32位字符串的原因是因为它是我的CPU自然使用的，所以当你有一个24位字符串时，你必须进行位移操作，这更加复杂。不过，我想我只能按照那种方式做了，谢谢！ - YAHsaves

Answer 2

有很多情况下，数据看起来是随机的，但实际上存在着潜在的结构。在这种情况下，一般的位压缩算法效果不佳，但通过预处理可以获得惊人的结果。

例如，如果你有一堆x、y坐标，这些数字看起来都是相当随机的，但如果它们代表了一个车辆的轨迹，那么增量将会是完全不随机的。因此，增量编码和其他更复杂的曲线拟合以及减去已知部分的方法可以大幅减小存储空间的大小。

- Dov