Место для всех букв и сумма длин

Код нужен каждой букве алфавита, даже если в сообщении её нет: выбирая код одной буквы, нельзя занимать место, нужное остальным. Из этого же правила получается наименьшая сумма длин кодов.

Работаем с кодами А — 00, Б — 01, В — 10: в дереве свободна одна ветвь 11…. Сначала найдём в ней код Г, когда в алфавите есть ещё буква Д, затем — наименьшую сумму длин для шести букв.

Код может подходить ко всем заданным кодам и всё равно быть неверным, если остальным буквам не хватит места. Пусть сообщения могут содержать буквы А, Б, В, Г, Д. Известно: А — 00, Б — 01, В — 10. Нужно подобрать кратчайший код Г.

На первый взгляд подходит Г — 11: он не конфликтует с 00, 01 и 10. Но тогда таблица займёт всё дерево: всё, что начинается с 0, занято буквами А и Б, с 10 — буквой В, с 11 — буквой Г. Для Д не осталось ни одного возможного кода. Поэтому Г — 11 — недопустимый выбор для полного алфавита задачи.

Нужно разделить последнюю свободную ветвь: Г — 110, Д — 111. Теперь всё корректно.

Кратчайший код Г с учётом существования Д — 110.

Код может быть совместим со всеми уже заданными кодами, но при этом не позволять закончить таблицу для остальных букв.

Поэтому проверка нового кода состоит из двух частей:

1. он не нарушает условие Фано с уже назначенными кодами;
2. после его выбора можно назначить коды всем оставшимся буквам.

В задачах, где кодируются все буквы русского алфавита, это особенно важно. Если в сообщении встречаются только три буквы, остальные всё равно нельзя вычеркнуть из алфавита.

Если длины кодов не ограничены, одной свободной ветви хватает на любое число оставшихся букв. Пусть теперь кодируется весь русский алфавит, а А, Б, В и Г уже получили коды 00, 01, 10, 110. Двадцать девять оставшихся букв не нужно сразу рисовать в листьях: им хватит одной свободной ветви 111….

Свободную ветвь 111 можно разделить на сколько угодно кодов:

2

1110, 1111

3

1110, 11110, 11111

4

11100, 11101, 11110, 11111

В общем случае можно спуститься достаточно глубоко и выбрать нужное количество одинаковых по длине продолжений. Если нужно разместить 20 букв, достаточно добавить к свободному началу пять знаков: получится 2⁵ = 32 варианта.

Здесь нет противоречия с условием Фано: сам резервируемый префикс 111 не назначается отдельной букве. Он обозначает место, внутри которого будут построены коды остальных букв.

Наименьшую сумму длин получают, разветвляя свободную ветвь ровно столько раз, сколько нужно букв. Пусть алфавит содержит шесть букв: А, Б, В, Г, Д, Е. Известно: А — 00, Б — 01, В — 10. Нужно найти наименьшую сумму длин кодов всех шести букв.

Для трёх оставшихся букв свободна только ветвь 11…. Использовать сам код 11 нельзя: тогда две другие буквы останутся без кодов. Разделим ветвь: 110 и 111 — два места, а нужны три. Разделим ещё одно из них:

Получаем Г — 110, Д — 1110, Е — 1111. Длины новых кодов 3, 4, 4, их сумма 11. Сумма длин всех шести кодов: 2 + 2 + 2 + 3 + 4 + 4 = 17.

Обрати внимание, какую сумму спрашивают. Сумма длин всех кодов — это заданные коды плюс новые (здесь 6 + 11 = 17); сумма длин оставшихся букв — только новые (11).

Если свободных ветвей несколько, делят самую короткую свободную вершину. Разделить вершину длины d — значит вместо одного места длины d получить два места длины d + 1. Чем короче делимая вершина, тем короче оба новых места.

Изменим один код примера: пусть В — 100 вместо 10. Теперь свободны две ветви разной длины: 101… и 11…. Для Г, Д, Е нужно три места, а их два — делим более короткую вершину 11:

Места 101, 110, 111 — длины 3, 3, 3, сумма новых длин 9. Если бы разделили длинную 101, получили бы 2 + 4 + 4 = 10 — хуже.

Иногда выгодно разделить короткую вершину, даже когда мест уже хватает. Пусть заданы А — 01, Б — 10, В — 110, Г — 1110, Д — 11110, а коды нужны ещё двум буквам Е и Ж. Свободны 00… и 11111…: два места длин 2 и 5, сумма 7. Но если разделить 00 на 000 и 001, получим 3 + 3 = 6.

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

• Место для всехновый код не занимает последнюю свободную ветвь, пока остались буквы
• Одна свободная ветвьвмещает сколько угодно букв, если длины не ограничены
• Сумма длинделят самую короткую свободную вершину
• Короткая вершинаиногда её выгодно разделить, даже когда мест хватает
• Сумма всех кодоввключает и заданные коды