1) Энтропия источника:
$H=-{\sum }_i{p}_i{\log }_2{p}_i=-(0.5{\log }_{2}0.5+0.25{\log }_{2}0.25+0.15{\log }_{2}0.15+0.1{\log }_{2}0.1)$
Вычисления:
$-0.5{\log }_{2}0.5=0.5,-0.25{\log }_{2}0.25=0.5,$ $-0.15{\log }_{2}0.15\approx 0.41055,-0.1{\log }_{2}0.1\approx \mathrm{0.33219.}$
Итого
$H\approx 0.5+0.5+0.41055+0.33219\approx 1.7427$ бит/символ.
2) Оптимальный код Хаффмана (построение кратко):
- Слияние наименьших: $0.1(D)+0.15(C)=0.25$.
- Далее узлы: $0.25(B),0.25(CD),0.5(A)$. Сливаем два 0.25 в 0.5, затем с A.
Одно возможное присвоение кодов:
A: $0$
B: $10$
C: $110$
D: $111$
3) Средняя длина кода:
$\bar{L}=\sum p_i{l}_i=0.5\cdot 1+0.25\cdot 2+0.15\cdot 3+0.1\cdot 3=1.75$ бит/символ.
Эффективность и избыток:
$\eta =H/\bar{L}\approx 1.7427/1.75\approx 0.996$.
Избыток $\bar{L}-H\approx 0.0073$ б/симв, и выполняется общая оценка $H\le \bar{L}<H+1$.
4) Когда арифметическое кодирование даёт заметное преимущество:
- При кодировании длинных последовательностей и/или при использовании сложных адаптивных моделей (контексты, условные вероятности): арифметическое кодирование может приблизиться к энтропии более плотно, т.к. даёт дробные биты на символ в среднем.
- Для больших алфавитов, сильно дробных или меняющихся вероятностей, а также когда требуется кодирование блоков символов как единого события (чтобы преодолеть ограничение целой длины кода у Хаффмана).
- Для очень малых вероятностей и редких событий (Хаффман даёт дискреteness-потери).
5) Практические сложности арифметического кодирования:
- Необходимы аккуратные методы с конечной точностью (ренормализация, работа с целыми интервалами); на практике используют range coding или адаптированные целочисленные реализации.
- Чувствительность к ошибкам: одна ошибка во внутреннем состоянии может разрушить декодирование последующей части потока.
- Требуется передача или согласование модели вероятностей (накладные расходы при коротких сообщениях).
- Сложнее и медленнее в реализации по сравнению с простым Хаффманом; исторически — патентные ограничения (сейчас в основном неактуально).
- Для очень коротких сообщений выигрыш по битам может быть пренебрежимо мал.
Кратко: для данного простого источника Хаффман почти оптимален ($\bar{L}=1.75$ против $H\approx 1.7427$). Арифметическое кодирование приносит значимое улучшение главным образом для длинных сообщений, больших/адаптивных моделей или сложных контекстов, но требует аккуратной реализации (range coding, финитная арифметика, обработка ошибок, передача модели).