string - 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 < n 的字符串，那么只有 2^k<2^n 个不同的压缩字符串，因此在某些情况下，两个不同的字符串将被压缩为相同的值。

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