Энтропия:
$$H=-\sum _{x\in \{A,B,C\}}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.4854754\text{бит/симв.}$$
Средняя длина оптимального префиксного (Хаффмана) кода:
- Объединяем наименьшие вероятности $0.2$ и $0.3$ в узел $0.5$. Тогда длины: для символа с $p=0.5$ — $l=1$, для остальных — $l=2$.
$$\bar{L}=0.5\cdot 1+0.3\cdot 2+0.2\cdot 2=1.5\text{бит/симв.}$$
Эффективность и избыточность:
$$\eta =\frac{H}{\bar{L}}\approx \frac{1.4854754}{1.5}\approx 0.9903(99.03\%)$$ $$\bar{L}-H\approx 0.0145246\text{бит/симв.}$$
Как меняется эффективность при корреляциях:
- При наличии корреляций у источника релевантной величиной является энтропийная скорость
$$H_{\mathrm{rate}}=\underset{n\to \infty }{\lim }\frac{1}{n}H(X^n).$$ Для стационарной марковской цепи 1-го порядка
$$H_{\mathrm{rate}}=\sum _{i,j}p(i,j)(-{\log }_{2}p(j\mid i)).$$ - Корреляции обычно уменьшают энтропийную скорость ($H_{\mathrm{rate}}<H$), значит потенциально можно сжать лучше, чем при покоординатном кодировании.
- Символ-о-символ Хаффман (как рассчитанный выше) не использует корреляции и даёт в среднем $\bar{L}=1.5$ б/симв; чтобы приблизиться к $H_{\mathrm{rate}}$, нужно кодировать блоки или использовать условное/контекстное кодирование (блочный Хаффман, условный Хаффман, арифметическое кодирование, модели контекста).
- Выигрыш в сжатии равен разности $H-H_{\mathrm{rate}}$ (или, в общем, взаимной информации между символами и их контекстом).