Энтропия источника:
$$H=-\sum _{i=1}^4{p}_i{\log }_2{p}_i=-(0.6{\log }_{2}0.6+0.25{\log }_{2}0.25+0.1{\log }_{2}0.1+0.05{\log }_{2}0.05)\approx 1.49046856\text{бит/симв.}$$
Нижняя граница средней длины префиксного кода (неравенство Шеннона):
$$\bar{L}\ge H,\text{а для префиксных кодов обычно}H\le \bar{L}<H+1.$$ Здесь нижняя граница равна $H\approx 1.4905$ бит/симв.
Конкретная префиксная кодировка (Хаффман):
Построение: объединяем $0.05+0.1=0.15$, затем $0.15+0.25=0.4$, затем $0.4+0.6=1.0$. Например, кодировка
$$s_1:0,s_2:10,s_3:110,s_4:111.$$ Средняя длина этого кода:
$$\bar{L}=0.6\cdot 1+0.25\cdot 2+0.1\cdot 3+0.05\cdot 3=1.55\text{бит/симв.}$$ Избыточность относительно энтропии:
$$R=\bar{L}-H\approx 1.55-1.49046856\approx 0.05953\text{бит/симв.}$$
Сравнение с арифметическим кодированием:
- Теоретически арифметическое (или range) кодирование может приблизиться к энтропии сколь угодно близко при больших блоках: средняя скорость $\approx H$ бит/симв. — т.е. выигрыш по сравнению с данным Хаффманом около
$$\Delta \approx {\bar{L}}_{\text{Huff}}-H\approx 0.0595\text{бит/симв.}.$$ - На практике есть накладные расходы: заголовок/модель (несколько десятков бит), конечная фиксация интервала, конечная-точность арифметики. Для статической известной модели эти накладные расходы распределяются по всей последовательности; если заголовок, скажем, $\sim 32$ бит, то точка безубыточности примерно
$$N\approx 32/0.0595\approx 538\text{символов.}$$ - Для коротких сообщений Хаффман часто выгоднее (меньше накладных расходов, простая реализация). Для длинных последовательностей арифметическое даёт лучшее сжатие (приближение к $H$).
- Адаптивность: адаптивный арифметический кодер автоматически подстраивается под неизвестные распределения и обычно даёт лучшее сжатие при меняющихся частотах, чем статический Хаффман; адаптивный Хаффман проще, но обычно менее эффективен, чем адаптивный арифметический.
- Сложность: арифметическое/range сложнее и медленнее в реализации, требует аккуратной реализации и точности; Хаффман — прост и быстр.
Вывод кратко: энтропия $H\approx 1.4905$ бит/симв.; оптимальный префиксный (Хаффман) код даёт $\bar{L}=1.55$ бит/симв. (избыточность $\approx 0.0595$ бит/симв.). Арифметическое кодирование может сократить этот избыточный кусок и приблизиться к $H$, но требует большего кода/накладных расходов и более сложной реализации; при коротких сообщениях Хаффман чаще предпочтителен, при длинных — арифметическое эффективнее.