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

Известные коды: С → 0; К → 1011. Начальные нули являются частью кодового слова и не отбрасываются.

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

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

Кодируем слово КОСОГОР. Для неизвестных кодов частоты букв равны: Г: 1, Д: 0, О: 3, Р: 1. Длина сообщения равна сумме произведений частоты буквы на длину её кода. Символы с частотой 0 всё равно должны иметь код: весь заданный алфавит обязан удовлетворять условию Фано.

Обозначим 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)] по всем таким разделениям. Одну занятую дочернюю ветвь можно поднять к родителю, уменьшив длины, поэтому для поиска минимума достаточно этих разветвлений. Формула заканчивается на одноэлементных наборах и перебирает все существенные формы дерева.

Для нескольких свободных ветвей обозначим через Gⱼ(S) минимум после первых j ветвей. Изначально доступен только пустой набор со стоимостью 0. При добавлении ветви глубины d проверяем все T ⊆ S и выбираем минимум Gⱼ₋₁(S ∖ T) + F(d, T). Это учитывает и неиспользованную ветвь, когда T пуст. Порядок наборов в следующих строках: ∅, Г, Д, ГД, О, ГО, ДО, ГДО, Р, ГР, ДР, ГДР, ОР, ГОР, ДОР, ГДОР.

Таблица минимальной стоимости для каждого набора:
После ветви 100: 0, 3, 0, 4, 9, 16, 12, 17, 3, 8, 4, 9, 16, 22, 17, 23.
После ветви 1010: 0, 3, 0, 3, 9, 13, 9, 14, 3, 7, 3, 8, 13, 19, 14, 20.
После ветви 11: 0, 2, 0, 2, 6, 9, 6, 9, 2, 5, 2, 5, 9, 13, 9, 14.

Получен минимум для неизвестных кодов: 14. Он достижим, например, при назначении:
Г: код 1010, длина 4, вес 1; вклад = 1 · 4 = 4.
Д: код 1000, длина 4, вес 0; вклад = 0 · 4 = 0.
О: код 11, длина 2, вес 3; вклад = 3 · 2 = 6.
Р: код 1001, длина 4, вес 1; вклад = 1 · 4 = 4.

Вклад известных кодов: 1 · 1 + 1 · 4 = 5.

Код слова по буквам: 1011 | 11 | 0 | 11 | 1010 | 11 | 1001.

Искомая длина = 5 + 14 = 19.

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

Ответ: 19.