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

Известные коды: F → 0110; B → 0111; S → 0011; C → 100; X → 0101; D → 101; Y → 0010; E → 0100; Z → 000. Начальные нули являются частью кодового слова и не отбрасываются.

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

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

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

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

Первый допустимый уровень имеет длину 2. Все более короткие варианты исключены. На этом уровне с учётом требуемого числового порядка выбираем 11. Пример полного дополнения: A → 11.

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

Ответ: 11.