Расчёт энтропии:
$$H=-\sum _i{p}_i{\log }_2{p}_i=-(0.5{\log }_{2}0.5+0.25{\log }_{2}0.25+0.125{\log }_{2}0.125+0.125{\log }_{2}0.125)$$ $$=-(0.5(-1)+0.25(-2)+0.125(-3)+0.125(-3))=0.5+0.5+0.375+0.375=1.75\text{бит/символ}.$$
Минимальная средняя длина кодового слова:
- Для префиксных кодов верно неравенство $H\le L<H+1$.
- Для данного распределения оптимальный Хаффманов код даёт длины $[1,2,3,3]$ (например: символы с вероятностями $0.5,0.25,0.125,0.125$ кодируются как $0,10,110,111$), поэтому средняя длина
$$L=0.5\cdot 1+0.25\cdot 2+0.125\cdot 3+0.125\cdot 3=1.75\text{бит/символ}.$$ Таким образом здесь $L=H$ — Хаффман достигает теоретического минимума.
Связь между энтропией и сжатием данных (кратко):
- Энтропия $H$ — теоретический нижний предел средней длины кода (с учётом бит/символ) для источника без памяти.
- Практическая эффективность сжатия определяется тем, насколько средняя длина кода близка к $H$; избыточность = $L-H$.
Когда практические кодировщики приближаются к пределу:
- Хаффман: оптимален среди префиксных (целочисленные длины). Он достигает $H$ ровно, если все вероятности равны степеням $2^{-l}$ (как в вашем примере). В общем даёт гарантированно $H\le L<H+1$.
- Арифметическое (или стохастическое) кодирование: может приближать $H$ сколь угодно близко при кодировании длинных блоков символов или при высокой точности представления дробных длин; для блочного кода среднего размера избыточность на символ убывает с ростом блока и стремится к нулю ($L_n/n\to H$ при $n\to \infty$).
- Практические ограничения: конечная длина блоков, вычислительная точность, модель (ошибки в оценке вероятностей), требования к задержке и памяти; они определяют, насколько близко реально можно подойти к $H$.
Коротко: здесь $H=1.75$ б/симв, минимальная средняя длина префиксного кода также $1.75$ б/симв; в общем арифметическое кодирование и блочное кодирование позволяют добиваться уровня, близкого к $H$, при росте размера блока или точности.