— Будем строить дерево, как построили вы, но немного иное. Строить его будем снизу вверх, а не сверху вниз. Для этого возьмём два символа с самой маленькой частотой появления — Э и Ъ. Для них определим новую вершину, которую назовём «ЭЪ», и припишем ей значение частоты, равное сумме значений Э и Ъ. Соответственно, точно так же, как и в вашем алгоритме, из этой вершины ветвь налево пометим битом 0, а направо — битом 1. Затем новый символ «ЭЪ» со своей частотой вставим в список на своё место по порядку частоты, а два символа «Э» и «Ъ» из этого списка вычеркнем.
Папа быстро нарисовал начальное состояние дерева и перечислил новый список. Пока что было не очень понятно, чем такой способ отличается от нашего.
Но папа продолжал:
— Эта процедура повторяется до тех пор, пока не останется единственная вершина, включающая все символы, и частота которой равна сумме всех частот. Получается двоичное дерево, и у его вершин слева всегда бит «0», а справа — «1». И код для каждого символа собирается так же, как и в вашем случае: при переходе от вершины дерева к его листу, означающему конкретный символ, одна за другой собираются все биты ветвей, по которым совершается переход. Этот код называется кодом Хаффмана в честь предложившего его Дэвида Хаффмана. Теперь давайте построим такое дерево и соответствующие коды для частот символов русского языка и посмотрим, что получится.
Папа раздал нам листки с записанными частотами символов, и мы втроём погрузились в вычисления. Конечно, папа сделал эту работу первым. Я сделал вторым, а Катя задержалась, но в конце концов и у неё получилось. Мы сравнили результаты, и они у всех троих оказались одинаковыми:
По этому дереву легко было вычислить новые коды для каждого символа. Надо было только всегда помнить, что линия налево обозначает «0», а линия направо — «1». Так что, например, букве «Р» соответствовал код 00011, а букве «З» — 101110. В итоге у нас получилась вот такая таблица:
После этого папа предложил:
— Теперь давайте возьмём какое-нибудь сообщение и сравним его длину в трёх наших кодировках. Я посчитаю длину для самой первой кодировки, Екатерина — для кодировки из сна Кирилла, а Кирилл для только что построенной. А в качестве сообщения возьмём такую фразу: «На колоссальной дощатой террасе близ палисадника веснушчатая Агриппина Саввична потчевала исподтишка коллежского асессора Фаддея Аполлоновича ветчиной, винегретом и другими яствами под аккомпанемент виолончели и брандспойта».
Мы с Катей переглянулись. Отец явно наслаждался нашим впечатлением и смотрел на нас, широко улыбаясь. Я сказал:
— Папа, я половину слов не понял, а вторую половину не расслышал. Что ты такое придумал?
— Это фраза для проверки грамотности. Я своим сотрудникам устраиваю такие диктанты, чтобы не расслаблялись.
— Может быть, что-то другое попробуем закодировать? А то мы до вечера провозимся.
— Хорошо, давайте другое. Предлагаю такое сообщение: «ЗАВТРА В ПЕРВОЙ ПОЛОВИНЕ ДНЯ МЫ СОБЕРЁМСЯ ВТРОЁМ И ОТПРАВИМСЯ НА ГАРЕТОЕ ПРОВЕРИТЬ КАК ТАМ ВОДИЦА». И при этом подсчитаем только буквы, не будем считать пробелы.
Это была прекрасная фраза — не только своей простотой, но и обещанием интересного завтрашнего дня. Мы с энтузиазмом принялись за работу.
Конечно, папа подсчитал число бит самым первым. Ему и нужно-то было только умножить количество символов в сообщении на пять. А вот мы с Катей помучались. В итоге получилось так:
Пятибитный код: 485 бит.
Код Шеннона — Фано: 373 бит.
Код Хаффмана: 375 бит.
Папа озадаченно покачал головой и сказал, что иногда такое происходит, поскольку для некоторых редко используемых букв код Хаффмана использует более длинные последовательности бит, нежели код Шеннона — Фано, и, похоже, это как раз наш случай. Однако это упражнение показало нам, что два кода, которые папа назвал «сжимающими», действительно позволяют использовать меньше бит для передачи сообщений.
Незаметно за всеми этими занятиями наступили сумерки. Мы с папой пошли проводить Катю до дома. Мы припозднились — Катина бабушка уже места себе не находила. Папа долго извинялся и пообещал впредь следить за временем, а Кате поручил научить бабушку пользоваться телеграфом. На этом мы и расстались.
Как и планировалось, сразу после завтрака мы сели на велосипеды, заехали за Катей и отправились на Гаретое. Ехать надо было порядочно, но расстояние мы преодолели быстро — и нам открылась водная гладь, с которой не мог сравниться ни один пруд в селе. Папа сказал, что это торфяное болото, каких много в округе, а название своё оно получило из-за того, что в своё время весь торф здесь выгорел. Теперь тут довольно чистая вода, а поскольку деревенский скот сюда не доходит, местные жители предпочитают купаться в Гаретом, а не в прудах.
Вода оказалась не то чтобы тёплой, но и не холодной. Болото было совсем неглубоким, так что солнечные лучи хорошо прогревали воду за день, но утром было зябко. Папа же сказал, что иногда под вечер вода здесь становится тёплой, как парное молоко.
