2.3.4 Пример: деревья кодирования по Хаффману

Этот раздел дает возможность попрактиковаться в использовании списковых структур и абстракции данных для работы с множествами и деревьями. Они применяются к методам представления данных как последовательностей из единиц и нулей (битов). Например, стандартный код ASCII, который используется для представления текста в компьютерах, кодирует каждый символ как последовательность из семи бит. Семь бит позволяют нам обозначить 27, то есть 128 различных символов. В общем случае, если нам требуется различать n символов, нам потребуется log2 n бит для каждого символа. Если все наши сообщения составлены из восьми символов A, B, C, D, E, F, G, и H, мы можем использовать код с тремя битами для каждого символа, например

A 000 C 010 E 100 G 110 B 001D 011F 101H 111

С таким кодом, сообщение

BACADAEAFABBAAAGAH

кодируется как строка из 54 бит

001000010000011000100000101000001001000000000110000111

Такие коды, как ASCII и наш код от A до H, известны под названием кодов с фиксированной длиной, поскольку каждый символ сообщения они представляют с помощью одного и того же числа битов. Иногда полезно использовать и коды с переменной длиной (variable-length), в которых различные символы могут представляться различным числом битов. Например, азбука Морзе не для всех букв алфавита использует одинаковое число точек и тире. В частности, E, наиболее частая (в английском) буква, представляется с помощью одной точки. В общем случае, если наши сообщения таковы, что некоторые символы встречаются очень часто, а некоторые очень редко, то мы можем кодировать свои данные более эффективно (т. е. с помощью меньшего числа битов на сообщение), если более частым символам мы назначим более короткие коды. Рассмотрим следующий код для букв с A по H:

A 0C 1010 E 1100 G 1110

B 100 D 1011 F 1101 H 1111

С таким кодом то же самое сообщение преобразуется в строку

100010100101101100011010100100000111001111

В этой строке 42 бита, так что она экономит более 20% места по сравнению с приведенным выше кодом с фиксированной длиной.

Одна из сложностей при работе с кодом с переменной длиной состоит в том, чтобы узнать, когда при чтении последовательности единиц и нулей достигнут конец символа. В азбуке Морзе эта проблема решается при помощи специального кода-разделителя (separator code) (в данном случае паузы) после последовательности точек и тире для каждой буквы. Другое решение состоит в том, чтобы построить систему кодирования так, чтобы никакой полный код символа не совпадал с началом (или префиксом) кода никакого другого символа. Такой код называется префиксным (prefix). В вышеприведенном примере A кодируется 0, а B 100, так что никакой другой символ не может иметь код, который начинается на 0 или 100.

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

Глава 2. Построение абстракций с помощью данных {A B C D E F G H} 17

A 8

{B

C D E F G H} 9

{B C D} 5

B3

D} 2

{E

F G H} 4

C 1 D 1

{E F} 2

E 1 F 1

H} 2

G 1 H 1

Рис. 2.18: Дерево кодирования по Хаффману.

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

Рисунок 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.

Порождение деревьев Хаффмана

Если нам дан «алфавит» символов и их относительные частоты, как мы можем породить «наилучший» код? (Другими словами, какое дерево будет кодировать сообщения при помощи наименьшего количества битов?) Хаффман дал алгоритм для решения этой задачи и показал, что получаемый этим алгоритмом код - действительно наилучший код с переменной длиной для сообщений, где относительная частота символов соответствует частотам, для которых код строился. Здесь мы не будем доказывать оптимальность кодов Хаффмана, но

42

покажем, как эти коды строятся.42

Алгоритм порождения дерева Хаффмана весьма прост. Идея состоит в том, чтобы упорядочить дерево так, чтобы символы с наименьшей частотой оказались дальше всего от корня. Начнем с множества терминальных вершин, содержащих символы и их частоты, как указано в исходных данных, из которых нам надо построить дерево. Теперь найдем два листа с наименьшими весами и сольем их, получая вершину, у которой предыдущие две являются левым и правым потомками. Вес новой вершины равен сумме весов ее ветвей. Исключим два листа из исходного множества и заменим их новой вершиной. Продолжим этот процесс. На каждом шаге будем сливать две вершины с самыми низкими весами, исключая их из множества и заменяя вершиной, для которой они являются левой и правой ветвями. Этот процесс заканчивается, когда остается только одна вершина, которая и является корнем всего дерева. Вот как было порождено дерево Хаффмана на рисунке 2.18:

Исходный набор листьев {(A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)} Слияние{(A 8) (B 3) ({C D} 2) (E 1) (F 1) (G 1) (H 1)}

Слияние{(A 8) (B 3) ({C D} 2) ({E F} 2) (G 1) (H 1)}

Слияние{(A 8) (B 3) ({C D} 2) ({E F} 2) ({G H} 2)}

Слияние{(A 8) (B 3) ({C D} 2) ({E F G H} 4)}

Слияние{(A 8) ({B C D} 5) ({E F G H} 4)}

Слияние{(A 8) ({B C D E F G H} 9)}

Окончательное слияние {({A B C D E F G H} 17)}

Алгоритм не всегда приводит к построению единственно возможного дерева, поскольку на каждом шаге выбор вершин с наименьшим весом может быть не единственным. Выбор порядка, в котором будут сливаться две вершины (то есть, какая из них будет левым, а какая правым поддеревом) также произволен.

42Обсуждение математических свойств кодов Хаффмана можно найти в Hamming 1980.