c - LZSS 与 LZ77 压缩差异

Question

LZSS有人可以解释一下和LZ77算法之间的区别吗？我已经在网上找了几个小时，但我找不到区别。我找到了 LZ77 算法并且理解了它的实现。

但是，与 有何LZSS不同LZ77？比方说，如果我们有一个字符串"abracadabra"，如何以LZSS不同的方式压缩它LZ77？是否有我可以遵循的 C 伪代码？

感谢您的时间！

标签： ccompressiondifferencelz77

Answer 1

不幸的是，LZ77 和 LZSS 这两个术语的使用都非常松散，因此它们并不真正暗示非常具体的算法。当人们说他们使用 LZ77 算法压缩数据时，他们通常是指他们实施了基于字典的压缩方案，其中最近解压缩数据的固定大小窗口用作字典，并且在压缩过程中替换了一些单词/短语通过引用窗口中以前看到的单词/短语。

让我们考虑单词形式的输入数据

abracadabra

并假设窗口可以与输入数据一样大。然后我们可以将“abracadabra”表示为

abracad(-7,4)

这里我们假设字母是按原样复制的，括号中的两个数字的含义是“从我们现在的位置返回 7 个位置并从那里复制 4 个符号”，它再现了“abra”。

这是任何 LZ77 压缩器的基本理念。现在，魔鬼在细节中。请注意，原始单词“abracadabra”包含 11 个字母，因此假设 ASCII 表示该单词，它的长度为 11 个字节。我们的新表示包含 13 个符号，所以如果我们假设相同的 ASCII 表示，我们只是扩展了原始消息，而不是压缩它。可以证明，这有时会发生在任何压缩机上，无论它实际上有多好。

因此，压缩效率取决于存储未压缩字母和反向引用信息的格式。最初描述 LZ77 算法的原始论文（Ziv, J. & Lempel, A. (1977) A universal algorithm for sequence data compression. IEEE Transactions on information Theory, 23(3), 337-343）使用以下格式可以在这里粗略地描述为

(0,0,a)(0,0,b)(0,0,r)(0,1,c)(0,1,d)(0,3,a)

因此，压缩数据是由三个项目组成的组序列：缓冲区中要复制的绝对（不是相对！）位置、字典匹配的长度（0 表示未找到匹配）以及匹配后的字母. 由于大多数字母与字典中的任何内容都不匹配，因此您可以看到，除了非常可压缩的数据之外，这不是一种特别有效的格式。

这种低效率很可能是 LZ77 的原始形式没有用于任何实际压缩机的原因。

“LZSS”中的 SS 指的是一篇试图用滑动窗口概括字典压缩思想的论文（Storer, JA & Szymanski, TG (1982)。通过文本替换进行数据压缩。Journal of the ACM, 29(4 ), 928-951）。该论文本身着眼于 Windows 字典压缩方案的几种变体，因此再一次，您不会在其中找到明确的“算法”。但是，大多数人使用术语 LZSS 来描述带有标志位的字典压缩方案，例如将“abracadabra”描述为 |0a|0b|0r|0a|0c|0a|0d|1-7,4| 为了清楚起见，我在其中添加了垂直线。在这种情况下，数字 0 和 1 实际上是前缀位，而不是字节。前缀位 0 表示“将下一个字节按原样复制到输出中”。前缀位 1 表示“接下来是复制匹配的信息”。没有什么是真正具体的，术语 LZSS 用于说明这些前缀信号位的使用的具体情况。希望您能看到如何紧凑地完成此操作，