Равномерное и неравномерное кодирование: в чём разница

Равномерное и неравномерное кодирование - это два способа сопоставить символам алфавита двоичные коды. В равномерном коде все символы получают цепочки одинаковой длины, в неравномерном - разной: частым символам достаётся короткий код, редким длинный. Различие кажется мелким, но именно оно лежит в основе всех алгоритмов сжатия данных, от телеграфа Морзе до современных архиваторов. Ниже разберём, как считается длина равномерного кода, как строится неравномерный код Хаффмана, почему он экономит память и где студенты чаще всего ошибаются в задачах. Чтобы сразу увидеть выигрыш в цифрах, покрути калькулятор ниже: задай частоты символов и сравни объём сообщения в обоих способах, а затем мы разберём каждую формулу по порядку.

Что такое равномерное кодирование

Равномерное кодирование сопоставляет каждому символу алфавита двоичный код одной и той же длины. Если в алфавите $N$ различных символов, то длина кода на символ равна

$L_{равн} = \lceil \log_2 N \rceil,$

где квадратные скобки обозначают округление вверх до целого числа бит. Логика простая: $k$ бит дают $2^k$ различных комбинаций, поэтому надо взять минимальное $k$, при котором $2^k \ge N$. Для алфавита из 5 символов нужно $\lceil \log_2 5 \rceil = 3$ бита (двух бит хватило бы только на 4 символа), для 8 символов - ровно 3 бита, для 256 символов - 8 бит, то есть привычный байт.

Рассчитать для своей задачи

Главное достоинство равномерного кода - простота: декодировать его можно, просто нарезая поток на куски фиксированной длины. Именно так устроен ASCII (7 бит на символ) и кодировки фиксированной ширины. Платой за простоту становится избыточность: код буквы, которая встречается в тексте один раз, занимает столько же бит, сколько код буквы, встречающейся тысячу раз.

Что такое неравномерное кодирование

Неравномерное кодирование назначает символам коды разной длины. Идея, восходящая ещё к азбуке Морзе, в том, чтобы частым символам давать короткие коды, а редким - длинные. Тогда суммарный объём сообщения падает, ведь короткие коды используются чаще всего. Чтобы такой код можно было однозначно декодировать без разделителей, он должен быть префиксным: ни один код не должен быть началом другого кода. Это условие гарантирует, что поток битов читается слева направо без неоднозначности.

Каноничный способ построить оптимальный префиксный код - алгоритм Хаффмана. Он собирает два самых редких символа в один узел, складывает их частоты и повторяет, пока не останется единственное дерево. Спуск от корня к листу даёт код символа: шаг влево добавляет 0, шаг вправо - 1. Чем чаще символ, тем ближе он к корню и тем короче его код.

Рассчитать для своей задачи

Средняя длина кода и энтропия

Качество неравномерного кода измеряют не максимальной, а средней длиной кода на символ:

$L_{ср} = \sum_i p_i \, l_i,$

где $p_i$ - вероятность (доля) символа, а $l_i$ - длина его кода. Каждый код входит в сумму с весом, равным частоте символа, поэтому короткие коды частых символов тянут среднюю длину вниз. Для равномерного кода все $l_i$ одинаковы, и $L_{ср}$ просто совпадает с $L_{равн}$.

Нижнюю границу средней длины задаёт энтропия источника по Шеннону:

$H = -\sum_i p_i \, \log_2 p_i.$

Энтропия - это среднее количество информации на символ в битах. Теорема Шеннона о кодировании утверждает, что никакой код не может иметь среднюю длину меньше энтропии: $L_{ср} \ge H$. Код Хаффмана подходит к этой границе вплотную, обычно отставая от энтропии меньше чем на один бит. Поэтому в калькуляторе выше штриховая линия энтропии всегда лежит чуть ниже столбика неравномерного кода - это теоретический предел, ниже которого опуститься нельзя.

Сравнение и коэффициент сжатия

Выигрыш неравномерного кодирования удобно выражать коэффициентом сжатия - отношением объёма при равномерном кодировании к объёму при неравномерном:

$k = \frac{L_{равн} \cdot M}{L_{ср} \cdot M} = \frac{L_{равн}}{L_{ср}},$

где $M$ - число символов в сообщении. Возьмём конкретный пример из калькулятора: алфавит A, B, C, D, E с частотами 40, 25, 18, 10, 7 (всего 100 символов). Равномерный код требует $L_{равн} = 3$ бита на символ, значит, всё сообщение займёт $300$ бит. Код Хаффмана даёт коды A = 0, B = 10, C = 111, D = 1101, E = 1100 со средней длиной

$L_{ср} = \frac{40 \cdot 1 + 25 \cdot 2 + 18 \cdot 3 + 10 \cdot 4 + 7 \cdot 4}{100} = \frac{212}{100} = 2{,}12 \text{ бит}.$

Сообщение сжимается до $212$ бит, то есть коэффициент сжатия $k = 300 / 212 \approx 1{,}42$, а экономия памяти - около 29 процентов. При этом энтропия источника равна $H \approx 2{,}07$ бит, и средняя длина Хаффмана 2,12 от неё почти не отстаёт. Чем сильнее перекошено распределение частот, тем больше выигрыш: если в калькуляторе выбрать пресет «Один частый», коэффициент сжатия вырастает примерно до 1,7.

Когда какой способ выбрать

Равномерное кодирование выбирают там, где важны простота и скорость доступа: фиксированная длина позволяет мгновенно найти $i$-й символ по смещению $i \cdot L_{равн}$ и не требует хранить таблицу кодов. Поэтому кодировки символов, форматы записей в базах и многие сетевые протоколы фиксированной ширины используют именно его. Неравномерное кодирование выбирают там, где важен объём: архиваторы, форматы изображений и видео, передача по узкому каналу. Платой становятся таблица кодов, которую нужно хранить или передавать вместе с данными, и невозможность прыгнуть к произвольному символу без последовательного декодирования. На коротких сообщениях накладные расходы на таблицу могут даже перевесить экономию - это стоит учитывать в задачах на сравнение.

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

• Округление длины равномерного кода вниз. Длина равна $\lceil \log_2 N \rceil$ с округлением вверх: для 5 символов это 3 бита, а не 2. Дробное число бит недопустимо.
• Путаница битов и байтов. Длина кода считается в битах. Чтобы перевести объём сообщения в байты, разделите число бит на 8 и округлите вверх.
• Непрефиксный неравномерный код. Если придумать коды вручную и допустить, что один код является началом другого, поток нельзя будет однозначно декодировать. Код Хаффмана префиксный по построению.
• Подсчёт средней длины без весов. $L_{ср}$ - это средневзвешенная длина по частотам, а не среднее арифметическое длин кодов. Редкий длинный код почти не влияет на результат.
• Сравнение длины Хаффмана с энтропией со знаком меньше. Средняя длина всегда не меньше энтропии: $L_{ср} \ge H$. Если в ответе $L_{ср} < H$, где-то ошибка в подсчёте.

FAQ

Чему равна длина равномерного кода для алфавита из 33 букв? Берём ближайшую сверху степень двойки: $2^5 = 32 < 33 \le 64 = 2^6$, поэтому $L_{равн} = \lceil \log_2 33 \rceil = 6$ бит на символ. Пяти бит хватило бы только на 32 символа.

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

В чём разница между кодом Хаффмана и азбукой Морзе? Оба дают частым символам короткие коды, но Морзе не является префиксным: для разделения букв в нём нужна пауза. Код Хаффмана префиксный и декодируется без разделителей, поэтому он оптимален для двоичной записи, а Морзе - нет.

Коротко

Равномерное кодирование даёт всем символам код одной длины $L_{равн} = \lceil \log_2 N \rceil$ и ценно простотой и быстрым доступом. Неравномерное кодирование (код Хаффмана) назначает частым символам короткие коды, а редким длинные, снижая среднюю длину $L_{ср} = \sum p_i l_i$ почти до энтропии $H = -\sum p_i \log_2 p_i$. Выигрыш измеряется коэффициентом сжатия $k = L_{равн} / L_{ср}$ и тем больше, чем сильнее перекошено распределение частот символов.