Сжатие данных: от кодов Хаффмана до предела Шеннона

simulation intermediate ~12 min
Загрузка симуляции...

Формула

\text{Compressed size} \geq N \cdot H \text{ bits}
\text{Compression ratio} = \frac{\text{Original size}}{\text{Compressed size}}
H \leq \bar{L} < H + 1 \quad \text{(single-symbol Huffman)}
\frac{H}{k} \leq \bar{L}_k < \frac{H}{k} + \frac{1}{k} \quad \text{(block-}k\text{ Huffman)}
Каждый раз, когда вы отправляете фото, транслируете видео или скачиваете файл, алгоритмы сжатия незаметно работают — сводя данные к их сущностному информационному содержанию. Теоретический фундамент всего этого — теорема Шеннона о кодировании источника. Теорема утверждает замечательный факт: для любого источника, порождающего символы с энтропией H бит на символ, невозможно сжать данные без потерь ниже N·H суммарных бит (где N — длина сообщения), но можно приблизиться к этому пределу сколь угодно близко. Энтропия, таким образом, является абсолютным эталоном сжатия. Кодирование Хаффмана, изобретённое Дэвидом Хаффманом в 1952 году, будучи аспирантом MIT, предоставляет практический алгоритм, приближающийся к этому пределу. Ключевая идея — кодирование переменной длины: присваивать короткие двоичные кодовые слова частым символам и длинные — редким. Алгоритм строит оптимальный префиксный код, возводя двоичное дерево снизу вверх, объединяя два наименее вероятных символа на каждом шаге. Этот симулятор генерирует сообщения из четырёх различных типов источников с совершенно разными профилями энтропии. Текст, подобный английскому, имеет неравномерные частоты букв (E — 13%, Z — 0,07%), что даёт энтропию около 4,0 бит — значительно ниже максимума в 4,7 бит для 26 букв. Случайный текст практически несжимаем. Повторяющийся текст имеет очень низкую энтропию и сжимается драматически. Последовательности ДНК с четырьмя примерно равными основаниями имеют около 2 бит на основание. Блочное кодирование расширяет принцип, рассматривая группы символов как единые единицы. Поскольку реальные источники имеют межсимвольные зависимости (в английском за «q» почти всегда следует «u»), совместное кодирование блоков символов улавливает эти корреляции и приближает сжатие к истинной скорости энтропии.

Частые вопросы

Как работает кодирование Хаффмана?

Кодирование Хаффмана присваивает более короткие двоичные коды частым символам и более длинные — редким. Алгоритм строит двоичное дерево снизу вверх: многократно объединяя два узла с наименьшими частотами, пока не останется одно дерево. Символы на неглубоких листьях получают короткие коды; глубокие листья — длинные. Результат — префиксный код (ни одно кодовое слово не является префиксом другого), минимизирующий ожидаемую длину кода для данного частотного распределения.

Что такое теорема Шеннона о кодировании источника?

Теорема Шеннона о кодировании источника (теорема о бесшумном кодировании) утверждает, что источник с энтропией H бит на символ нельзя сжать без потерь ниже H бит на символ в среднем. И наоборот, можно сжать до скорости сколь угодно близкой к H, используя достаточно длинные блочные коды. Тем самым энтропия устанавливается как фундаментальный предел сжатия без потерь.

Почему нельзя сжать случайные данные?

Истинно случайные данные имеют максимальную энтропию — все символы равновероятны и паттернов нет. Поскольку энтропия равна log₂(N) для N равновероятных символов, сжатый размер равен исходному. По принципу голубятни любая схема сжатия, укорачивающая одни входы, должна удлинить другие. Для равномерно случайных данных ни один вход не вероятнее другого, поэтому систематическое сжатие невозможно.

Чем отличается сжатие без потерь от сжатия с потерями?

Сжатие без потерь (Хаффман, LZ77, DEFLATE) сохраняет каждый бит исходных данных — распакованный выход идентичен входу. Сжатие с потерями (JPEG, MP3, H.264) отбрасывает информацию, считающуюся перцептивно незначимой, достигая гораздо более высоких коэффициентов сжатия ценой точности. Теорема Шеннона о кодировании источника описывает сжатие без потерь; теория скорость–искажение описывает сжатие с потерями.

Источники

Другие симуляции: Теория информации

simulation

Исследователь пропускной способности канала
simulation

Симулятор коррекции ошибок
simulation

Калькулятор энтропии Шеннона
View source on GitHub