164
Глава 2. Построение абстракций с помощ ью данных
Одна из сложностей при работе с кодом с переменной длиной состоит в том, чтобы
узнать, когда при чтении последовательно сти единиц и нулей достигнут конец символа.
В азбуке Морзе эта проблема решается при помощи специального кода-разделителя
(separator code) (в данном случае паузы) после последовательности точек и тире для
каждой буквы. Другое решение состоит в том, чтобы построить систему кодирования
так, чтобы никакой полный код символа не совпадал с началом (ил и префиксом) кода
никакого другого символа. Такой код называется префиксным (prefix). В вышеприведен-
ном примере A кодируется 0, а B 100, так что никакой другой символ не может иметь
код, который начинается на 0 или 100.
В общем случае можно добиться существенной экономии, если использовать коды
с переменной длиной, использующие относительные частоты символов в подлежащих
кодированию сообщениях. Одна из схем такого кодирования называется кодированием
по Хаффман у, в честь своего изобретателя, Дэвида Хаффмана. Код Хаффмана может
быть представлен как бинарное дерево , на листьях которого лежат кодируемые символы.
В каждом нетерминальном узле находится множество символов с тех листьев, которые
лежат под данным узлом. Кроме того, каждому символу на листе дерева присваивается
вес (представляющий собой относительную частоту), а каждый нетерминальный узел
имеет ве с, который равняется сумме весов листьев, лежащих под данным узлом. Веса
не используются в процессе кодирования и декодирования. Ниже мы увидим, как они
оказываются полезными при построении дерева.
Рисунок 2.18 изображает дерево Хаффмана для кода от A до H, показанного выше.
Веса в вершинах дерева указывают, что дерево строилось для сообщений, где A встреча-
ется с относительной частотой 8, B с относительной частотой 3, а все остальные буквы
с относительной частотой 1.
Имея дерево Хаффмана, можно найти код любого символа, если начать с корня и
двигаться вниз до тех пор, пока не будет достигнута концевая вершина, содержащая
этот символ. Каждый раз, как мы спускаемся по левой ветви, мы добавляем 0 к коду, а
спускаясь по правой ветви , добавляем 1. (Мы решаем, по какой ветке двигаться, прове-
ряя, не является ли одна из веток концевой вершиной, а также содержит ли множество
при вершине символ, который мы ищем.) Например, начиная с корня на к артине 2.18, мы
попадаем в концевую вершину D, сворачивая на правую дорогу, затем на левую, затем
на правую, затем , наконец, снова на правую ветвь; следовательно, код для D — 1011.
Чтобы раскодировать последовательность битов при помощи дерева Хаффмана, мы
начи наем с корня и просматриваем один з а другим биты в последовательности, чтобы
решить, нужно ли нам спускаться по левой или по правой ветви. Каждый раз, к ак мы
добираемся до листовой вершины, мы порождаем новый символ сообщения и возвра-
щаемся к вершине дерева, чтобы найти следующий символ. Например, пусть нам дано
дерево, изображенное на рисунке, и последовательность 10001010. Начиная от корня,
мы идем по правой ветви (поскольку первый бит в строке 1), затем по левой (поскольку
второй бит 0), затем опять по левой (поскольку и третий бит 0). Здесь мы попадаем в
лист, соответствующий B, так что первый символ декодируемого сообщения — B. Мы
снова начинаем от корня и идем налево, поскольку следующий бит строки 0. Тут мы по-
падаем в лист, из ображающий символ A. Мы опять начинаем от корня с остатком строки
1010, двигаемся направо, налево, направо, налево и приходим в C. Таким образом, все
сообщение было BAC.