Оптимальный префиксный код (Хаффман):
- Сортируем вероятности: $0.5,0.3,0.2$. Сливаем две наименьшие $0.3$ и $0.2$ → $0.5$. Получаем дерево, дающее, например, коды
$$A\mapsto 0,B\mapsto 10,C\mapsto 11.$$
Средняя длина кода:
$$L=\sum _{x}p(x)\ell (x)=0.5\cdot 1+0.3\cdot 2+0.2\cdot 2=1.5\text{бит/символ}.$$
Энтропия источника:
$$H=-\sum _{x}p(x){\log }_{2}p(x)=-0.5{\log }_{2}0.5-0.3{\log }_{2}0.3-0.2{\log }_{2}0.2\approx 1.4855\text{бит/символ}.$$
Избыточность (редундандность) и эффективность:
$$\text{редунд.}R=L-H\approx 1.5-1.4855\approx 0.0145\text{бит/символ},\text{эффективность}=\frac{H}{L}\approx \mathrm{0.9903.}$$
Замечания об источнике с памятью (Марковская зависимость) и практические последствия:
- Для источника с памятью релевантной мерой является энтропия в единицу времени (энтропийная скорость) $H_{\infty }={\lim }_{n\to \infty }\frac{1}{n}H(X_1^n)$, для первомарковского процесса это условная энтропия $H(X_n\mid X_{n-1})$.
- Кодирование по одному символу (символьный Хаффман) игнорирует зависимости и ограничено нецелыми длинами, даёт среднюю длину $L$ с оценкой
$$H\le L<H+1$$ (для кодирования символов). Для источника с памятью эталон — энтропийная скорость, и символьный код может быть далеким от неё.
- Чтобы учесть память, применяют:
- блоковое кодирование (Хаффман по блокам длины $n$): средняя длина на символ стремится к энтропийной скорости при росте $n$, но размер алфавита растёт экспоненциально;
- контекстное/предиктивное моделирование + арифметическое кодирование или адаптивные методы (PPM, rANS, LZ): позволяют эффективно эксплуатировать зависимости и приближать среднюю длину к энтропийной скорости без целочисленных ограничений кодовых длин.
- Практические следствия: наличие памяти обычно даёт возможность достичь лучшего сжатия (меньше бит/символ), но требует модели переходов и большего вычислительного/памятного ресурса; в реальных алгоритмах (аритметическое кодирование, PPM, современные энтропийные кодеры) предпочтение отдаётся учёту контекста и адаптивному моделированию, а не простому символьному Хаффману.