LZ77压缩保留字节"<，>“

Question

我正在学习LZ77压缩，我发现当我发现一个重复的字节字符串时，我可以使用<distance, length>形式的指针，并且"<"，“"，">”字节是保留的。所以..。如果我不能压缩这些字节，但又不能通过不同的字节来改变它(因为解码器将无法读取它)，我如何压缩具有这些字节的文件。有什么办法吗？(如果有，那么想象一下，如果我们在一个文件中找到了这些字节。会发生什么？)

谢谢!

Answer 1

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

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

一种方法是保留一些字符作为“特殊”(所谓的“转义序列”)。你可以像以前那样做，也就是使用<来标记反向引用的开始。但是，如果<是文字，那么您还需要一种方法来输出它。例如，你可以这样做，当在<之后有另一个<时，它意味着一个文字，然后你只输出一个<。或者，您可以确定，如果在<之后立即出现>，中间没有任何内容，那么这就不是反向引用，所以您只需输出<。

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

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

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

Answer 2

如果我没弄错你的问题，那就没道理了。LZ77压缩器的未压缩输入没有“保留字节”。您只需明确地对文字和长度/距离对进行编码即可。