Автор: Антон Лосев
Вступление
В статье разберём несколько типичных заданий, покажем, как строить кодовые деревья, соблюдать условие Фано и оптимизировать длину кодов.
Задача 1: кодирование букв
Для соблюдения условия Фано удобно использовать дерево кодов, которое строится сверху вниз. Ветви, уходящие влево, будут содержать нули, а уходящие вправо — единицы. Построим дерево для известных букв.
Начнём с буквы А, её код — 00. Чтобы найти её позицию дважды, сделаем ветвление влево, а чтобы не запутаться, каждую вершину будем ветвить сразу в обе стороны.
Следующая буква — B, её код — 010, значит, путь от верха дерева до неё должен выглядеть как $0 \to 1 \to 0$.
Тем же способом отмечаем на дереве все известные буквы.
Далее нужно определить, в какие свободные вершины дерева можно разместить буквы C и L. Ещё раз обратимся к условию задачи. Нам требуется найти минимальную суммарную длину кодов, то есть сумма для C и L должна быть как можно меньше.
Если посмотреть на построенное дерево, то единственной свободной ветке, которую можно продолжить, соответствует код $111$. Остальные ветки использовать нельзя, иначе будет нарушено условие Фано. При этом код $111$ нельзя сразу присвоить одной из букв, потому что тогда для второй не останется свободных кодов.
Следовательно, мы должны продолжить дерево от узла $111$, и тогда каждой из букв C и L достанется код длиной 4 символа.
Поскольку длины кодов для C и L одинаковы, их конкретное распределение не влияет на результат. Для одной буквы будет код $1110$, для другой — $1111$.
Суммарная длина кодов составит: $4 + 4 = 8$.
Ответ: 8
Задача 2: выбор вариантов
По аналогии с предыдущей задачей построим дерево и отметим на нём все известные буквы.
Остаются две свободные позиции с кодами 010 и 101. Нам нужен код наименьшей длины. Согласно схеме варианты длины 2 невозможны: все комбинации 00, 01, 10 и 11 уже ведут к другим буквам. Следовательно, минимальная возможная длина кода — 3.
По условию необходимо выбрать максимальный код, поэтому из двух вариантов нам подходит 101, а не 010.
Ответ: 101
Задача 3: кодирование слова
Проанализируем слово «Кодируй» и таблицу. Нам неизвестны коды для букв К и Й. Обе встречаются в слове по одному разу, и наша задача — подобрать для них такие коды, чтобы общая длина всего слова оказалась минимальной.
Построим дерево на основе известных букв.
Свободные позиции — 00, 100, 1010. Нам нужны коды минимальной длины, поэтому мы выбираем 00 и 100. Куда отнести букву К, а куда «Й», не имеет значения, т. к. в слове каждая встречается ровно по одному разу. Пусть К = 00, Й = 100.
Сосчитаем суммарную длину кода для всего слова: К — 00 (2), О — 110 (3), Д — 0101 (4), И — 111 (3), Р — 0100 (4), У — 011 (3), Й — 100 (3).
Сложим длины всех символов: 2 + 3 + 4 + 3 + 4 + 3 + 3 = 22.
Ответ: 22
Задача 4: эксперт по шифрованию
Поскольку построение дерева для каждого варианта требует времени, удобно сначала построить базу, отметив все буквы, коды которых известны. Затем, скопировав этот рисунок, мы в каждом из вариантов по-разному разместим буквы О, Р, М, Д, Е и достроим дерево до конца. Так проще сравнивать результаты, не теряя времени на лишние построения.
Прежде чем размещать оставшиеся буквы, определим, как часто они встречаются в слове: Р — 1, О — 4, М — 1, Д — 1, Е — 0.
Буквы, которые встречаются большее количество раз, будем вешать в дереве как можно выше, а букву Е вообще неважно куда, т. к. её нет в слове (но разместить на дереве её нужно обязательно!)
Рассмотрим два способа построения.
Вариант 1
Сейчас есть всего две свободные позиции: 00 и 110. Попробуем букве О присвоить код 00, тогда, чтобы разместить оставшиеся 4 буквы, придётся продолжить ветвление от кода 110.
После ветвления все коды получились длины 5, поэтому порядок расставления букв Р, М, Д, Е неважен.
Посчитаем получившуюся длину слова:
Г — 10 (2), Р — 11000 (5), О — 00 (2), М — 11001 (5), О — 00 (2), О — 00 (2), Т — 01 (2), В — 111 (3), О — 00 (2), Д — 11010 (5).
2 + 5 + 2 + 5 + 2 + 2 + 2 + 3 + 2 + 5 = 30.
Вариант 2
Попробуем не ставить на позицию 00 сразу букву О, а разветвить её на один уровень, чтобы у оставшихся букв код не получался слишком длинным.
Получилось три кода длины 3: 000, 001, 110. Разместим О на любое место, пусть О = 000. Осталось разместить 4 буквы, тогда разветвим две свободные позиции на один уровень вниз.
Получилось 4 кода длины 4, поэтому порядок расстановки букв Р, М, Д, Е неважен.
Посчитаем получившуюся длину слова:
Г — 10 (2), Р — 0010 (4), О — 000 (3), М — 0011 (4), О — 000 (3), О — 000 (3), Т — 01 (2), В — 111 (3), О — 000 (3), Д — 1100 (4).
2 + 4 + 3 + 4 + 3 + 3 + 2 + 3 + 3 + 4 = 31.
В первом варианте длина слова получилась меньше, значит, ответ — 30.
Итог
При решении задач на кодирование важно помнить нескольких ключевых моментов:
-
Учитывать отсутствующие буквы\
Даже если буква не встречается в слове, но указана в условии, её необходимо разместить в дереве. -
Повторно использовать дерево\
В задачах, где нужно рассмотреть несколько способов размещения букв (как в задаче 4), не стоит каждый раз рисовать дерево заново. Достаточно один раз построить основу с известными кодами, а затем, скопировав этот рисунок, достраивать разные варианты отдельно. Если их несколько, лучше нарисовать все: часто разница составляет всего один символ, и наглядная схема поможет не ошибиться в расчётах. Такой подход ускоряет решение и позволяет сосредоточиться на сравнении результатов. -
Помнить о частоте символов\
Буквы, встречающиеся чаще, стоит кодировать более короткими кодами, чтобы уменьшить общую длину закодированного сообщения.
Потренироваться и закрепить свои знания можно на подборке заданий.