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

Известные коды: А → 00; Л → 1101; Б → 1100; Р → 1010; Е → 010; С → 1110; И → 011; Т → 1011; К → 1111. Начальные нули являются частью кодового слова и не отбрасываются.

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

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

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

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

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

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

Ответ: 100.