algorithm - ziv lempel效率可以通过压缩更长的重复来提高吗

Question

我有一个问题 - 我被介绍给 Ziv-Lempel 的一个版本，它只编码大小为 3 或更长的重复（不编码 1 或 2 个字符的重复 - 字符本身被放置到编码字符串而不是 (m ,k) 值)。有人问我是否可以提高 ziv Lempel 编码效率（就编码字符串的长度而言 - 而不是时间复杂度）。

我认为就编码字符串的长度而言 - 可能存在以下情况：不在位置 p 编码 3 长度重复，而是编码从位置 p+1 或 p+2 开始的重复可能会产生更好的结果 - 这也出现在我读到的理论中：我添加了一张相关段落的照片，仅说明了这一点（但没有给出示例）。到目前为止，我设法找到的每个示例都是编码长度为 3 的重复的代码也可以检测到的示例。

这是一段谈到存在这样一个文本的事实：

到目前为止，我们描述的压缩算法是贪婪的：任何长度为 3 或更多的重复都会立即报告并使用。有时这不是最优的：我们可以在 p 位置重复一个 [ m 1 _, k 1 _]，在p +1 或p +2位置重复一个 [ m ₂ , k ₂ ] ，其中k ₁ << k ₂。因此，非贪心算法可能会导致改进的压缩。

（原图）

Answer 1

是的。gzip 和 zlib 的 deflate 算法使用“惰性”匹配，它将发出匹配的决定推迟到下一个字符，以便查看那里是否有更长的匹配。这绝对是一场胜利。

Answer 2

这在技术上称为 LZ 非贪婪解析方法。正如马克所提到的， gzip 使用that，但仅用于 p+1 跳过。

在本文档中，您将找到更多具有 LZ 算法该特性的多个详细信息的通用编码器。