Информатика / Кодирование информации

Средняя длина кода Хаффмана: расход бит на символ

Средняя длина двоичного кода равна сумме длин кодовых слов с весами вероятностей символов. Для кода Хаффмана этот расход минимален среди двоичных посимвольных префиксных кодов с заданными вероятностями.

Опубликовано: 18 октября 2026 г.Обновлено: 18 октября 2026 г.

Формула

\overline{L}=\sum_{i=1}^{m}p_i\ell_i

Схема Код с расходом 1,9 бит/символ

Взвешенная сумма длин меньше двух бит фиксированного кода.

Обозначения

$m$: число символов алфавита, безразмерная величина
$i$: номер символа, безразмерная величина
$pᵢ$: вероятность символа i, безразмерная величина
$ℓᵢ$: длина его двоичного кодового слова, бит
$L̄$: средний расход, бит/символ

Условия применения

Вероятности положительны и суммируются в единицу; алфавит содержит не менее двух символов. Длины относятся к фактически построенному двоичному префиксному коду. Формула среднего работает и для других кодов, но минимальность требует именно корректного построения Хаффмана.

Ограничения

Оптимальность касается среднего расхода посимвольного префиксного кода, а не любого способа сжатия. Словарь, заголовки и выравнивание байтов в формулу не входят. Если статистика реального потока отличается от использованной при построении дерева, прежняя оптимальность для нового потока не гарантирована.

Подробное объяснение

Длины кодовых слов различаются, поэтому простое среднее длин может дать неверную оценку. Символ, встречающийся в половине позиций, участвует в расходе гораздо чаще символа с вероятностью одна сотая. Вес p превращает длину слова в его вклад на один исходный символ.

Алгоритм Хаффмана начинает с отдельных символов и многократно объединяет два узла с наименьшими весами. Вес родителя равен сумме весов детей. После построения дерева рёбра помечают нулями и единицами, а длина пути от корня к листу становится длиной слова.

Префиксность означает, что ни одно кодовое слово не является началом другого. Поэтому поток можно читать по дереву без разделителей между символами. Перестановка меток 0 и 1 на ветвях меняет сами слова, но не длины и не средний расход.

Сумма весов всех внутренних объединений также равна средней длине: каждый вес листа учитывается один раз за каждый пройденный уровень. Это удобная независимая проверка дерева. При равных весах возможны разные оптимальные деревья с одинаковой средней длиной.

Для двоичного кода Хаффмана средняя длина не меньше энтропии и строго меньше энтропии плюс один бит на символ при обычных условиях конечного алфавита. Однако даже хороший средний расход не означает уменьшение короткого файла: передача таблицы кодов может перекрыть выигрыш.

Как пользоваться формулой

Определите вероятности по выбранной модели или частотам и нормируйте их до суммы, равной единице.
Постройте дерево, каждый раз объединяя два наименьших веса, либо выпишите длины готовых кодовых слов.
Умножьте длину каждого слова на вероятность соответствующего символа и сложите все вклады.
Проверьте итог суммой весов объединений и отдельно учтите служебные данные при оценке размера файла.

Историческая справка

Дэвид Хаффман описал построение кодов минимальной избыточности в статье 1952 года в Proceedings of the IRE. Метод дал конструктивный способ назначить целые длины двоичных слов с минимальным средним расходом для заданных вероятностей. Он дополнил теоретическое описание границ кодирования практической процедурой объединения наименьших весов. В современной литературе алгоритм служит классическим примером жадного выбора, для которого доказывается глобальная оптимальность. Само взвешенное среднее длин является общим математическим ожиданием и не было отдельным изобретением Хаффмана. Исторический вклад относится к оптимальному построению префиксного дерева; арифметическое кодирование и словарные методы решают связанные задачи другими средствами и не сводятся к этому дереву.

Историческая линия формулы

Алгоритм построения оптимального префиксного кода носит имя Хаффмана и связан с публикацией 1952 года. Формула среднего расхода — обычное взвешенное среднее; важно отличать вычисление показателя от метода, который подбирает код с минимальным значением этого показателя.

Пример

Пусть вероятности A,B,C,D равны 0,4;0,3;0,2;0,1. Хаффман объединяет 0,1 и 0,2 в 0,3; затем этот узел и исходный 0,3 в 0,6; наконец 0,4 и 0,6 в 1. Подходящий код: A=0, B=10, C=110, D=111. Длины 1,2,3,3 дают L̄=0,4·1+0,3·2+0,2·3+0,1·3=1,9 бит/символ. Проверка по весам объединений: 0,3+0,6+1=1,9. Фиксированный код четырёх символов требует два бита, поэтому полезный поток экономит в среднем 0,1 бита на символ, или 5%. Это сравнение не включает хранение словаря, а конкретная короткая последовательность может иметь другой средний расход.

Частая ошибка

Не усредняйте длины без вероятностей. Не присваивайте короткие слова, нарушающие префиксность, ради искусственного уменьшения суммы. Не считайте любой переменный код кодом Хаффмана. Не обещайте процент уменьшения всего файла по полезному потоку без учёта словаря, выравнивания и исходного представления данных.

Практика

Задачи с решением

Три символа

Условие. Вероятности 1/2,1/4,1/4. Кодовые слова 0,10,11. Найдите среднюю длину.

Решение. Длины 1,2,2: L̄=(1/2)·1+(1/4)·2+(1/4)·2=1,5.

Ответ. 1,5 бит/символ

Счёт по частотам

Условие. В сообщении 40 A,30 B,20 C,10 D. Длины слов 1,2,3,3. Сколько бит в полезном потоке?

Решение. Суммарно 40·1+30·2+20·3+10·3=190 бит. На 100 символов среднее равно 1,9.

Ответ. 190 бит без служебных данных

Дополнительные источники

https://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf
https://www.cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/compression.pdf
https://www.cs.cmu.edu/~guyb/real-world/compress/gutmann.html

Связанные формулы

Информатика

Неравенство Крафта: длины двоичных префиксных кодов

$\sum_{i=1}^{m}2^{-l_i}\le 1$

Неравенство Крафта проверяет, могут ли заданные длины двоичных слов образовать префиксный код: сумма 2 в степени минус длина не должна превышать единицу.

Информатика

Энтропия Шеннона: средняя информация дискретного источника

$H(X)=-\sum_{i=1}^{m}p_i\log_2p_i$

Энтропия Шеннона измеряет среднюю неопределённость исхода по его вероятностям. При двоичном логарифме результат выражают в битах на символ; редкие и частые символы вносят разный вклад.

Информатика

Размер сообщения по числу символов и битам на символ

$I=K\cdot i$

Размер сообщения по числу символов и битам на символ: формула I=K\cdot i помогает величины I, K, i заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата.