你能给我一些LZ77算法的解释吗？

Question

我正在和朋友学习LZ77算法，有些情况让我们感到困惑。

例如）

初始化

搜索缓冲区大小：7
前瞻缓冲区大小：8
原始字符串：abcabbcabbcabca

当前 window: abcabbc 查看：abcabca

我认为 LLD 元组是：字面量：'a' 长度：4 距离：4

我朋友认为 LLD 元组是什么：字面量：'c' 长度：6 距离：4

我以为查找最长匹配字符串的算法只检查搜索缓冲区，但他说查找匹配字符串没有限制。

谁的答案是正确的？

Answer 1

我不能给你一个明确的答案，但我可以证明 LZ77 没有理由不支持“过长”的元组。

我相信你是在问元组的长度分量是否可以大于它的距离分量。

换句话说，我相信您是在问将生成以下哪些元组流：

（长度：0，距离：0，字符：'a'）
(0,0,'b')
(0,0,'c')
(2,3,'b')
(4,4,'c')^[1] 长度以距离为上限。
(2,4,'c')
(0,0,'a')

或

(0,0,'a')
(0,0,'b')
(0,0,'c')
(2,3,'b')
(7,4,'c')^[2]长度大于距离。
(0,0,'a')

显然，后者会产生更好的压缩效果。

我不能给你一个明确的答案，但我可以证明解码器可以像编码器生成它们一样容易地处理“过长”的元组。因此，LZ77 没有理由不支持它们。

从第一个流重建输入

(0,0,'a'): "" + "a" ⇒ "a"
(0,0,'b'): "" + "b" ⇒ "ab"
(0,0,'c'): "" + "c" ⇒ "abc"
(2,3,'b'): "ab" + "b" ⇒ "abcabb"
(4,4,'c'): "cabb" + "c" ⇒ "abcabbcabbc"
(2,4,'c'): "ab" + "c" ⇒ "abcabbcabbcabc"
(0,0,'a'): "" + "a" ⇒ "abcabbcabbcabca"

简单。

正在重构来自第二个流的输入

(0,0,'a'): "" + "a" ⇒ "a"
(0,0,'b'): "" + "b" ⇒ "ab"
(0,0,'c'): "" + "c" ⇒ "abc"
(2,3,'b'): "ab" + "b" ⇒ "abcabb"

(7,4,'c')

到目前为止，我们已经制作了 abcabb。元组表示接下来的 7 个字符从 abcabb.

末尾的 4 个字符开始

a b c c a b b _ _ _ _ _ _ _ c
      | | | | ^ ^ ^ ^ ^ ^ ^
      | | | | | | | | | | |
      +-)-)-)-+ | | | ? ? ?
        +-)-)---+ | |
          +-)-----+ |
            +-------+

我们缺少三个字符！我们是吗？如果都是一个缓冲区，我们从左到右复制，我们只需要继续。

                  +-------+
                +-)-----+ |
              +-)-)---+ | |
              | | |   | | |
              | | |   v v v
a b c c a b b _ _ _ _ _ _ _ c
      | | | | ^ ^ ^ ^
      | | | | | | | |
      +-)-)-)-+ | | |
        +-)-)---+ | |
          +-)-----+ |
            +-------+

所以这不需要额外的努力！

(7,4,'c'): "cabbcab" + "c" ⇒ "abcabbcabbcabc"

(0,0,'a'): "" + "a" ⇒ "abcabbcabbcabca"

你说错了 (4,4,'a').
你说错了 (6,4,'c').

Answer 2

你的朋友是对的。一个更简单的例子是LZ77用距离1匹配完成run-length编码，长度为n-1 for a 运行 of n 相同字节的副本。（该字节的第一次出现是文字。）

你能给我一些LZ77算法的解释吗？

Could you give me some explain of LZ77 Algorithm?

c

algorithm

compression

pseudocode

lz77