python - LZ77压缩保留字节 "< , >"

Question

我正在学习 LZ77 压缩，我发现当我找到重复的字节字符串时，我可以使用 <distance, length> 形式的指针，并且“<”、“、”、“>”字节被保留。那么...如果我无法压缩这些字节但无法用不同的字节更改它(因为解码器无法读取它)，我该如何压缩具有这些字节的文件。有办法吗？或者解码器仅解码是否有确切的<d, l>字符串？ (如果有的话，想象一下如果我们巧合地在文件中找到这些字节。会发生什么？)

谢谢!

Answer 1

LZ77 是通过字符串的长度和距当前位置的距离来引用解压缩缓冲区中的字符串。但如何对这些反向引用进行编码就取决于您了。 LZ77 的许多实现都以不同的方式实现。

但是你是对的，必须有某种方法来区分“文字”(未压缩的数据片段，意味着从输入“按原样”复制到输出)和“反向引用”(从已经复制的数据中复制)未压缩部分)。

一种方法是将某些字符保留为“特殊”(所谓的“转义序列”)。您可以按照您的方式进行操作，即使用 <标记反向引用的开始。但是你还需要一种方法来输出 <如果它是一个字面量。例如，您可以通过在<之后建立when来做到这一点。还有一个< ，那么它的意思就是一个字面量，你就输出一个< 。或者，您可以确定如果在 < 之后立即> ，中间没有任何内容，那么这不是反向引用，因此您只需输出 < .

它也不是对这些反向引用进行编码的最有效方法，因为它使用几个字节来对反向引用进行编码，因此只有在引用长于这几个字节的字符串时它才会变得有效。对于较短的反向引用，它会膨胀数据而不是压缩它们，除非您确定短于几个字节的匹配将按原样保留，而不是生成反向引用。但同样，这意味着较低的压缩增益。

如果您仅压缩普通的旧 ASCII 文本，则可以采用更好的编码方案，因为 ASCII 在一个字节中仅使用 8 位中的 7 位。因此，您可以使用最高位来表示反向引用，然后使用剩余的 7 位作为长度，并使用下一个字节(或两个)作为反向引用的距离。这样，您始终可以通过检查其最高位来确定下一个字节是文字 ASCII 字符还是反向引用。如果为0，则直接输出字符。如果为1，则使用后面的7位作为长度，并读取接下来的2个字节作为距离。这样，每个反向引用占用 3 个字节，因此您可以有效地压缩重复序列长度超过 3 个字符的文本文件。

但是还有一个更好的方法来做到这一点，它提供了更多的压缩:您可以用可变长度的位代码替换字符，这些位代码的制作方式使得更频繁出现的字符将具有最短的代码，而那些最常出现的字符将具有最短的代码。很少有会有更长的代码。为了实现这一点，这些代码必须是所谓的“前缀代码”，这样任何代码都不会成为其他代码的前缀。当您的代码具有此属性时，您始终可以通过按顺序读取这些位直到对其中一些进行解码来区分它们。然后，您可以确保通过读取更多位不会获得任何其他有效项目。下一位总是开始另一个新序列。要生成此类代码，您需要使用霍夫曼树。然后，您可以将所有字节和不同长度的引用连接到一棵这样的树中，并根据它们的频率为它们生成不同的位代码。当您尝试对它们进行解码时，您只需读取这些位，直到到达其中某些元素的代码，然后您就可以确定它是某个文字字符的代码还是反向引用长度的代码。在第二种情况下，您可以读取一些额外的位来了解反向引用的距离(也使用前缀代码进行编码)。这就是 DEFLATE 压缩方案的作用。但这完全是另一个故事，您可以在 @MarkAdler 提供的 RFC 中找到详细信息。