Почему рандомный шум несжимаемый?

Красивый заголовок красуется, теперь стоит добавить - в общем случае.

Возьмём все битстроки какой-нибудь длины n, да. Если это рандомный шум, то распределение униформное - вероятность встретить любую из строк 1/2^n. А компрессия это что?

Блять, вопрос вообще-то хороший. Если зайти интуицией, то вот можно представить, что строка несёт какую-то информацию. Допустим, строку можно удлинить (как тот url longener), и при этом не потерять в информативности. Размазать информацию, короче. Но тогда логично предположить, что можно пойти и в обратную сторону? Тогда для одной и той же информации можно представить целый бесконечный спектр всех строк, которыми она может быть представлена. Хотя скорее это даже луч, как нам на математике в 3 классе рассказывали, потому что у этого спектра явно есть начало. Если пустая строка и может быть дохуя информативной, то вот с отрицательной длиной как-то лыжи уже не едут.

Собственно, компрессия и есть - переместиться ближе к началу луча. Желательно.

Нижний предел длины, или же начало луча, можно оценить по среднему количеству информации в строке - оно же 2^n - оно же энтропия строки, как однажды сказал мой кумир Шеннон.

Возвращаясь к нашим строчечкам, как и было сказано - вероятность каждой составляет 1/2^n, это и есть наша энтропия. Значит, каждая битстрока длины n несёт в себе ровно столько информации, сколько в ней собственно бит. Если взять какую-нибудь одну рандомную из них и попытаться урезать ей один битик, тогда вдруг окажется, что эта урезанная строка является префиксом для второй битстроки. Это не очень приятно, особенно если мы захотим потом передавать эту информацию. Ну а как понять-то ёпта, ты получил полную n-1 строку, или нам всё-таки хотели следующим битом донести другую истину? Короче однозначность декодирования пропадает. Опыт ниже среднего.

Хорошо, от неоднозначности можно избавиться. Из всех битстрок можно построить одно большое бинарное дерево, которое сможет однозначно их определять. Напоминаю, у n-1 и n битстрок будет общий последний бит, поэтому чтобы в дереве не проебать n строку, нам придётся перейти на соседний узел от n-1 строки. Но он и так уже определяет третью битстроку. Но! Не стена, подвинется. Из терминального тот соседний узел магическим образом превращается в обычный и теперь ведёт к двум новым узлам: один для n строки, второй для той самой неудачливой третьей битстроки, которая там изначально сидела (жертва обстоятельств!). Эти два новых узла, выходит, лежат уже на n+1 глубине, а значит - теперь они кодируются n+1 битами.

Вот и выходит, что если попытаться сжать рандомную битстроку, то по итогу вылезет два лишних, и мы кончим с одним лишним битом в множестве. Сообщения от таких мувов станут только длиннее. Компрессор выходит ниже среднего.



Ремарка: сложность Колмогорова* здесь роли не играет - общая тенденция 2m новых бит для m убранных. ВСЕГДА. Даже если взять строку, состояющую полностью из нулей и сократить её до одного нуля, мы всё равно получим 2(n-m) бит оверхеда.

Сложность Колмогорова* - длина наименьшей программы (обычно машины Тьюринга), способной описать некую строку. В целом, она и классическая энтропия - две стороны одной монеты. Только эта более прикладная в контексте компрессоров.

А ещё лучше посмотрите 3b1b.