Неравномерный код

Неравномерный код – это отображение символов исходного алфавита в кодовые слова разной длины над кодовым алфавитом (чаще всего двоичным), сконструированное так, чтобы обеспечить однозначную раскодировку сообщений и, как правило, минимизировать среднюю длину кодового слова при заданных вероятностях символов. Неравномерные коды лежат в основе сжатия без потерь, телекоммуникаций и задач ЕГЭ, связанных с кодированием информации, таблицами частот, декодированием и оценкой длины сообщений.

Понятийный аппарат

1. Алфавиты и кодирование
   
   

2. Средняя длина и информационные величины
   
   

Корректность неравномерных кодов

1. Однозначная декодируемость, префиксность, мгновенность
   

   • Однозначно декодируемый код: любая конкатенация кодовых слов разбивается единственным образом.

   • Префиксный (prefix-free): ни одно кодовое слово не является префиксом другого.

   • Мгновенный: префиксный код, декодируемый «на лету» слева направо без просмотра вперёд – достаточно проверять префиксность.
     Факт: любой префиксный код однозначно декодируем.
     

2. Дерево кода
   

   Префиксные коды удобно представлять деревом решений (бор/трибор для k-ичного алфавита): путь от корня к листу – кодовое слово. Отсутствие ситуации «лист на пути к другому листу» эквивалентно префиксности.

3. Крафт–Макмиллан
   

   Для k-ичного алфавита и длин ℓ1,…,ℓm ​ необходимо и достаточно для существования префиксного кода: 
   

Конструирование неравномерных кодов

1. Хаффмановское кодирование (оптимально по средней длине при фиксированных pip_ipi​)

Алгоритм (двоичный вариант):

1. Поместить все символы с весами pi​ в список.

2. Повторять: выбрать два наименее вероятных узла, объединить их в новый узел с весом суммы; привесить бит 0/1 на соответствующие ветви.

3. По завершении обходить дерево от корня к листам – пути дают кодовые слова.
   Свойства: код префиксный, мгновенный; более вероятные символы получают более короткие слова.

2. Шеннон–Фано 

Сортируем символы по убыванию pi, рекурсивно делим множество на две части с близкими суммами вероятностей, присваивая 0/1 на каждом разделении. Проще, чем Хаффман, но может давать чуть большую L.

3. Десятичные/тернарные коды

Декодирование и проверка корректности

1. Мгновенное декодирование
   

   Идём по битовой строке от корня префиксного дерева. Как только пришли в лист – выдаём символ, возвращаемся в корень. Это работает, только если код префиксный.

2. Проверка префиксности
   

   Достаточно удостовериться, что ни одно слово не является префиксом другого. Практически:

   • отсортировать слова по лексикографическому порядку и проверить соседние пары;

   • построить бор: если во внутренней вершине «повесился» лист и под ним есть ещё ветви – префикс нарушен.

3. Однозначная декодируемость вне префиксности (к сведению)
   

   Существуют не префиксные, но однозначно декодируемые коды. Теоретический тест – алгоритм Сардинаса–Паттерсона. В ЕГЭ обычно достаточно проверять префиксность.

Практика и «правила ЕГЭ»

1. Частоты → дерево Хаффмана → таблица кода → средняя длина.

2. Проверка префиксности: быстро через сортировку слов; любое нарушение – не мгновенно.

3. Границы Шеннона: сверять

4. Крафт: по набору длин проверить существование префиксного кода.

5. Декодирование: предпочитать метод дерева/борa, а не «угадывание» разбиений.

Типичные ошибки

• Путают префиксность и однозначную декодируемость (префиксность сильнее и проще проверяется).

• Считают L без нормировки вероятностей.

• Нарушают условие Крафта при конструировании «на глаз».

• Декодируют «жадно» не префиксный код – возникает неоднозначность.

• В задачах с k≠2 продолжают использовать логарифм по основанию 2.

Пять упражнений (академический формат «теория + практика»)

Упражнение 1. Проверка префиксности и существования

Дан набор длин двоичного кода для пяти символов: ℓ=(1,2,3,3,4).
a) Проверьте условие Крафта.
b) Постройте пример префиксного кода с такими длинами (если возможно) в виде дерева.
c) Является ли получившийся код полным?

Упражнение 2. Средняя длина и границы Шеннона

Упражнение 3. Декодирование

Упражнение 4. Непрефиксный, но (возможно) однозначный?

Упражнение 5. Троичный код и Крафт

Заключение

Неравномерные коды позволяют адаптировать длину кодовых слов под частоты символов, достигая близости к энтропийному пределу и тем самым сокращая объём данных при передаче/хранении. Для задач ЕГЭ ключевые навыки:

• различать префиксные и непрефиксные коды;

• строить код Хаффмана и дерево кода;

• вычислять среднюю длину, энтропию и проверять границы Шеннона;

• применять условие Крафта для проверки реализуемости набора длин;

• уверенно декодировать битовые строки.

Системное владение этими правилами превращает задания на кодирование в рутинные и предсказуемые – именно это приносит устойчиво высокие баллы на экзамене.