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

Известные коды: А → 1; Б → 00; В → 0100; Г → 0111. Начальные нули являются частью кодового слова и не отбрасываются.

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

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

Нужно минимизировать сумму длин неизвестных кодовых слов. Поэтому каждой неизвестной букве приписываем вес 1. Неизвестные буквы: Д, Е.

Обозначим F(d, S) минимальную стоимость размещения набора букв S внутри полностью свободной ветви, начало которой имеет длину d. Стоимость — сумма «вес буквы × полная длина кода». Для пустого набора F(d, ∅) = 0; для единственной буквы a имеем F(d, {a}) = d · wₐ: ей отдаём корень свободной ветви.

Если букв две или больше, разделяем их на два непустых набора T и S ∖ T и добавляем к началу соответственно 0 и 1. Общая формула: F(d, S) = min [F(d + 1, T) + F(d + 1, S ∖ T)] по всем таким разделениям. Одну занятую дочернюю ветвь можно поднять к родителю, уменьшив длины, поэтому для поиска минимума достаточно этих разветвлений. Формула заканчивается на одноэлементных наборах и перебирает все существенные формы дерева.

При единичных весах стоимость зависит только от количества букв. Начальные значения для свободной ветви: F(d, 0) = 0, F(d, 1) = d; для k ≥ 2 выбираем минимум F(d + 1, j) + F(d + 1, k − j) при j от 1 до k − 1. Затем распределяем k букв между свободными началами. При добавлении очередной ветви пробуем отдать ей от 0 до k букв и берём наименьшую сумму стоимости старых ветвей и новой.

Минимальные суммы для 0, 1, …, 2 букв после добавления каждой свободной ветви:
После ветви 0101: 0, 4, 10.
После ветви 0110: 0, 4, 8.

Получен минимум для неизвестных кодов: 8. Он достижим, например, при назначении:
Д: код 0110, длина 4, вес 1; вклад = 1 · 4 = 4.
Е: код 0101, длина 4, вес 1; вклад = 1 · 4 = 4.

Известные коды не входят в требуемую сумму: вопрос касается только оставшихся букв.

Искомая длина = 0 + 8 = 8.

Проверка: все назначенные слова лежат в свободных ветвях; внутри каждой ветви они являются разными листьями, поэтому условие Фано выполнено и между новыми кодами, и со старыми. Сумма вкладов соответствует найденному минимуму. Таблица перебрала все распределения между свободными ветвями, а рекурсия — все разветвления внутри них, поэтому меньшая стоимость невозможна.

Ответ: 8.