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

Question

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

谢谢！

Answer 1

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

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

一种方法是将某些字符保留为“特殊”（所谓的“转义序列”）。您可以按照自己的方式进行操作，即使用<标记反向引用的开始。<但是，如果它是文字，您还需要一种输出方式。例如，您可以通过确定 when after <there's another <，然后它表示文字，并且您只需输出 one即可做到这一点<。或者，您可以确定如果在之后<立即有>，中间没有任何内容，那么这不是反向引用，所以您只需输出<。

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

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

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

Answer 2

如果我正确理解你的问题，那是没有意义的。LZ77 压缩器的未压缩输入没有“保留字节”。您需要简单地对文字和长度/距离对进行明确编码。