LZ77和转义字符

Question

我在尝试实现LZ77压缩算法时遇到了这个问题。

我以字节为单位压缩输入(可以是任何二进制文件，而不仅仅是文本文件)，并且我使用3个字节来表示指向以前的子字符串的指针/引用。指针的第一个字节总是转义字符，b"\xCC"，为了简单起见，我们假设它是C。

在使用转义字符时，我知道的“标准”方法是，正常地对所有其他字符进行编码，然后转义与转义字符具有相同值的文字。因此，'ABCDE‘编码为'ABCCDE’。

问题是，指针的值可能是“CCx”，其中第二个字节可能是“C”，并使指针与转义的文字“CC”无法区分，这会导致问题。

我该怎么解决这个问题呢？或者，做LZ77的正确/标准方法是什么？谢谢!

Answer 1

为了让LZ77变得有用，它后面需要一个熵编码器。在该步骤中，您将符号编码为进入压缩数据的位。

一种方法是定义258个符号，256个用于文字字节，一个指示后面的匹配的长度和距离，以及一个指示流的结束。

或者，您可以执行deflate所做的操作，即将长度和文字一起编码，以便将符号解码为文字字节或长度，其中长度表示后面跟有距离代码。

或者你可以像brotli一样，定义“插入和复制”代码，它给出了文字的数量，然后是那么多的文字代码，然后是复制长度和距离。

或者你可以发明你自己的。