Оптимальный префиксный код (Хаффман):
- Один из оптимальных кодов: $a\mapsto 0,b\mapsto 10,c\mapsto 11$.
Энтропия источника:
$$H=-\sum _{x\in \{a,b,c\}}p(x){\log }_{2}p(x)=-\frac{1}{2}{\log }_2\frac{1}{2}-\frac{1}{4}{\log }_2\frac{1}{4}-\frac{1}{4}{\log }_2\frac{1}{4}=\frac{1}{2}+\frac{1}{2}+\frac{1}{2}=1.5\text{бит/символ}.$$
Средняя длина кода:
$$L=\sum _{x}p(x)\ell (x)=\frac{1}{2}\cdot 1+\frac{1}{4}\cdot 2+\frac{1}{4}\cdot 2=1.5\text{бит/символ}.$$ Здесь $L=H$, значит полученный префиксный код достигает энтропии (нулевая избыточность).
Пределы сжатия и общие неравенства:
$$H\le L<H+1$$ (для кодов на отдельных символах). Для блочных кодов длины $n$ выполняется
$$\frac{H(X^n)}{n}\le L_n<\frac{H(X^n)}{n}+\frac{1}{n},$$ и при $n\to \infty$ можно приближаться к энтропийной скорости источника.
Как меняются выводы при добавлении коррелированных символов:
- При наличии корреляций полезна не односимвольная статистика, а условная/блочная: энтропийная скорость равна ${\lim }_{n\to \infty }H(X^n)/n$ и может быть меньше энтропии одиночного распределения.
- Хаффман, построенный на одном символе, не использует корреляцию; чтобы её учесть, кодируют блоки (блочный Хаффман) или применяют адаптивные/арифметические методы с моделью контекста. При блочном кодировании неэффективность на символ падает не более чем на $1/n$.
- Пример: если второй символ однозначно определяется первым, условная энтропия $H(Y|X)=0$ и энтропийная скорость уменьшится вдвое по сравнению с энтропией по одиночному распределению; это даёт возможность дополнительного сжатия ниже $H$ одиночного распределения, но не ниже энтропийной скорости источника.
Краткий вывод: для заданных вероятностей оптимальный префиксный код приведён выше, он достигает энтропии $1.5$ бит/символ; при наличии корреляций следует учитывать условную/блочную энтропию и применять блочные или статистические методы кодирования, чтобы приблизиться к реальной энтропийной скорости.