Страница 12 из 12
– Ты лучше скажи, для чего это нужно. Ведь мы с Катей не смогли придумать, как использовать новый код.
– Это потому, что у вас не было под рукой телеграфа. Если бы попробовали отправлять сообщения при помощи этого нового кода, то сразу поняли бы.
– И все-таки расскажи, пожалуйста.
– Всё просто. В том коде, который я вам дал, каждая буква представлена пятью битами. А в твоём коде длина представления буквы зависит от её частоты: чем чаще, тем короче. Теперь понимаешь?
– То есть для длинных передач моим кодом надо будет меньше раз жать на ключ, чем для передач твоим?
– Абсолютно верно. Давай попробуем. У Кати есть копия этого кода?
– Должна быть, она перерисовала его себе.
– Тогда включай телеграф и вызывай её.
Прежде всего я закодировал при помощи нового кода сообщение: «КАТЯ ПРИЕЗЖАЙ ПАПА РАССКАЖЕТ НОВУЮ ТЕМУ». Получилось довольно длинно и необычно. Я включил телеграф и передал сигнал начала сессии. Пять минут не было никакого ответа, и тогда я снова передал этот сигнал. На этот раз ответ пришёл через две минут. Что ж, алгоритм установки сессии работал.
Я передал подготовленный шифр и стал ждать. В ответ пришло сообщение: «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». И код для каждого символа собирается так же, как и в вашем случае: при переходе от вершины дерева к его листу, означающему конкретный символ, одна за другой собираются все биты ветвей, по которым совершается переход. Этот код называется кодом Хаффмана в честь предложившего его Дэвида Хаффмана. Теперь давайте построим такое дерево и соответствующие коды для частот символов русского языка и посмотрим, что получится.
Папа раздал нам листки с записанными частотами символов, и мы втроём погрузились в вычисления. Конечно, папа сделал эту работу первым. Я сделал вторым, а Катя задержалась, но в конце концов и у неё получилось. Мы сравнили результаты, и они у всех троих оказались одинаковыми:
По этому дереву легко было вычислить новые коды для каждого символа. Надо было только всегда помнить, что линия налево обозначает «0», а линия направо – «1». Так что, например, букве «Р» соответствовал код 00011, а букве «З» – 101110. В итоге у нас получилась вот такая таблица:
После этого папа предложил:
– Теперь давайте возьмём какое-нибудь сообщение и сравним его длину в трёх наших кодировках. Я посчитаю длину для самой первой кодировки, Екатерина – для кодировки из сна Кирилла, а Кирилл для только что построенной. А в качестве сообщения возьмём такую фразу: «На колоссальной дощатой террасе близ палисадника веснушчатая Агриппина Саввична потчевала исподтишка коллежского асессора Фаддея Аполлоновича ветчиной, винегретом и другими яствами под аккомпанемент виолончели и брандспойта».
Мы с Катей переглянулись. Отец явно наслаждался нашим впечатлением и смотрел на нас, широко улыбаясь. Я сказал:
– Папа, я половину слов не понял, а вторую половину не расслышал. Что ты такое придумал?
– Это фраза для проверки грамотности. Я своим сотрудникам устраиваю такие диктанты, чтобы не расслаблялись.
– Может быть, что-то другое попробуем закодировать? А то мы до вечера провозимся.
Конец ознакомительного фрагмента.
Текст предоставлен ООО «ЛитРес».
Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.
Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.