Задание EGEINF460D7D: Однозначное кодирование и условие Фано

Известные коды: А → 000; Б → 001; В → 10; Г → 11. Начальные нули являются частью кодового слова и не отбрасываются.

Условие Фано запрещает два случая: новый код является началом уже известного или известный код является началом нового. Изобразим возможные записи мысленно как двоичное дерево: ребро 0 ведёт влево, ребро 1 вправо. Известный код занимает вершину вместе со всеми её продолжениями; его предки также не могут стать кодами других букв.

После исключения занятых ветвей остаются свободные начала: 01. Это самые короткие корни полностью свободных ветвей. Их можно получить обходом дерева: если текущая строка уже является известным кодом, её ветвь закрыта; если она не совпадает с началом ни одного известного кода, вся ветвь свободна; иначе проверяем два продолжения, добавляя 0 и 1. Такой обход охватывает все допустимые новые коды.

Неизвестные коды нужны для Д, Е. Ищем кратчайший код символа Д; среди равных длин выбираем наибольшее двоичное значение. Для одной длины числовой порядок совпадает с алфавитным порядком битовых строк.

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

Проверяем длины по возрастанию. В каждой строке перечислены все коды данной длины, совместимые с известными кодами; после каждого отмечена возможность завершить весь алфавит:
Длина 1: совместимых кодов нет.
Длина 2: 01 — не оставляет места другим символам.
Длина 3: 010 — подходит; 011 — подходит.

Первый допустимый уровень имеет длину 3. Все более короткие варианты исключены. На этом уровне с учётом требуемого числового порядка выбираем 011. Пример полного дополнения: Д → 011; Е → 010.

Проверка: сравним каждую пару кодов в полученном полном наборе. Ни короткое слово не совпадает с началом длинного, ни два слова одинаковой длины не совпадают друг с другом. Все символы получили разные коды, а выбранная запись проходит также проверку минимальной длины и указанного порядка. В ответ переносим битовую строку полностью, включая её начальные нули.

Ответ: 011.