3 c compression difference lz77
LZSS有人可以解释一下和算法之间的区别吗LZ77？我在网上查了几个小时，但找不到区别。我找到了LZ77算法并且了解了它的实现。
但是，与 有何LZSS不同LZ77？假设我们有一个字符串，"abracadabra"如何以LZSS不同的方式压缩它LZ77？有我可以遵循的 C 伪代码吗？
感谢您的时间！
小智 5
不幸的是，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 forequential 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 用于表示有关这些前缀信号位的使用的特定内容。希望您能看到如何紧凑地完成此操作，实际上比 LZ77 论文中描述的格式更有效。