- Энтропия источника:
$$H=-\sum p_i{\log }_2{p}_i=-(0.7{\log }_{2}0.7+0.2{\log }_{2}0.2+0.1{\log }_{2}0.1)\approx 1.1568\text{бит/символ}.$$
- Оптимальный префиксный (Хаффманов) код: объединяем $B(0.2)$ и $C(0.1)$ в узел $0.3$, получаем код
$$A:0,B:10,C:11.$$
- Средняя длина кода:
$$L=0.7\cdot 1+0.2\cdot 2+0.1\cdot 2=1.3\text{бит/символ}.$$
- Избыточность по сравнению с энтропией:
$$R=L-H\approx 1.3-1.1568=0.1432\text{бит/символ},$$ эффективность $H/L\approx 0.889$ (≈88.9%). Утверждение для префиксных кодов: $H\le L<H+1$ — здесь выполняется.
- Когда арифметическое кодирование предпочтительнее и почему (кратко):
- Когда нужно приблизиться как можно ближе к энтропии, особенно для коротких блоков или при дробных средних длинах: арифметическое даёт «дробные» биты в среднем и может быть значительно лучше Хаффмана.
- При больших алфавитах или сильных неравномерностях распределения; при моделировании контекстов/адаптации (P меняется) арифметика эффективнее.
- Для блочного/потокового кодирования с точным учетом вероятностей и при желании минимизировать избыточность.
- Минусы: более сложная реализация, требования к точности (или использование range coding), потенциально медленнее, чувствительна к ошибкам; в простых случаях или где важна очень быстрая/простая реализация, Хаффман может быть предпочтительнее.