LZ 77压缩算法

Question

我想知道如何证明Lempel ZIV 77压缩算法确实是最优压缩。

我发现了以下信息：

So how well does the Lempel-Ziv algorithm work? In these notes, we’ll
calculate two quantities. First, how well it works in the worst case, and
second, how well it works in the random case where each letter of the message
is chosen uniformly and independently from a probability distribution, where
the ith letter appears with probability pi
. In both cases, the compression
is asymptotically optimal. That is, in the worst case, the length of the
encoded string of bits is n + o(n). Since there is no way to compress all
length-n strings to fewer than n bits, this can be counted as asymptotically
optimal. In the second case, the source is compressed to length
                                 α
H(p1, p2, . . . , pα)n + o(n) = n∑(-pi log2 pi) + O(n)
                                     i=1
which is to first order the Shannon bound.

这里是什么意思？为什么没有办法将所有长度-n个字符串压缩到小于n位呢？

谢谢大家。

Answer 1

有2^n个不同长度的随机字符串，为了对它们进行解压缩，压缩算法必须将它们全部压缩到不同的压缩版本:如果两个不同的n长字符串压缩到相同的序列中，则无法判断要解压缩到哪一个。如果所有字符串都压缩到长度为k

请注意，在所有情况下都没有实际的保证最优方案。如果我知道一个明显是随机的长序列是一个带有密钥的流密码的输出，我也知道我可以通过只给出密码和密钥的设计来描述它，但是压缩算法可能需要很长的时间才能计算出长的、显然是随机的序列可以以这种方式被极大地压缩。