LZSS与LZ77压缩的区别

Question

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

但是，LZSS与LZ77有什么不同呢？假设我们有一个字符串"abracadabra"，LZSS如何与LZ77不同地压缩它？是否有C伪代码可以遵循？

谢谢您的时间！

- user12208476

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 sequential 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, J. A. & Szymanski, T. G. (1982). Data compression via textual substitution. Journal of the ACM, 29(4), 928-951）。该论文研究了几种具有窗口的字典压缩方案的变体，因此，在其中你不会找到一个明确的“算法”。然而，大多数人使用术语“LZSS”来描述带有标志位的字典压缩方案，例如将“abracadabra”描述为 |0a|0b|0r|0a|0c|0a|0d|1-7,4| 在这种情况下，数字0和1实际上是前缀位，而不是字节。前缀位0表示“将下一个字节按原样复制到输出中”。前缀位1表示“接下来是用于复制匹配项的信息”。除此之外，没有其他具体内容，“LZSS”这个术语用于描述这些前缀信号位的使用。希望您能看出如何紧凑地完成这个过程，事实上比LZ77论文中描述的格式更有效率。

- introspec