Кодовое дерево и кратчайший код

Задача подтемы: сообщения состоят из букв А, Б, В, Г; известны А — 1, Б — 000, В — 011. Найди кратчайший код Г, а если таких несколько — с наименьшим числовым значением.

Все коды таблицы удобно видеть сразу — как пути в двоичном дереве: буква стоит в конце своего пути, и ниже неё других букв нет. Сначала нарисуем дерево знакомой таблицы А — 0, Б — 10, В — 110, Г — 111 и прочитаем по нему сообщение, затем вернёмся к задаче.

Каждый код — путь от корня: за каждый знак делаем шаг по ветви 0 или 1. Вместо постоянного сравнения строк удобно изображать все возможные коды в виде дерева. Начинаем с начальной точки — она называется корнем дерева. Из каждой точки можно сделать два шага: по ветви 0 или по ветви 1. Пройденные знаки образуют код.

Например, один шаг 0 даёт код 0; шаги 1, затем 0 дают 10; шаги 1, 1, 0 дают 110. Таблица А — 0, Б — 10, В — 110, Г — 111 изображается так:

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

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

На дереве условие Фано звучит так: буквы стоят в листьях, и ниже буквы других букв нет. Если назначили букве код 10, то под ней нельзя размещать коды 100, 101, 1000, 1001 и все остальные, которые начинаются с 10.

И наоборот: если где-то ниже уже есть код 100, то вершину 10 нельзя назначить другой букве — она лежит на пути к существующему коду.

Это и есть две проверки нового кода из подтемы 1, показанные геометрически: «новый код — начало старого» значит, что новая буква встала на путь к старой; «старый код — начало нового» — что новая буква встала под старой.

Сообщение читают по дереву: от корня до буквы, а затем снова от корня. Пусть получено 111010110. Идём от корня по знакам: пока вершина лежит на пути к буквам, читаем дальше; как только пришли в букву — записываем её и возвращаемся в корень.

Получается 111 | 0 | 10 | 110 — ГАБВ. Не нужно специально выбирать «самый длинный подходящий код»: при условии Фано первое найденное кодовое слово уже определяет букву.

Если сообщение закончилось, а прочитанный остаток не образует кодовое слово, последовательность не является полной записью сообщения по этой таблице. Например, одиночное 11 здесь не обозначает букву: это только начало кодов В и Г.

Свободная ветвь — вершина, на которой и под которой нет ни одной буквы. Возьмём неполную таблицу А — 1, Б — 000, В — 011 и разберём, где можно разместить новую букву.

• 1 занято буквой А, все продолжения 1… запрещены; так же заняты 000… и 011….
• 0, 00 и 01 нельзя назначить новым буквам: они являются началами существующих кодов.
• Остаются две полностью свободные ветви: 001… и 010….

Что означает «ветвь 001… свободна»? В ней можно использовать сам код 001 для одной буквы — либо не занимать 001, а размещать буквы глубже: 0010, 0011 и так далее. Это принципиальный выбор:

Свободную вершину можно занять одной буквой или разветвить для нескольких букв. Одновременно сделать и то и другое нельзя.

Если назначили Г — 001, то использовать 0010 и 0011 для других букв уже нельзя. Если нужны Г — 0010 и Д — 0011, то 001 остаётся промежуточной вершиной, а не кодом отдельной буквы.

При поиске свободных ветвей записывай их у ближайших к корню свободных вершин: достаточно записать 001, а не перечислять отдельно 0010, 0011, 00100 и все остальные продолжения.

Кратчайший код ищут по длине, а среди кодов одной длины — по числовому значению. Найдём кратчайший код Г для таблицы А — 1, Б — 000, В — 011; если вариантов несколько, выберем код с наименьшим числовым значением. Проверяем длины по порядку:

1

0 — начало 000 и 011; 1 уже занятодного знака недостаточно

2

00 — начало 000; 01 — начало 011; 10 и 11 начинаются с занятого 1двух знаков тоже недостаточно

3

000 и 011 заняты, 1… не подходит; 001 и 010 подходяткратчайшая длина — 3

Это ровно две свободные ветви с рисунка. Они имеют одинаковую длину, меньшее числовое значение у 001. Ответ: 001.

Почему одинаковые по длине двоичные коды можно сравнивать слева направо? Смотрим на первый знак, в котором они различаются: код, у которого в этой позиции стоит 0, меньше. У 001 и 010 первый знак одинаковый, во втором у первого кода 0, у второго — 1. Поэтому первый меньше.

Иногда спрашивают код с наибольшим числовым значением — тогда среди кратчайших берут последний: здесь это 010. Длина при этом всё равно минимальная: сначала длина, потом значение.

Два правила оформления ответа:

• если спрашивают код, записываем саму последовательность, включая ведущие нули;
• если спрашивают длину, записываем количество знаков.

Для найденного кода ответы на эти разные вопросы — 001 и 3.

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