Кратко и по делу.
Что такое энтропия
- Энтропия в теории информации — мера средней неопределённости или средней информации, приносимой одним исходом случайного источника. Для дискретной величины $X$ с вероятностями $\{p_i\}$ энтропия определяется как
$$H(X)=-\sum _i{p}_i\log p_i,$$ обычно берут логарифм по основанию $2$ и измеряют в битах.
Вычисление для распределения $\{0.5,0.25,0.25\}$ $$H(X)=-(0.5{\log }_{2}0.5+0.25{\log }_{2}0.25+0.25{\log }_{2}0.25)$$ $$=-(0.5\cdot (-1)+0.25\cdot (-2)+0.25\cdot (-2))=1.5\text{бит}$$ (то есть $H(X)=1.5$ бит на символ).
Связь энтропии со сжатием данных
- Энтропия даёт фундаментальную нижнюю границу средней длины кодового слова при безошибочном (lossless) сжатии: средняя длина кода $\bar{L}$ удовлетворяет $\bar{L}\ge H(X)$.
- Теорема Шеннона: для больших блоков символов можно сжимать до скорости, сколь угодно близкой к энтропии (в битах на символ) с пренебрежимо малой ошибкой.
- Для префиксных (удобных для декодирования) кодов существует оценка $H(X)\le \bar{L}<H(X)+1$.
- В данном примере оптимальный префиксный код (например, Хаффман) может дать точную среднюю длину $\bar{L}=1.5$ бит — например: символ с $0.5$ → код «0», два символа с $0.25$ → «10» и «11».
Вывод: энтропия показывает минимально возможное среднее число бит на символ при безпотерьном сжатии; практические схемы приближают эту границу.