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的随机串。为了对它们进行解压缩，压缩算法必须将它们全部压缩到不同的压缩版本：如果两个不同的n长的字符串被压缩到相同的序列，那么将无法分辨哪些解压缩到。如果全部被压缩为长度为k的字符串，那么将只有不同的压缩字符串，因此必须有一些情况下两个不同的字符串被压缩到相同的值。

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