Энтропия и WinRAR — развернутый ответ

Несколько дней назад на Хабре была опубликована статья Энтропия и WinRAR. В ней замечены некоторые неточности, на которые хочется дать развернутый ответ.

Начну с простого — картинка «степень сжатия различных данных». Вот она:

image

Удивительно, что случайная последовательность чисел сжимается где-то до 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% от оригинала. В принципе, это тоже ожидаемый результат. Проверим его по формуле.
Я воспользуюсь формулой, приведенной в оригинальной статье:

image

Мы считаем, что символы в нашем файле появляются независимо. На каждой позиции возможно 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, обозначающей вероятность.

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 19

    +2
    Забавное наблюдение
      –2
      Не совсем понял сравнение зипования jpg и видео со случайно последовательностью — понятное дело, что и jpg, и видео, не поддаются сжатию архиватора, поскольку и то и другое специально разработанный архивный формат для сжатия картинок / последовательностей картинок. А вот TIFF (картинка без компрессии) жмется архиваторами на ура, до 20% от исходного объема.
        +6
        В статьях показывается, что минимальная компрессия соответствует максимальной энтропии которая соответствует полностью случайной последовательности. Минимальная компрессия равна нулю (даже меньше, за счёт накладных расходов), что проявляется, например, на сжатых картинках и видео. Вот автор данной статьи и недоумевает, как так получилось, что у не совсем случайных данных (jpg) компрессия ниже (а значит энтропия выше), чем у «полностью случайных данных».

        Кстати, в продолжение «высокоинтеллектуального архиватора» — «случайную» последовательность, сгенерённую на ГПСЧ также, как и ПИ можно сжать в [формула генератора][стартовое значение][длина последовательности]
          +1
          Это как архивировать архив. После сжатия, получается последовательность псевдослучайных символов. Если бы любая случайная последовательность сжималась хоть немного — такой процесс можно было бы продолжать до бесконечности, всё больше сжимая исходный файл. Сам писал архиватор, процесс знаком.

          Действительно случайные значения обещает сайт random.org, пишут про генерацию из атмосферного шума
            +5
            Автор не умеет генерировать случайные числа.
            Я скачал файл с random.org
            На странице random.org/bytes введите 16384 и Download to file.
            НЕ СЖИМАЕТСЯ!
            Не завалите radrom.org: вот ссылочка на скачанный мной файл на google drive
              0
              Прошу прощения за коммент не в тему. Поздно редактировать :(
              0
              Ну так по индукции же доказывается, что есть предел у любого алгоритма сжатия любой последовательности.
              +14
              TIFF (Tag Image Format File) — вовсе не «картинка без компрессии». Это контейнер, в котором блоки данных помечены специальными тегами (последовательностями бит). Там внутри может быть ЧТО УГОДНО, если это картинка. Внутри TIFFа может быть JPEG, JPEG2000, JBIG, CCITT group 3, 4, и тому подобное. Может быть и любой неизвестный науке (но известный программе-генератору) способ кодирования изображения — хоть deflate обычного битмапа.

              В свете сказанного мной становится очевидно, что далеко не любой tiff «жмётся архиваторами на ура».
                +1
                JPEG файлы поддаются сжатию, причем неплохо, но с помощью спец. алгоритмов
                www.maximumcompression.com/data/jpg.php

                en.wikipedia.org/wiki/StuffIt#StuffIt_Image_Format_.28SIF.29
                  0
                  Да, с помощью разбора и перепаковки арифметическим кодированием. Причём поддержка этого арифметического кодирования есть в самом jpg давно, но никто её не использует, да и не все браузеры/редакторы поддерживают. Именно это обеспечивает до 30% улучшения сжатия.
                  Из бесплатных утилит, архивирующих jpg, рекомендую PackArc.
                –7
                > Словарный запас автора текста наверняка не превышает 4096 слов

                Эллочка-Людоедка детектед?
                  +3
                  «Как подсчитали ученые-лингвисты, в русском языке около 500 тыс.слов. У великого русского поэта А.С. Пушкина, знатока и мастера языка, в литературной речи были всего 21197 слов. У выпускника средней школы словарный запас составляет в среднем от 2000 до 5000 слов, а у человека с высшим образованием — до 8000 слов.»
                  С просторов Интернета, но весьма похоже на правду.
                    0
                    Похоже, что эту новость принесли на хвосте пегасы с островов туманного Альбиона.
                    У Пушкина в литературной речи было свыше 100 тысяч слов.
                    То же самое касается и человека с высшим образованием: где-то раз в пять недопоставка.
                      0
                      активный и пассивный словарный запас сильно различаются. Хотя даже для активного цифры кажутся немного заниженными.
                        +1
                        Можно источник про Пушкина?
                    0
                    В этой последовательности нет ни одного случайного символа, и высокоинтеллектуальный архиватор мог бы это распознать.

                    А если и не распознает, то можно использовать виртуальную машину RAR.
                      0
                      А если распознает что это число Пи и запишет в таком виде — [формула вычисления символов числа Пи][количество символов] где [количество символов] = 1 000 000, то на телефоне такой, вроде бы очень маленький, архив будет очень долго открываться…
                    0
                    Считаю нужным напомнить, что не все задачи, даже требующие ответа да/нет, алгоритмически разрешимы. Описанная хитрость с числом π, в частности, очень хорошо соответствует понятию колмогоровской сложности, вычисление которой является алгоритмически неразрешимой задачей.

                    Впрочем, никто не мешает нам запомнить несколько частых «популярных» последовательностей (вроде того же π), если мы сумеем показать, что на практике и впрямь возможны ситуации, когда потребуется сжимать запись из 100 цифр какого-нибудь корня третьей степени из семи.

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое