LZ77:存储格式

Question

我开始编写一个小程序，允许使用LZ77压缩算法压缩单个文件。效果很好。现在我在考虑如何存储数据。在LZ77中，压缩数据由一系列三重奏组成。每个三重奏具有以下格式：

<"start reading at n. positions backwards", "go ahead for n. positions", "next character">

怎样才能正确地存储这些三胞胎呢？我想：<11，5，8>位，然后：

• 2048位，用于向后看
• 32，匹配字符串
• 的最大长度为1字节。

这种格式在文本压缩方面非常好，但它对我的目的(由二进制图像制作的视频)来说很糟糕，如果与原始文件大小相比，它也会增加大小。你有什么意见建议？

Answer 1

我认为您的意思更像是：<后退n，复制k，插入文字byte>。

你需要看你的比赛的统计数据。您可能会得到许多具有零长度匹配的文字字节。对于这种情况，一个好的开端是使用一个位来决定匹配还是不匹配。如果该位是1，则后面跟着一个距离、长度和文字字节。如果它是零，则后面只有一个文字字节。

通过对文字、长度和距离进行编码，您还可以做得更好。长度和文字可以组合成一个代码，就像平放一样，这样就可以删除一个位。