Несколько дней назад на Хабре была опубликована статья Энтропия и WinRAR. В ней замечены некоторые неточности, на которые хочется дать развернутый ответ.
Начну с простого — картинка «степень сжатия различных данных». Вот она:
Удивительно, что случайная последовательность чисел сжимается где-то до 60% от исходного объема. Я точно помню, в молодости пытался зиповать сжатое видео и картинки в jpg. Архивы получались практически такого же объема, как оригинал, а иногда и на пару процентов больше! К сожалению, автор статьи не очень подробно описал, как именно он получил свой результат. Степень сжатия его последовательности случайных чисел подозрительно похожа на отношение 10/16 = 0.625.
Я попробовал воспроизвести эксперимент своими силами. Я генерировал файл со случайными символами, а потом сжимал его тем самым winRar’ом, упомянутым в заголовке. Результат таков:
| Размер файла | Размер архива |
|---|---|
| 1 000 000 байт | 1 002 674 байт |
| 100 000 байт | 100 414 байт |
| 10 000 байт | 10 119 байт |
Как вы видите, при случайно сгенерированной последовательности данных размер архива больше, чем размер исходного файла, что и следовало ожидать.
Забавное наблюдение: для генерации файла я написал небольшую программу на java. Собственно генерация производилась командой
dataOutputStream.writeChar((int) (Math.random() * 65536));
Поясню: в Java поддерживается юникод, поэтому тип char занимает 2 байта. То есть представляет собой число от 0 до 65535. Math.random() дает число от 0 до 1, домножением на коэффициент получается случайный символ, который может с равной вероятностью оказаться любым доступным символом.
Забавное наблюдение: сначала программа была написана с ошибкой, вместо 65536 стояло 16536. В результате файл со случайными символами сжимался до 95% от оригинала. В принципе, это тоже ожидаемый результат. Проверим его по формуле.
Я воспользуюсь формулой, приведенной в оригинальной статье:
Мы считаем, что символы в нашем файле появляются независимо. На каждой позиции возможно 16536 разных символа, вероятность каждого исхода одинакова и равна. Значит сумма вычисляется так:
H = — (1/16536 * log(1/16536)) * 16536 = 14
Здесь и далее логарифм берется по основанию 2.
Однако архиватор позволяет использовать все 65536 значений на каждые 2 байта. Энтропия на символ архива составляет
H = — (1/65536 * log(1/65536)) * 65536 = 16
Отношение энтропий 14/16 = 0.875 – немного меньше, чем 0.95, полученные в результате архивирования – тоже вполне закономерный результат.
Я подозреваю, что автор оригинальной статьи генерировал цифры в десятичной системе, а после сжатия эти цифры кодировались в 16-ричном формате. Это позволяет архиватору сжать данные в отношении, которое стремится к 10/16.
Второй момент, который хотелось бы прокомментировать. Как вы заметили, в формуле энтропии фигурирует такая величина, как вероятность получения того или иного значения. Мне кажется, с этой вероятностью не все так очевидно, и она достойна отдельной большой статьи. Я только что рассмотрел простейший случай, когда все символы в нашем сообщении не зависят друг от друга, каждое значение появляется случайно. В этом случае все просто: мы можем говорить о вероятности появления каждого значения. Если файл генерируется, мы можем задать эту вероятность. Если файл приходит извне – мы можем измерить частоту появления каждого символа и, при достаточно длинном сообщении, она будет стремиться к вероятности.
Однако в реальности все не так просто. Возьмем для примера текст – связные предложения на человеческом языке. Если рассматривать его как поток независимых букв, можно заметить, что буквы имеют разную частоту, им можно сопоставить вероятность и достичь некой степени сжатия. Однако в естественном языке некоторые пары и тройки букв практически не встречаются – на этом основана работа, например, всем известного PuntoSwitcher’а. Т.е. вероятность появления текущей буквы зависит от того, что было до нее. Это позволяет снизить неопределенность и достичь еще большей степени сжатия. Можно двигаться дальше: текст состоит из слов. Словарный запас автора текста наверняка не превышает 4096 слов, что даст 12 бит на слово. Сюда надо добавить 3 бита на около 8 падежей или спряжений – итого 15 бит. Среднее слово русского языка состоит из 6 букв – это 48 бит в ASCII либо 96 бит в юникоде. Кстати, одни слова встречаются чаще других, то же с падежами – значит, среднее количество бит на слово будет еще меньше (редкие слова можно кодировать более длинной последовательностью бит, а частые – более короткой).
Но это еще не все. Мы можем перейти на уровень предложений – это даст возможность предсказать, какое слово наиболее вероятно последует за предшествующими, и, таким образом, еще больше уменьшить энтропию сообщения.
Не надо думать, что все эти сложности характерны только для естественных текстов. В статье, которую я комментирую, автор сжимал последовательность символов числа Пи. В этой последовательности нет ни одного случайного символа, и высокоинтеллектуальный архиватор мог бы это распознать. В таком случае архив любого количества символов числа Пи представлял бы собой, к примеру, такую запись:
[формула вычисления символов числа Пи][количество символов]
Как видно, длина этой записи будет расти логарифмически по отношению к длине исходной последовательности (для кодирования 999 символов требуется записать формулу + 3 десятичных цифры, а для кодирования 9999 символов – на 1 десятичную цифру больше, дополнительный символ потребуется для записи «9999»). Поделим длину «архива» на длину исходной последовательности, чтобы получить степень сжатия и оценить энтропию на символ. Это отношение будет стремиться к нулю при росте длины исходной последовательности, как и должно быть для неслучайных исходных данных. Да, распаковка такого архива потребует неких вычислительных ресурсов, но ведь и обычные архивы распаковываются не сами собой.
Все сказанное отнюдь не опровергает формулу по вычислению энтропии, а просто иллюстрирует, какие фокусы могут скрываться за буквой p, обозначающей вероятность.
Автор: Oleg_Sh
