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

У меня произошло что-то вроде лёгкого головокружения, и головоломка внезапно сошлась. Деление пополам при помощи бросания монеты, дерево переходов, двоичные числа и биты, и, наконец, частоты символов — всё это соединилось в идее, которая засияла у меня в голове. Я даже зажмурился от нахлынувшего потока ощущений. Мне казалось, что мысли и идеи обрели форму и заворочались у меня в голове, царапая мозг.

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

После этого я нарисовал первый уровень дерева выбора. Левая ветвь обозначала те символы, которые лежат слева от разделительной черты, а правая, соответственно, правые. Левую ветвь я обозначил символом «0», а правую — символом «1».

Затем каждую половину символов я разделил ещё на две части так, чтобы сумма частот каждой равнялась примерно 25 %. Сделать это точно оказалось ещё сложнее, так что получилось так, как получилось:

Я продолжал делить множества символов снова и снова пополам, чтобы при каждом делении получались два новых множества примерно с одинаковой суммой частот. К моему удивлению, множества, расположенные левее, быстро закончились, то есть я дошёл до отдельных символов. А вот множества с правой стороны делились несколько дольше. Соответственно, дерево выбора получилось не равномерным и симметричным, а скособоченным на правую сторону.

После этого пришло время собрать коды для каждого символа. Получилась вот такая таблица:

Очевидно, что чем чаще встречается символ в русском языке, тем короче в этой таблице его двоичное представление. Мы с Катей смотрели на результаты моих упражнений и не могли понять, что это такое и для чего может пригодиться. Но я чувствовал, что открыл что-то очень важное, полезное и интересное. Похоже, надо дождаться отца, чтобы показать ему и узнать, где это можно применять.

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

Дни были однообразны. Мы с Катей катались на велосипедах по окрестностям села. Я сопоставлял всё то, что вижу, со своими наведёнными воспоминаниями. Обычно всё совпадало в общих чертах, но детали, конечно, были мне в новинку. Катя вообще всё воспринимала как какую-то диковинку. Например, она удивленно рассматривала деревенских коров и коз.

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

Он так и не приехал до самого вечера, и я пошёл укладываться. Он не отвечал на мои телеграммы, но я понимал, что он не может этого сделать за рулём. Но он мог бы уж остановиться и написать, чтобы я не волновался! В общем, я не получил никаких сигналов и в конце концов уснул.

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

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

С собой папа привёз кучу разных вещей. Во-первых, всё заднее сиденье было уставлено бутылями с водой. Действительно, привезённая из города вода у нас уже почти закончилась. Хотя у тёти Кати я пил колодезную воду, но папа не советовал мне этого делать. Не знаю уж почему, ведь он в детстве пил ту же самую воду. Несколько часов мы выгружали эти бутыли в подсобку нашего штаба.

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

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

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

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

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

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

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

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