Криптографические приключения. Таинственные шифры и математические задачи. Р. В. Душкин
Читать онлайн книгу.
называют «хранением информации».
Папа расхаживал из стороны в сторону:
– Только в середине прошлого века были разработаны научные основы передачи информации. Основоположником теории информации стал Клод Шеннон, который опубликовал несколько фундаментальных статей по криптографии и кодированию.
Затем он взял мой блокнот и раскрыл его на той странице, где был записан придуманный мною код. Отец продолжил свой рассказ:
– То, что вы придумали, впервые было разработано Клодом Шенноном. Другой учёный, Роберт Фано, создал то же самое независимо от Шеннона, поэтому код носит двойное имя: Шеннона – Фано. Этот код – сжимающий и, как вы сами поняли, он основан на частотности символов: чем чаще встречается символ, тем короче его код. Но он также префиксный, то есть ни один код символа не является началом другого, и это свойство удобно использовать при декодировании. Можно посылать поток символов без разделения, а отделять для декодирования надо начальные биты последовательности, и это произойдёт однозначно. Давайте попробуем сделать это с какой-нибудь фразой.
Папа быстро написал на чистом листке последовательность бит без разделителей: 01100111111111100001101011000010110000110101110101. Но действительно, её декодирование было простым и однозначным. Мы с Катей закончили работу над этим упражнением практически одновременно. Тогда папа продолжил:
– Наверняка, когда вы считали частоты и их суммы, вы столкнулись с тем, что разделить пополам сумму частот было трудно. Суммы всё больше и больше не совпадали. Поэтому-то код Шеннона – Фано не считается оптимальным. Давайте я научу вас другому коду, у которого нет такого недостатка.
Папа открыл чистый лист и на самом верху вновь написал буквы русского алфавита и пробел в порядке убывания частоты. Затем под каждым символом он поставил его частоту. После этого начал своё объяснение:
– Будем строить дерево, как построили вы, но немного иное. Строить его будем снизу вверх, а не сверху вниз. Для этого возьмём два символа с самой маленькой частотой появления – Э и Ъ. Для них определим новую вершину, которую назовём «ЭЪ», и припишем ей значение частоты, равное сумме значений Э и Ъ. Соответственно, точно так же, как и в вашем алгоритме, из этой вершины ветвь налево пометим битом 0, а направо – битом 1. Затем новый символ «ЭЪ» со своей частотой вставим в список на своё место по порядку частоты, а два символа «Э» и «Ъ» из этого списка вычеркнем.
Папа быстро нарисовал начальное состояние дерева и перечислил новый список. Пока что было не очень понятно, чем такой способ отличается от нашего.
Но папа продолжал:
– Эта процедура повторяется до тех пор, пока не останется единственная вершина, включающая все символы, и частота которой равна сумме всех частот. Получается двоичное дерево, и у его вершин слева всегда бит «0», а справа – «1». И код для каждого символа собирается так же, как и в вашем случае: при переходе от вершины дерева к его листу, означающему конкретный символ, одна за другой собираются все биты ветвей, по которым совершается переход. Этот код называется кодом Хаффмана