Префиксный код: чтение и сокращение
Как декодировать префиксный код и проверить сокращение кодового слова?
p — не начало q
- p
- непустое двоичное кодовое слово одного символа, последовательность битов
- q
- любое другое кодовое слово; коды всех символов различны, последовательность битов
Условие Фано здесь означает: ни одно кодовое слово не является началом другого. Такой код можно читать слева направо: как только набран код символа, записывай символ и начинай следующий.
Пример: А = 0, Б = 11, В = 101, Г = 1000, Д = 1001. Это полный список кодов. Декодируем строку 10010101111000: 1001 / 0 / 101 / 11 / 1000 → Д / А / В / Б / Г.
Ответ: ДАВБГ; все биты использованы.
Можно ли сделать код Г короче, сохранив остальные коды и условие Фано? Однобитный 0 уже занят; 1 был бы началом кодов Б, В и Д. Из двухбитных 00 и 01 начинаются с кода А; 10 является началом кодов В = 101 и Д = 1001; 11 занят кодом Б. Из трёхбитных слова на 0 начинаются с кода А, 110 и 111 — с кода Б; 100 является началом кода Д = 1001; 101 занят кодом В. Подходящего слова длины 1, 2 или 3 нет. Значит, нынешняя длина кода Г — 4 бита — минимальна при неизменных кодах А, Б, В и Д.
Ловушка: проверять нужно оба направления — новый код не должен быть началом старого, а старый началом нового. Неполный остаток битов нельзя молча отбросить. Префиксность достаточна, но не необходима для однозначного декодирования вообще; вывод о минимуме здесь относится именно к условию Фано и фиксированным остальным кодам.

