Энтропия источника

Считаем, сколько информации в среднем приходится на один символ источника, а не на одно конкретное сообщение.

Энтропия источника — это средняя информация на один символ: $H=-\sum_{i=1}^{N} p_i\log_2 p_i$ бит. Она показывает, насколько источник в среднем «непредсказуем».

В прошлом уроке мы измеряли информацию одного конкретного сообщения через $-\log_2 p$. Но источник выдаёт не одно сообщение, а поток символов с разными вероятностями. Хочется одну характеристику всего источника — среднее количество информации на символ. Это и есть энтропия.

Зачем это нужно

Энтропия отвечает на практический вопрос: сколько бит в среднем нужно, чтобы закодировать один символ из этого источника? Это нижняя граница для любого алгоритма сжатия без потерь. Если энтропия русского текста около 1–1,5 бита на букву (с учётом частот и связей), то теоретически такой текст можно сжать примерно до этого предела, а ниже — нельзя без потери информации. Поэтому энтропия — ключевое понятие теории информации и регулярная тема олимпиадных и экзаменационных задач.

Энтропия как среднее

Идея проста. Каждый символ $a_i$ имеет вероятность $p_i$ и несёт собственную информацию $-\log_2 p_i$. Чтобы найти среднее, умножаем информацию каждого символа на его вероятность (как часто он встречается) и складываем:

$$ H = \sum_{i=1}^{N} p_i \cdot \bigl(-\log_2 p_i\bigr) = -\sum_{i=1}^{N} p_i \log_2 p_i $$

Это в точности формула математического ожидания собственной информации. Сумма всех вероятностей при этом равна единице: $\sum p_i = 1$.

Пример: источник из 4 символов

Пусть источник выдаёт буквы A, B, C, D с вероятностями $0{,}5$, $0{,}25$, $0{,}125$, $0{,}125$. Посчитаем вклад каждого символа:

Складываем последний столбец:

$$ H = 0{,}5 + 0{,}5 + 0{,}375 + 0{,}375 = 1{,}75 \ \text{бит/символ} $$

В среднем каждый символ этого источника несёт 1,75 бита. Это меньше, чем 2 бита (которые понадобились бы при наивном равномерном коде из двух битов на символ), — потому что символы неравновероятны.

Максимум энтропии при равновероятности

Ключевое свойство: при фиксированном числе символов $N$ энтропия максимальна, когда все символы равновероятны, $p_i=\tfrac{1}{N}$. Тогда:

$$ H_{\max} = -\sum_{i=1}^{N} \frac{1}{N}\log_2 \frac{1}{N} = \log_2 N $$

И снова мы получили формулу Хартли! Для нашего алфавита из 4 символов максимум равен $\log_2 4 = 2$ бита. Наш реальный источник дал $1{,}75 \lt 2$ — это нормально: любая неравномерность вероятностей снижает энтропию. Логика понятна: если один исход почти всегда наступает, источник предсказуем, и информации в нём мало. Максимальная непредсказуемость — когда «угадать» нельзя совсем, то есть при равных вероятностях.

Связь с минимальной длиной кода

Теорема Шеннона о кодировании источника утверждает: средняя длина кода на символ не может быть меньше энтропии $H$, но к ней можно сколь угодно близко подойти. Для нашего источника удачный код (например, A→0, B→10, C→110, D→111) даёт среднюю длину ровно $0{,}5\cdot 1 + 0{,}25\cdot 2 + 0{,}125\cdot 3 + 0{,}125\cdot 3 = 1{,}75$ бита — совпадает с энтропией. Так теория подсказывает, как строить экономные коды.

Как это работает

Посчитаем энтропию на Python для произвольного набора вероятностей. Важная техническая деталь: если какой-то символ имеет вероятность 0, его вклад $0\cdot\log_2 0$ принимают равным 0 (по пределу), поэтому такие символы просто пропускаем — иначе log2(0) даст ошибку.

import math

def entropy(probs):
    h = 0.0
    for p in probs:
        if p > 0:
            h -= p * math.log2(p)
    return h

source = [0.5, 0.25, 0.125, 0.125]
uniform = [0.25, 0.25, 0.25, 0.25]

print(f"Сумма вероятностей: {sum(source)}")
print(f"Энтропия источника: {entropy(source)} бит/символ")
print(f"Максимум (равновероятно): {entropy(uniform)} бит/символ")

Вывод:

Сумма вероятностей: 1.0
Энтропия источника: 1.75 бит/символ
Максимум (равновероятно): 2.0 бит/символ

Расчёт подтверждает теорию: реальный источник даёт 1,75 бита, а равновероятный — ровно 2 бита, то есть максимум для четырёх символов.

Сколько бит на всё сообщение

Если источник с энтропией $H$ выдал сообщение длиной $L$ символов, то полное количество информации оценивается как $I = L \cdot H$. Например, текст из 1000 символов нашего источника несёт примерно $1000 \cdot 1{,}75 = 1750$ бит, то есть около 219 байт, — заметно меньше, чем 2000 бит при наивном двухбитном кодировании.

Частые ошибки

• Забыть минус перед суммой. Поскольку $\log_2 p_i \le 0$, без минуса энтропия получилась бы отрицательной.
• Не проверить, что $\sum p_i = 1$. Если вероятности заданы в процентах или «на глаз», их нужно нормировать.
• Считать $0\cdot\log_2 0$ как ошибку. По соглашению этот член равен 0 — символ с нулевой вероятностью в сумму не входит.
• Путать энтропию (среднее на символ) с информацией одного конкретного сообщения ($-\log_2 p$). Энтропия — усреднение по всем символам.
• Думать, что максимум энтропии бесконечен. При $N$ символах он ограничен сверху: $H_{\max}=\log_2 N$.

Итоги

• Энтропия источника: $H=-\sum p_i\log_2 p_i$ бит на символ — средняя информация на один символ.
• Максимум $H_{\max}=\log_2 N$ достигается при равновероятных символах; любая неравномерность энтропию снижает.
• Энтропия — нижняя граница средней длины кода: ниже неё сжать без потерь нельзя.
• Информация всего сообщения длиной $L$: $I=L\cdot H$.
• Член с $p_i=0$ в сумму не входит (его вклад равен 0).