Длина закодированного слова

Длина закодированного слова — сумма длин кодов всех его букв с повторами, поэтому частым буквам выгодно давать короткие коды. Это самый частый тип задания 4 последних лет.

Главный пример страницы — слово МОЛОКО: сообщения состоят из букв М, О, Л, К, Н, заданы коды О — 00 и К — 01. Сначала разберёмся, что именно считать.

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

Например, для таблицы А — 0, Б — 10, В — 110, Г — 111 сумма длин всех кодов равна 1 + 2 + 3 + 3 = 9, а длина сообщения АААБВ — 1 + 1 + 1 + 2 + 3 = 8. Это разные величины.

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

Итого 3 + 2 + 3 = 8. Общее правило:

Длина сообщения = сумма произведений частот букв на длины их кодов.

Буква с нулевой частотой не увеличивает длину конкретного сообщения. Но её код по-прежнему занимает место в дереве.

Буква, которой нет в слове, всё равно требует места в дереве. Вернёмся к МОЛОКО. Алфавит М, О, Л, К, Н; заданы О — 00, К — 01. Нужно уменьшить длину записи слова МОЛОКО. Сначала считаем частоты: О — 3, К — 1, М — 1, Л — 1, Н — 0.

Известные коды дают неизменный вклад: 3 · 2 + 1 · 2 = 8. Остаётся выбрать коды М, Л и Н. Ветвь 0… полностью занята кодами 00 и 01, поэтому все новые коды должны находиться в ветви 1….

Если забыть о Н, можно предложить М — 10, Л — 11. Тогда длина слова получилась бы 8 + 2 + 2 = 12. Но это неверное решение: букве Н не осталось места.

Правильный вариант — разделить ветвь, как в подтеме 3: М — 10, Л — 110, Н — 111.

Тогда длина слова 8 + 2 + 3 = 13. Проверим запись целиком: М | О | Л | О | К | О — это 10 | 00 | 110 | 00 | 01 | 00, длины 2 + 2 + 3 + 2 + 2 + 2 = 13.

Все буквы, которых нет в слове, можно временно представить одной резервной ветвью. Если бы кодировался весь русский алфавит, решение МОЛОКО не изменилось бы: место 111 стало бы резервом для Н и всех остальных букв, а длина слова осталась бы 13. Потом резерв делится на нужное количество кодов, как в подтеме 3.

Так можно, если длина кодов не ограничена — в задании 4 так почти всегда.

При подсчёте суммы длин всей таблицы каждая буква учитывается отдельно.

Для уже выбранных мест короткие коды выгодно назначать более частым буквам. Предположим, мы уже выбрали два свободных кодовых слова — длины 2 и длины 4. Буква А встречается пять раз, буква Б — один раз.

Если короткий код отдать А: 5 · 2 + 1 · 4 = 14. Если короткий код отдать Б: 5 · 4 + 1 · 2 = 22. Первый вариант лучше на 8 бит. Причина проста: сокращение кода А на два знака экономит два знака при каждом из пяти появлений, а увеличение кода Б на два знака добавляет их только один раз.

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

Получается порядок действий для наименьшей длины слова:

1. Посчитать частоты букв слова и вклад букв с заданными кодами.
2. Найти свободные ветви. Буквам вне слова, если они есть, нужно одно резервное место.
3. Буквам слова по убыванию частоты давать самый короткий свободный код, после которого остаётся место всем остальным буквам и резерву.
4. Проверить, не выгоднее ли разделить короткую вершину, — об этом следующий раздел.

Самый короткий код для частой буквы иногда ухудшает весь результат. Поэтому, когда у частой буквы есть выбор, рисуют оба варианта дерева и сравнивают длины слова. Пример: алфавит из семи букв А, Б, В, Г, Д, Е, Ж, заданы Д — 01, Е — 10, Ж — 110. В сообщении А встречается 4 раза, Б — 3 раза, В и Г — по 2.

Букв Д, Е, Ж в сообщении нет, но их заданные коды занимают место. Свободны две ветви: 00… и 111…. Первая начинается на глубине 2, вторая — на глубине 3.

Попробуем сразу дать самой частой букве А кратчайший код 00. Теперь Б, В, Г нужно разместить в 111…, и лучшее размещение для них — Б — 1110, В — 11110, Г — 11111. Длина сообщения 4 · 2 + 3 · 4 + 2 · 5 + 2 · 5 = 40.

Теперь попробуем не занимать вершину 00 одной буквой, а разделить её: А — 000, Б — 001, В — 1110, Г — 1111.

Код самой частой буквы стал длиннее, но всё сообщение сократилось: 4 · 3 + 3 · 3 + 2 · 4 + 2 · 4 = 37. Почему? Код А удлинился на один знак, и это добавило 4 бита — по одному на каждое появление. А коды Б, В, Г укоротились на один знак каждый и сэкономили 3 + 2 + 2 = 7 бит. Мы добавили четыре бита, а сэкономили семь.

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

• Величинакод одной буквы, сумма длин или длина слова — разные ответы
• Длина словасумма «частота × длина кода»
• Буква вне словачастота 0, но место в дереве нужно
• Частым — короткиена готовых местах; заданные коды не переставляют
• Короткая вершинасравни с вариантом, где она разделена