Энтропия и компрессия

Я знаю, что вы нихуя ту мою статью не читали, поэтому вкратце напомню - энтропия есть мера равномерности вероятностей системы. Чем больше перевес в сторону одного исхода относительно других, тем система предсказуемей - энтропия ниже. Энтропия идеального генератора случайных чисел, например, равна количеству битов на выходе.

С такой формулировкой, определение "энтропия есть мера хаоса" должно быть чуточку яснее: чем менее хаос упорядочен, тем более он, собственно, хаос. Шото типа холод - отсутствие тепла.

Сжатие - тема социально-значимая. Изначально мысль у меня возникла, когда с кодировкой Хаффмана игрался. Эффективность компрессии напрямую зависит от частотного распределения символов: чем больше разброс, тем эффективнее сжатие получается. Ну, то есть, чем более предсказуема система, или же чем больше дисперсия в распределении. ЧЕМ ВЫШЕ ГОРБИК НА ГРАФИКЕ. А это значит, что чем ниже энтропия строки, тем эффективнее можно провести сжатие.

Но как мера хаоса меняется при сжатии? Да никак. Если в строке одни символы доминируют над другими, тогда энтропия символа в такой строке ниже, чем количество бит, которыми он закодирован. Компрессор же лишь приближает количество бит символа к его энтропии.

Например, если у нас в ASCII строке идут 70 байт "а" и 30 байт "б", то P("a") = 0.7, P("б") = 0.3. Тогда энтропия равна 0.7*(-log 0.7) + 0.3*(-log 0.3) ≈ 0.88 бит. Это значит, что вместо использования фиксированного кодпоинта 8 бит шириной (на самом деле 7 + неиспользованный старший), мы можем закодировать каждый символ, используя всего ~0.88 бит. Коэффициент сжатия 9х!

Здесь, конечно, есть свои нюансы. Во-первых, биты не делятся. Поразительные умозаключения. Во-вторых, реальная жизнь трудна и полна разочарований. Всё.

Да и нельзя сказать, что это универсальное определение задачи компрессора. Энтропия и кодировка не являются равнозначными. Например, строки abababababab и ajftblkqnsmp имеют одинаковую энтропию, если принимать алфавит {a, b} для первой строки и {a, j, f, t, ...} для второй, поскольку каждый символ алфавита встречается ровно один раз. Но чтобы описать первую строку, нам понадобится лишь сказать, что ab повторяется 6 раз. Со второй строкой дела обстоят сложнее. Это называется колмогоровская сложность: количество ресурсов, необходимых для описания объекта.

Кодировка Хаффманна неплохо справится с обеими строками. Но если взять, например, английский алфавит и продублировать его несколько раз, тогда гораздо лучше справился бы lz77. Он ищет повторяющиеся последовательности (с ретроспективой в 32768 байт и плавающим окном) и подменяет их неким указателем - парой (offset, len), что довольно дёшево. Тогда коэффициент сжатия будет равен количеству дубликатов алфавита, минус полшишечки поправки на размер самой пары.

В общем-то, поэтому и существует целая куча разных компрессоров. Каждый работает по-своему, со своими плюсами и минусами. Основным плюсом, конечно же, считается вычислительная сложность. Перф, братцы, чиселки надо! Чиселки сами себя не вотэтовот!