Криптографические приключения. Таинственные шифры и математические задачи

Душкин Роман

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

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

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

– То, что вы придумали, впервые было разработано Клодом Шенноном.

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

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

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

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

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

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

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

– Эта процедура повторяется до тех пор, пока не останется единственная вершина, включающая все символы, и

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

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

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

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

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

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

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

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

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

Конец ознакомительного фрагмента.