Кратко — формула, смысл, применение и контрпримеры.
Что такое энтропия Шеннона
- Для дискретной случайной величины $X$ с распределением $p(x)$ энтропия равна
$$H(X)=-\sum _{x}p(x){\log }_{2}p(x).$$ Это среднее минимальное число бит на символ, необходимое для кодирования символа при знании распределения.
- Для стационарного источника последовательностей вводят энтропию-скорость
$$H=\underset{n\to \infty }{\lim }\frac{1}{n}H(X_1^n),$$ — она даёт нижнюю границу на среднее число бит на исходный символ при бесконечно долгих последовательностях.
Теоретическое применение к сжатию
- Теорема кодирования: для источника с энтропией-скоростью $H$ существует код с средней длиной на символ, стремящейся к $H$ бит, и ни один код не может в среднем опустить значение ниже $H$.
- На практике энтропия используется как эталон: она даёт нижнюю границу сжатия и помогает проектировать модели вероятностей для арифметического/энтропийного кодирования (Huffman, арифметика, ANS и т.д.).
Почему уменьшение энтропии не всегда ведёт к хорошему сжатию (примеры)
1) Наличием накладных расходов и малых блоков:
- Идеальный размер сжатого сообщения длины $n$ символов — примерно $nH$ бит. Но реализуемый файл содержит постоянные накладные данные (заголовки, модель, словарь) размером $B$ бит. Если $B$ соизмерим или больше $nH$, реальный файл может быть больше необжатого.
- Пример численно: $n=10$ байт $=80$ бит. Пусть энтропия уменьшилась с $H_1=6$ до $H_2=2$ бит/байт. Идеальные размеры: $10\cdot 6=60$ бит и $10\cdot 2=20$ бит. Но если кодер добавляет модель/заголовок $B=160$ бит (20 байт), реальные размеры будут $220$ и $180$ бит — оба больше исходных $80$ бит. То есть уменьшение энтропии не помогло из‑за накладных расходов.
2) Ограничения моделирования и вычислительные ресурсы:
- Энтропия-скорость часто предполагает оптимальную модель (возможно бесконечную память). Практические кодеры имеют ограниченную память/окно и не улавливают длинные корреляции. Источник может иметь очень низкую асимптотическую энтропию (длинная периодичность), но сжатие с окном длины $W$ не использует эти корреляции и даёт худший результат.
- Иными словами: теоретический $H$ мало достижим при ограниченных ресурсах.
3) Неправильная оценка энтропии (модельное несоответствие):
- Если энтропия вычислена при неверной модели (например, считаем символы независимыми, хотя есть зависимости), то оценка может уменьшиться при применении неадекватной трансформации, но реальный кодер не сможет эффективно воспользоваться этой «меньшей» энтропией.
- Также преобразования данных (например, нелинейная перестановка) могут уменьшать эмпирическую энтропию статистически, но переводить данные в форму, менее пригодную для конкретного алгоритма сжатия.
4) Практические ограничения кодов (целочисленность, блочное кодирование):
- Хаффман-код даёт целые числа бит на символ; при коротких алфавитах/малых частотах разница между $H$ и целочисленным кодированием может быть существенной.
- Блочное кодирование или квантование коэффициентов в мультимедийных кодеках может снизить энтропию в одной метрике, но разрушить структурные признаки, которые кодер использует для эффективной компрессии.
Короткое руководство
- Энтропия — фундаментальная нижняя граница; она показывает идеал, но не гарантирует достижимость в реальных условиях.
- При оценке сжимаемости всегда учитывайте накладные расходы, размер блока/файла, ограничения модели и вычислительные ресурсы.