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