LZSS与LZ77压缩差异

Question

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

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

谢谢您抽时间见我!

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)概括字典压缩思想的论文。本文本身研究了几种不同的带有windows的字典压缩方案，因此，您再一次不会在其中找到明确的“算法”。然而，大多数人使用术语LZSS来描述带有标志位的字典压缩方案，例如，将"abracadabra“描述为|0a|0b|0r|0a|0c|0a|0d|1-7,4|其中我纯粹为了清楚起见添加了竖线。在这种情况下，数字0和1实际上是前缀位，而不是字节。前缀位0表示“按原样将下一个字节复制到输出中”。前缀位1表示“下一步跟随复制匹配的信息”。没有什么是真正具体的，术语LZSS用于表示关于这些前缀信号比特的使用的具体信息。希望您能看到这是如何简洁地完成的，实际上比LZ77论文中描述的格式高效得多。