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

Известные коды: A → 00; F → 1001; B → 1000; S → 1100; C → 010; X → 1010; D → 011; Y → 1101; Z → 111. Начальные нули являются частью кодового слова и не отбрасываются.

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

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

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

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

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

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

Ответ: 1011.