← Вернуться к оглавлению
Alterna · глава 26 · страница 26.3

Декодирование

Пошаговое декодирование префиксных кодов.

Декодирование — восстановление исходного сообщения из битовой строки с помощью кодового дерева.

ФГОСОГЭ №2,4ЕГЭ №4
Связь. Декодирование — обратный процесс к кодированию. Используем то же дерево, но двигаемся от корня, читая биты.
01

Алгоритм декодирования

Алгоритм (для префиксного кода):

  1. Начать с корня дерева.
  2. Читать следующий бит: 0 → влево, 1 → вправо.
  3. Если достигли лист — вывести символ, вернуться к корню.
  4. Повторять, пока не обработаны все биты.

Для непрефиксного кода декодирование неоднозначно — одна битовая строка может дать разные тексты.

Пример

Код: A=0, B=10, C=110, D=111. Декодируем 01101110:

  • Читаем 0 → лист A. Результат: A. Код: 1101110
  • Читаем 1 → вправо, читаем 1 → вправо, читаем 0 → лист C. Результат: A C. Код: 1110
  • Читаем 1 → вправо, читаем 1 → вправо, читаем 1 → вправо, читаем 0 → лист D. Результат: A C D. Код: 0
  • Читаем 0 → лист A. Результат: A C D A
02

Пошаговый декодер

📡Декодер с пошаговым выводом
Введите коды и биты.
03

Задание ЕГЭ №4

📋ЕГЭ №4 — Интерактивные задачи
04

Ошибки декодирования

Непрефиксный код — неоднозначность

Если код не удовлетворяет условию Фано, одна битовая строка может декодироваться по-разному.

Пример: код {0, 01}

Строка 01:

  • Как 0 + 01 → A + B → «AB»
  • Как 01 → C → «C»

Два варианта! Такой код нельзя декодировать однозначно.

Проверка декодируемости

Для префиксного кода декодирование всегда однозначно — алгоритм «корень → лист → корень» даёт唯一的 результат.