DEFLATE:反向引用真的更好吗？

Question

我正在制作自己的放气压缩器，它几乎每次都能击败ZLIB库。

在DEFLATE格式(LZ77)中，数据流要么包含一个字节文字，要么包含一个反向引用，即我们应该从先前解码的字节中复制字节序列。压缩器通常执行LZ77 (找到尽可能多的反向引用)，然后构建霍夫曼树并压缩该字节/引用流。

可能会有一个极端的情况:引用3个相同的字节，长度由15位编码，距离由15+13位编码，而编码的字节在我们的霍夫曼树中只有1位。差别是43个比特与3个比特。使用引用使输出比直接编码字节大14倍。

我的问题如下:我有一个10,097,918B的文本文件。ZLIB在其LZ77中的引用覆盖了9,089,334B，而我的压缩器覆盖了9,305,056B，所以我想我可以说我的LZ77更好。

但是ZLIB给出了1,329,309 B文件，而我的程序给出了1,381,153 B文件(两者都构建了最优的霍夫曼树)。因此，较好的LZ77会导致较差的霍夫曼编码。有没有关于对霍夫曼友好的LZ77的研究？

Answer 1

这是一个困难的问题，因为你只有在做出所有决定是采用原文还是反向引用之后，才知道与这些决定相关的bit成本。但您可以迭代并使用上一次运行的成本来做出这些决策，同时重新编码几次，直到您对结果满意为止。

这是Zopfli为了在保持DEFLATE格式的同时获得更好的压缩比而做的事情之一，除了使用最短路径方法而不是贪婪的决定。