Кратко о понятии:
- Энтропия источника дискретных символов задаёт среднее количество информации (в битах) на символ в идеальном кодировании и определяется как
$$H(X)=-\sum _i{p}_i{\log }_2{p}_i,$$ где $p_i$ — вероятность $i$-го символа. Энтропия — нижняя теоретическая граница среднего числа бит на символ при кодировании без потерь.
Как оценить среднюю длину оптимального префиксного кода и сравнить с реальной кодировкой — пошагово:
1) Собрать частоты и вычислить вероятности:
$$p_i=\frac{n_i}{N},$$ где $n_i$ — число вхождений символа $i$, $N$ — всего символов.
2) Вычислить энтропию:
$$H=-\sum _i{p}_i{\log }_2{p}_i\text{(бит/символ)}.$$
3) Нижняя и достижимая оценка для префиксных кодов:
$$H\le L^{\ast }<H+1,$$ где $L^{\ast }$ — средняя длина оптимального префиксного (целочисленного) кода. Конструкции:
- Шенноновский код с длинами $l_i=\lceil -{\log }_2{p}_i\rceil$ даёт среднюю длину $\sum p_i{l}_i$ и укладывается в указанную границу.
- Алгоритм Хаффмана даёт оптимальный префиксный код (минимизирует среднюю длину среди целочисленных длин).
- Аритметическое кодирование или блочное кодирование позволяют приблизиться к $H$ сколь угодно близко (снижение избыточности при увеличении блока).
4) Оценить существующую кодировку: если код присваивает символу длину $l_i^{(exist)}$, средняя длина
$$L_{exist}=\sum _i{p}_i{l}_i^{(exist)}.$$ Сравнения:
- избыточность (редундантность) в бит/символ:
$$R=L_{exist}-H.$$ - эффективность (доля энтропии в средней длине):
$$\eta =\frac{H}{L_{exist}}.$$ - ожидаемый объём сжатых данных для текста длины $N$: $\text{bits}=N\cdot L$.
Небольшой числовой пример:
- Частоты: $A:50,B:30,C:20$ ($N=100$), тогда
$$p_A=0.5,p_B=0.3,p_C=\mathrm{0.2.}$$ Энтропия:
$$H=-0.5{\log }_{2}0.5-0.3{\log }_{2}0.3-0.2{\log }_{2}0.2\approx 1.4855\text{бит/симв.}$$ Шенноновские длины $l=\lceil -{\log }_{2}p\rceil$ дают $l_A=1,l_B=2,l_C=3$ и среднюю длину
$$L_S=0.5\cdot 1+0.3\cdot 2+0.2\cdot 3=\mathrm{1.7.}$$ Хаффман даёт $l_A=1,l_B=2,l_C=2$ и
$$L_{Huff}=0.5\cdot 1+0.3\cdot 2+0.2\cdot 2=\mathrm{1.5.}$$ Сравнение: избыточность $R_{Huff}=1.5-1.4855\approx 0.0145$ бит/симв, эффективность $\eta \approx 0.9903$ (99.03%). Для ASCII (8 бит/симв) избыточность ≈$6.5145$ бит/симв.
Практическая инструкция для реального текста:
- подсчитать частоты (байты/символы/глифы),
- вычислить $p_i$ и $H$,
- посчитать $L_{exist}=\sum p_i{l}_i^{(exist)}$ если известны длины текущей кодировки,
- построить Хаффман (или арифметическое кодирование) и получить $L_{opt}$,
- сравнить по $R$ и $\eta$, вычислить предполагаемую сэкономленную длину $N\cdot (L_{exist}-L_{opt})$ бит.
Это и есть полная методика оценки и сравнения.