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. 

Что здесь имеется в виду? И почему нет возможности сжимать строки alllength-n меньше, чем n бит?

Спасибо всем.

Answer 1

Существует 2^n различных случайных строк длины n. Чтобы их распаковать, алгоритм сжатия должен сжать их все в разные сжатые версии: если две разные n-длинные строки сжимаются до одной и той же последовательности, не было бы способа определить, из каких из них нужно выполнить распаковку. Если бы все были сжаты до строк длиной k < n, было бы только 2^k < 2^n различных сжатых строк, и поэтому должны были быть случаи, когда две разные строки сжимались до одного значения.

Обратите внимание, что при любых обстоятельствах не существует практически гарантированной оптимальной схемы. Если я знаю, что длинная, по-видимому, случайная последовательность - это вывод шифрования потока с ключом, я также знаю, что я могу описать его, предоставив только схему шифрования и ключа, но для сжатия может потребоваться много времени алгоритм для разработки того, что длинная, по-видимому, случайная последовательность может быть сжата чрезвычайно таким образом.