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

Question

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

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

这是一段说明这样一个文本存在的事实:

Our compression algorithm as described so far is greedy: Any repeat of length 3 or more is reported and employed right away. Sometimes this is not optimal: We could have an [m₁, k₁] repeat in position p, and an [m₂, k₂] repeat in position p+1 or p+2, with k₁ << k₂. Thus a non-greedy algorithm may result in improved compression.

(original image)

Answer 1

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