1

我正在制作自己的 DEFLATE 压缩器,它几乎每次都击败了 ZLIB 库。

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

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

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

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

4

1 回答 1

2

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

这是 Zopfli 在保持 DEFLATE 格式的同时获得更好的压缩比所做的事情之一,此外还使用最短路径方法而不是贪婪决策。

于 2018-05-19T14:14:13.770 回答