1) Оптимальный префиксный код (Хаффман)

Для вероятностей {a:0.5, b:0.3, c:0.2} алгоритм Хаффмана объединяет 0.3 и 0.2 в узел 0.5, затем соединяет эти два узла 0.5 и 0.5. Один допустимый оптимальный префиксный код:

a → 0 (длина 1)b → 10 (длина 2)c → 11 (длина 2)

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

H = −∑ p(x) log2 p(x)
= −(0.5·log2 0.5 + 0.3·log2 0.3 + 0.2·log2 0.2)
≈ 0.5 + 0.52109 + 0.46439 ≈ 1.48548 бит/символ.

(округлённо H ≈ 1.4855 бит/символ)

3) Средняя длина кода L и эффективность η

L = 0.5·1 + 0.3·2 + 0.2·2 = 1.5 бит/символ.

Эффективность η = H / L ≈ 1.48548 / 1.5 ≈ 0.9903 ≈ 99.03%.

Избыточность L − H ≈ 0.01452 бит/символ (маленькая, как и ожидалось; для оптимального префиксного кода всегда H ≤ L < H + 1).

4) Что происходит при введении корреляций между символами

При наличии корреляций релевантной характеристикой становится энтропийная скорость (entropy rate) H_rate = lim(1/n) H(X1..Xn), или для марковского источника H_rate = ∑_i πi H(X{t+1}|X_t=i). Как правило H_rate ≤ H (H — энтропия маргинального распределения). То есть при корреляциях "информация на символ" снижается — можно сжать лучше, чем при независимых одинаковых маргинальных распределениях.Если вы продолжаете применять однобуквенный Хаффман, то средняя длина L не будет учитывать корреляции (она зависит только от маргиналов) — следовательно эффективность относительно реальной энтропийной скорости ухудшится: η_real = H_rate / L < 1, и может быть значительно меньше 1, если сильные зависимости.Чтобы использовать корреляции, нужно кодировать с учётом зависимости между символами:
Блочное кодирование: строить код для блоков длины n (Huffman или другие префиксные коды для совместных вероятностей блоков). При росте n средняя длина на символ L_n удовлетворяет H_rate ≤ L_n < H_rate + 1/n, то есть можно приближаться к H_rate, но растут сложность и задержка.Условное/контекстное кодирование: для каждой предшествующей ситуации (контекста) строить отдельный код (условный Хаффман). Это эффективно при небольшом числе контекстов.Энтропийное кодирование с дробными битами: арифметическое кодирование или ANS (asymmetric numeral systems) в сочетании с моделями контекста (PPM, CTW, адаптивные марковские модели) дает практический способ приблизиться к H_rate с низкой избыточностью и без необходимости округления длин до целого числа бит.Универсальные методы (LZ-подобные) хорошо работают, когда статистика заранее неизвестна: они эксплуатируют повторения/зависимости и со временем приближаются к энтропийному пределу для широкого класса источников.

5) Практические рекомендации

Если источник действительно памятьless (независимые символы с данными маргиналами), Хаффман — простое и эффективное решение (в нашем случае эффективность ≈99%).Если есть корреляции/контексты — лучше использовать контекстные модели + арифметическое кодирование или ANS (или блоковый Хаффман при небольших блоках и известной статистике). Эти методы дают существенное улучшение при сильной зависимости между символами.Вариант с условным Хаффманом (для каждого контекста отдельный префиксный код) полезен, если число значимых контекстов невелик; иначе предпочтительны адаптивные контекстные энкодеры (PPM, CTW) или ANS.

Если хотите, могу:

показать пример, как сильно может падать энтропийная скорость при конкретной марковской модели (и сравнить L для однобуквенного Хаффмана и для контекстного кодирования), илипродемонстрировать построение блокового Хаффмана для пар символов и вычислить L_n.