Читать книгу "Криптографические приключения. Таинственные шифры и математические задачи - Роман Душкин"

Кроме того, он привёз какие-то странные и сложные устройства, упакованные в мягкую бумагу и пупырчатый полиэтилен (я сразу начал лопать пузырьки). Они были похожи на лазерные установки. Отец убрал их на чердак. Я пока не стал спрашивать, что это такое, но про себя подумал, что дело идёт к какой-то заварушке, раз папа привёз лазерные ружья. Вероятно, будем отбиваться от инопланетян. Ведь он сам рассказывал мне, что в тамбовских лесах иногда приземляются летающие тарелки с зелёными человечками.

В общем, мы целый день переезжали и обустраивались. Пришла Катя, мы немного поиграли, а она скачала свою почту за всё время, пока не было доступа в сеть. Так день и прошёл — в заботах и отдыхе. Я был рад, что папа вернулся, и не хотел думать ни о чём сложном.

На следующий день я показал папе свои выкладки о разделении множества символов на две половины в соответствии с их частотностью. Отец внимательно изучил всё, что я ему показал, а потом спросил, где я это вычитал. Я горячо возразил, что всё придумал сам (ну, может быть, Катя немного помогла). А вообще идея пришла ко мне во сне.

Тогда отец рассказал, что я разработал метод сжатия информации в соответствии с основной теоремой теории информации для каналов без шума. По его словам, эту тему изучают в технических институтах на третьем курсе. Я сразу запутался в терминах, которые он использовал, поэтому попросил:

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

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

— И все-таки расскажи, пожалуйста.

— Всё просто. В том коде, который я вам дал, каждая буква представлена пятью битами. А в твоём коде длина представления буквы зависит от её частоты: чем чаще, тем короче. Теперь понимаешь?

— То есть для длинных передач моим кодом надо будет меньше раз жать на ключ, чем для передач твоим?

— Абсолютно верно. Давай попробуем. У Кати есть копия этого кода?

— Должна быть, она перерисовала его себе.

— Тогда включай телеграф и вызывай её.

Прежде всего я закодировал при помощи нового кода сообщение: «КАТЯ ПРИЕЗЖАЙ ПАПА РАССКАЖЕТ НОВУЮ ТЕМУ». Получилось довольно длинно и необычно. Я включил телеграф и передал сигнал начала сессии. Пять минут не было никакого ответа, и тогда я снова передал этот сигнал. На этот раз ответ пришёл через две минут. Что ж, алгоритм установки сессии работал.

Я передал подготовленный шифр и стал ждать. В ответ пришло сообщение: «01101 01000 10111 00101 00011 01110 01101 00101 01111 01110 01101 01000 01100 00000 11110», что соответствовало тексту «НИЧЕГО НЕ ПОНИМАЮ». Тогда я передал обычным кодом: «ИСПОЛЬЗУЙ НОВЫЙ КОД». Через какое-то время пришло сообщение: «0100 11001 11010 11111100 11001 0110 1000 0100», что при декодировании новым кодом значило «ЕДУ ЖДИТЕ».

Катя приехала примерно через пятнадцать минут. Папа посадил нас на низенькую скамеечку около входа в наш штаб, а сам принялся рассказывать об открытии, которое мы сделали. Папа у меня любит подходить издалека, поэтому он начал с теории информации. Впрочем, это было достаточно интересно, и я узнал много нового.

Папа рассказывал:

— Люди с древнейших времён передают информацию как в пространстве, так и во времени. Например, полководец отправляет гонца с посланием своим офицерам. Это — передача информации в пространстве, от источника информации к её потребителям. А если учёный пишет научный трактат для потомков, то это передача информации во времени. Конечно, можно передавать информацию только в будущее время. И такую передачу называют «хранением информации».

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

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

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

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

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

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

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

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

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

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

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

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