LZ4压缩算法解释

9

来自 维基百科 的描述:

LZ4算法将数据表示为一系列序列。每个序列以一个字节的令牌开头,该令牌被分成两个4位字段。第一个字段表示要复制到输出的文字字节数。第二个字段表示要从已解码的输出缓冲区中复制的字节数(0表示最小匹配长度为4个字节)。在任一位字段中的值15表示长度更长,并且有一个额外的数据字节要添加到长度中。在这些额外字节中值为255表示要添加另一个字节。因此,任意长度都由一系列包含值255的额外字节表示。在文字字符串之后是标记和指示字符串长度所需的任何额外字节。然后是偏移量,用于指示从输出缓冲区开始复制的位置。匹配长度的额外字节(如果有)出现在序列的末尾。

我完全不明白! 有没有简单清晰的例子可以理解?例如,在上面的说明中,什么是文字字节和匹配? 当我们刚开始压缩时,如何有已解码的输出缓冲区?长度是什么?

此处的说明对我来说也无法理解。

如果您有更好的解释方式,那么简单的例子是不错的。


考虑无符号字符的字符串:“hello eddy how are you”。它们如何被压缩? - ade
7
以下链接提供了LZ4压缩格式的非常好的解释,以及它的工作原理:http://www.brutaldeluxe.fr/products/crossdevtools/lz4/index.html。 - Cyan
好的,所以在每个压缩块中可能会有一个文字节段和许多匹配部分?这似乎是合理的,因为一系列字节可以重复数十次。是这种情况吗? - ade
1个回答

8

首先,了解正在使用的核心方法LZ77。该文本是描述一种特定方式来编码先前数据中的字面量和字符串匹配的。

当未压缩的数据中的下一个字节出现在先前解压缩的数据中时,就会产生匹配。所以,不直接发送这些字节,而是发送长度和偏移量。然后,向后移动偏移字节并将长度字节复制到输出。

是的,在流的开头不能有匹配项。您必须从literal开始。(除非有预设的字典,这是另一个话题。)


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接