Декодирование по неравномерному коду: как разобрать строку

Неравномерный код - это такой способ представления символов, при котором разные символы кодируются двоичными словами разной длины. Короткие коды достаются частым символам, длинные - редким, и именно так работают алгоритмы сжатия данных. Декодирование такой строки нетривиально: нельзя просто нарезать биты фиксированными кусками. Ниже разберём, как строится алгоритм разбора, почему важен критерий Фано и как дерево кода превращает цепочку нулей и единиц в читаемое сообщение. Интерактивный калькулятор ниже позволит сразу потренироваться - введите таблицу кодов и строку для разбора.

Что такое неравномерный код и зачем он нужен

В равномерном коде (например, ASCII) каждый символ занимает строго $n$ бит: просто делим строку на равные блоки и смотрим в таблицу. Неравномерный код работает иначе: символ «а» может кодироваться одним битом 0, а символ «я» - пятью битами 11011. Длина кодового слова определяется частотой символа: чем чаще символ встречается в тексте, тем короче его код.

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

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

Критерий Фано: почему декодирование возможно однозначно

Декодирование неравномерного кода однозначно, только если код удовлетворяет критерию Фано (свойство префиксности): ни одно кодовое слово не является началом другого кодового слова. Такой код называют префиксным или кодом без запятых.

Например, если «а» = 0, то ни у одного другого символа код не начинается с 0. А если «б» = 10, то никакой другой символ не может иметь код 1, 10x или 10xx и т. д.

Код Хаффмана всегда строится как префиксный. Это гарантирует: как только достигнута конкретная битовая последовательность, совпадающей с кодовым словом - перед нами ровно один символ, а разбор продолжается с ближайшего следующего бита.

$$\text{Код } C \text{ является префиксным} \iff \forall\, i \neq j:\; c_i \text{ не является префиксом } c_j$$

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

Алгоритм разбора: дерево Хаффмана

Самый надёжный способ декодировать строку по неравномерному коду - построить двоичное дерево кода и обходить его по одному биту:

1. Строим дерево: корень - пустой узел; для каждого символа из таблицы прокладываем путь от корня, где 0 - левая ветвь, 1 - правая; в конце пути - листовой узел с символом.
2. Начинаем с корня, читаем биты закодированного сообщения по одному.
3. По каждому биту идём вниз по дереву: 0 - влево, 1 - вправо.
4. Как только попадаем в листовой узел - записываем символ, возвращаемся в корень и читаем следующий бит.
5. Повторяем до конца строки.

Этот алгоритм работает за $O(n)$ по длине кодированной строки $n$ (при заранее построенном дереве). Построение дерева по таблице кодов - $O(\sum_i |c_i|)$, где $|c_i|$ - длина кода символа $i$.

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

Пошаговый пример декодирования

Возьмём типичную учебную таблицу кодов и декодируем конкретную строку.

Таблица кодов:

Закодированная строка: 1101001110

Разбираем пошагово:

• Читаем 1 - идём вправо. Листа нет.
• Читаем 1 - идём вправо. Листа нет.
• Читаем 0 - идём влево. Лист C (110). Возвращаемся в корень. C
• Читаем 1 - идём вправо.
• Читаем 0 - идём влево. Лист B (10). B
• Читаем 0 - идём влево. Лист A (0). A
• Читаем 1 - идём вправо.
• Читаем 1 - идём вправо.
• Читаем 1 - идём вправо. Лист D (111). D
• Читаем 0 - идём влево. Лист A (0). A

Результат: CBADA.

Обратите внимание: каждый раз, когда встречен лист, мы точно знаем символ - именно благодаря свойству префиксности нет никакой неоднозначности.

Построение кода Хаффмана по частотам

В реальных задачах таблица кодов не даётся - её нужно построить по частотам символов. Алгоритм Хаффмана:

1. Создать узел для каждого символа с весом = частота встречаемости.
2. Поместить все узлы в очередь с приоритетом (минимальный вес - первый).
3. Взять два узла с наименьшими весами, объединить в новый узел с весом = сумма двух.
4. Вернуть новый узел в очередь. Повторять до одного корневого узла.
5. Обойти дерево: левая ветвь = 0, правая = 1. Листья - коды символов.

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

$$H(X) \leq \bar{L} < H(X) + 1,$$

где $H(X) = -\sum_i p_i \log_2 p_i$ - энтропия источника (бит/символ), а $\bar{L} = \sum_i p_i |c_i|$ - средняя длина кодового слова.

Равномерный vs неравномерный код: сравнение

Чтобы понять, зачем нужен неравномерный код, сравним средние длины. Пусть в алфавите 4 символа с вероятностями:

$$p_A = 0.5,\quad p_B = 0.25,\quad p_C = 0.125,\quad p_D = 0.125.$$

Равномерный код потребует $\lceil \log_2 4 \rceil = 2$ бита на символ - средняя длина $\bar{L} = 2$.

Код Хаффмана для тех же символов:

Средняя длина: $\bar{L} = 0.5 \cdot 1 + 0.25 \cdot 2 + 0.125 \cdot 3 + 0.125 \cdot 3 = 1.75$ бит/символ.

Энтропия: $H = -(0.5 \log_2 0.5 + 0.25 \log_2 0.25 + 2 \cdot 0.125 \log_2 0.125) = 1.75$ бит/символ.

Хаффман достиг теоретического минимума - экономия 12.5% по сравнению с равномерным кодом.

Частые ошибки при декодировании

• Не возвращаться в корень после нахождения символа. Ошибка: продолжают путь в дереве от найденного листа. Лист - тупик; каждый новый символ читается заново с корня.
• Путать направления ветвей. Всегда смотрите на соглашение: 0 влево или 0 вправо - в разных учебниках по-разному. Главное - применять одно соглашение и при построении дерева, и при декодировании.
• Декодировать нал на нескольких шагах сразу. Алгоритм строго последовательный: один бит → шаг по дереву. Нельзя «угадать» символ, сравнивая несколько кусков строки параллельно.
• Игнорировать критерий Фано. Если код не является префиксным, однозначное декодирование невозможно. Перед решением задачи проверьте: нет ли слова, которое является префиксом другого.
• Ошибка в дереве Хаффмана при одинаковых весах. При объединении двух узлов с равными весами порядок выбора произвольный, и разные учебники могут дать разные деревья - все они корректны, но дают разные коды. Важно: декодирование работает с тем деревом, по которому производилось кодирование.

FAQ

Что делать, если не знаешь таблицу кодов, а нужно декодировать строку? Без таблицы кодов (или дерева) декодировать неравномерно закодированную строку невозможно - это принципиально отличает неравномерный код от равномерного. В задачах на ЕГЭ/ОГЭ таблица всегда дана. В реальных форматах (zip, gzip) дерево хранится в заголовке файла вместе со сжатыми данными.

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

Можно ли неравномерный код применять в реальном времени (потоковое сжатие)? Да. Именно так работает gzip и большинство кодеков. Передаётся дерево, а затем закодированный поток. Декодер читает биты один за другим и обходит дерево точно по алгоритму выше - без буферизации всего сообщения.

Коротко

Декодирование по неравномерному коду сводится к обходу дерева по одному биту: достигли листа - записали символ, вернулись в корень. Алгоритм работает только для префиксных кодов (критерий Фано). Код Хаффмана автоматически префиксный и оптимален по средней длине кодового слова. Дерево строится жадным алгоритмом по частотам символов за $O(n \log n)$, а само декодирование строки - за $O(|s|)$.