Криптографические приключения: таинственные шифры - Страница 17

Папа расхаживал из стороны в сторону:

— Только в середине прошлого века были разработаны научные основы передачи информации. Основоположником теории информации стал Клод Шеннон, который опубликовал несколько фундаментальных статей по криптографии и кодированию.

Затем он взял мой блокнот и раскрыл его на той странице, где был записан придуманный мною код. Отец продолжил свой рассказ:

— То, что вы придумали, впервые было разработано Клодом Шенноном. Другой учёный, Роберт Фано, создал то же самое независимо от Шеннона, поэтому код носит двойное имя: Шеннона — Фано. Этот код — сжимающий и, как вы сами поняли, он основан на частотности символов: чем чаще встречается символ, тем короче его код. Но он также префиксный, то есть ни один код символа не является началом другого, и это свойство удобно использовать при декодировании. Можно посылать поток символов без разделения, а отделять для декодирования надо начальные биты последовательности, и это произойдёт однозначно. Давайте попробуем сделать это с какой-нибудь фразой.

Папа быстро написал на чистом листке последовательность бит без разделителей: 01100111111111100001101011000010110000110101110101. Но действительно, её декодирование было простым и однозначным. Мы с Катей закончили работу над этим упражнением практически одновременно. Тогда папа продолжил:

— Наверняка, когда вы считали частоты и их суммы, вы столкнулись с тем, что разделить пополам сумму частот было трудно. Суммы всё больше и больше не совпадали. Поэтому-то код Шеннона — Фано не считается оптимальным. Давайте я научу вас другому коду, у которого нет такого недостатка.

Папа открыл чистый лист и на самом верху вновь написал буквы русского алфавита и пробел в порядке убывания частоты. Затем под каждым символом он поставил его частоту. После этого начал своё объяснение:

— Будем строить дерево, как построили вы, но немного иное. Строить его будем снизу вверх, а не сверху вниз. Для этого возьмём два символа с самой маленькой частотой появления — Э и Ъ. Для них определим новую вершину, которую назовём «ЭЪ», и припишем ей значение частоты, равное сумме значений Э и Ъ. Соответственно, точно так же, как и в вашем алгоритме, из этой вершины ветвь налево пометим битом 0, а направо — битом 1. Затем новый символ «ЭЪ» со своей частотой вставим в список на своё место по порядку частоты, а два символа «Э» и «Ъ» из этого списка вычеркнем.

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

Но папа продолжал:

— Эта процедура повторяется до тех пор, пока не останется единственная вершина, включающая все символы, и частота которой равна сумме всех частот. Получается двоичное дерево, и у его вершин слева всегда бит «0», а справа — «1». И код для каждого символа собирается так же, как и в вашем случае: при переходе от вершины дерева к его листу, означающему конкретный символ, одна за другой собираются все биты ветвей, по которым совершается переход. Этот код называется кодом Хаффмана в честь предложившего его Дэвида Хаффмана. Теперь давайте построим такое дерево и соответствующие коды для частот символов русского языка и посмотрим, что получится.

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

По этому дереву легко было вычислить новые коды для каждого символа. Надо было только всегда помнить, что линия налево обозначает «0», а линия направо — «1». Так что, например, букве «Р» соответствовал код 00011, а букве «З» — 101110. В итоге у нас получилась вот такая таблица:

После этого папа предложил:

— Теперь давайте возьмём какое-нибудь сообщение и сравним его длину в трёх наших кодировках. Я посчитаю длину для самой первой кодировки, Екатерина — для кодировки из сна Кирилла, а Кирилл для только что построенной. А в качестве сообщения возьмём такую фразу: «На колоссальной дощатой террасе близ палисадника веснушчатая Агриппина Саввична потчевала исподтишка коллежского асессора Фаддея Аполлоновича ветчиной, винегретом и другими яствами под аккомпанемент виолончели и брандспойта».

Мы с Катей переглянулись. Отец явно наслаждался нашим впечатлением и смотрел на нас, широко улыбаясь. Я сказал:

— Папа, я половину слов не понял, а вторую половину не расслышал. Что ты такое придумал?

— Это фраза для проверки грамотности. Я своим сотрудникам устраиваю такие диктанты, чтобы не расслаблялись.

— Может быть, что-то другое попробуем закодировать? А то мы до вечера провозимся.

— Хорошо, давайте другое. Предлагаю такое сообщение: «ЗАВТРА В ПЕРВОЙ ПОЛОВИНЕ ДНЯ МЫ СОБЕРЁМСЯ ВТРОЁМ И ОТПРАВИМСЯ НА ГАРЕТОЕ ПРОВЕРИТЬ КАК ТАМ ВОДИЦА». И при этом подсчитаем только буквы, не будем считать пробелы.

Это была прекрасная фраза — не только своей простотой, но и обещанием интересного завтрашнего дня. Мы с энтузиазмом принялись за работу.

Конечно, папа подсчитал число бит самым первым. Ему и нужно-то было только умножить количество символов в сообщении на пять. А вот мы с Катей помучались. В итоге получилось так: