Применение деревьев. Представление сообщений кодами Хаффмана

Рассмотрим пример применения двоичных деревьев в качестве структур данных. Для этого рассмотрим задачу конструирования кодов Хаффмана, используемых для сжатия информации. Предположим, мы имеем сообщения, состоящие из последовательности символов. В каждом сообщении символы независимы и появляются с известной вероятностью, не зависящей от позиции в сообщении. Например, мы имеем сообщения, состоящие из пяти символов а, b, с, d, е, которые появляются в сообщениях с вероятностями 0.12, 0.4, 0.15, 0.08 и 0.25 соответственно.

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

В таблице показаны две возможные кодировки для наших пяти символов. Ясно, что первый код 1 обладает префиксным свойством, поскольку любая последовательность из трех битов будет префиксом для другой последовательности из трех битов, т.е. любая префиксная последовательность однозначно идентифицируется символом. Алгоритм декодирования для этого кода следующий: надо поочередно брать по три бита и преобразовывать каждую группу битов в соответствующие символы. Например, последовательность 001010011 соответствует исходному сообщению bсd.

Таблица. Два двоичных кода

Несложно проверить, что второй код также обладает префиксным свойством. Процесс декодирования здесь не отличается от аналогичного процесса для первого кода. Единственная сложность для второго кода заключается в том, что нельзя сразу всю последовательность битов разбить на отдельные сегменты, соответствующие символам, так как символы могут кодироваться и двумя и тремя битами. Для примера рассмотрим двоичную последовательность 1101001, которая опять представляет символы bсd. Первые два бита 11 однозначно соответствуют символу b, поэтому их можно удалить, тогда получится 01001. Здесь 01 также однозначно определяет символ с и т.д.

Задача конструирования кодов Хаффмана заключается в следующем: имея множество символов и значения вероятностей их появления в сообщениях, построить такой код с префиксным свойством, чтобы средняя длина кода (в вероятностном смысле) последовательности символов была минимальной. Мы хотим минимизировать среднюю длину кода для того, чтобы уменьшить длину вероятного сообщения, т.е. чтобы сжать сообщение. Чем короче среднее значение длины кода символов, тем короче закодированное сообщение. В частности, первый код из нашего примера имеет среднюю длину кода 3. Это число получается в результате умножения длины кода каждого символа на вероятность появления этого символа. Второй код имеет среднюю длину 2.2, поскольку символы a и d имеют суммарную вероятность появления 0.20 и длина их кода составляет три бита, тогда как другие символы имеют код длиной 2.

Появляется вопрос. Можно ли придумать код, который был бы лучше второго кода? Ответ положительный: существует код с префиксным свойством, средняя длина которого равна 2.15. Это наилучший возможный код с теми же вероятностями появления символов. Способ нахождения оптимального префиксного кода называется алгоритмом Хаффмана. В этом алгоритме находятся два символа а и b с наименьшими вероятностями появления и заменяются одним фиктивным символом, например х, который имеет вероятность появления, равную сумме вероятностей появления символов а и b. Затем, используя эту процедуру рекурсивно, находим оптимальный префиксный код для меньшего множества символов (где символы а и b заменены одним символом х). Код для исходного множества символов получается из кодов замещающих символов путем добавления 0 и 1 перед кодом замещающего символа, и эти два новых кода принимаются как коды заменяемых символов. Например, код символа а будет соответствовать коду символа х с добавленным нулем перед этим кодом, а для кода символа b перед кодом символа х будет добавлена единица.

Можно рассматривать префиксные коды как пути на двоичном дереве: прохождение от узла к его левому сыну соответствует 0 в коде, а к правому сыну – 1. Если мы пометим листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева. Префиксное свойство гарантирует, что нет символов, которые были бы метками внутренних узлов дерева (не листьев), и наоборот, помечая кодируемыми символами только листья дерева, мы обеспечиваем префиксное свойство кода этих символов.

Двоичные деревья для кодов 1 и 2 из таблицы показаны на рис. 26 (дерево слева соответствует коду 1, а дерево справа – коду 2).

Рис. 26 – Двоичные деревья, представляющие коды с префиксным свойством

Для реализации алгоритма Хаффмана используется лес, т.е. совокупность деревьев, чьи листья помечаются символами, для которых разрабатывается кодировка, а корни помечаются суммой вероятностей всех символов, соответствующих листьям дерева. Эти суммарные вероятности называются весом дерева. Вначале каждому символу соответствует дерево, состоящее из одного узла, в конце работы алгоритма получается одно дерево, все листья которого будут помечены кодируемыми символами. В результирующем дереве путь от корня к любому листу представляет код для символа-метки этого листа, составленный по схеме, согласно которой левый сын узла соответствует 0, а правый – 1.

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

Рассмотрим на примере последовательные шаги выполнения алгоритма Хаффмана. Кодируемые символы и их вероятности заданы в таблице. Этапы построения дерева Хаффмана показаны на рис. 27.

Рис. 27 – Этапы построения дерева Хаффмана

На рисунке видно, что символы а, b, с, d и е получили соответственно коды 1111, 0, 110, 1110 и 10. В этом примере существует только одно нетривиальное дерево, соответствующее оптимальному коду, но в общем случае их может быть несколько. Например, если бы символы b и е имели вероятности соответственно 0.33 и 0.32, то после шага алгоритма, показанного на рис. 27.в, можно было бы комбинировать b и е, а не присоединять е к большому дереву, как это сделано на рис. 27.г.

Для представления бинарных деревьев используется массив TREE, состоящий из записей следующего типа:

Также используется массив ALPHABET, состоящий из записей, имеющих следующий тип:

Для представления непосредственно деревьев необходим массив FOREST, состоящих из записей, имеющих тип:

Исходное состояние трех массивов показано на рис. 28.

Рис. 28 – Исходное состояние массивов

На рис. 29 показано состояние трех массивов, соответствующее лесу, на рис. 27.в.

Рис. 29 – Промежуточное состояние массивов

После завершения работы алгоритма код каждого символа можно определить следующим образом. Найти в массиве ALPHABET запись с нужным символом в поле symbol. Затем по значению поля leaf этой же записи определить местоположение записи в массиве TREE, которая соответствует листу, помеченному рассматриваемым символом. Далее нужно последовательно переходить по указателю parent от текущей записи, например соответствующей узлу n, к записи в массиве TREE, соответствующей его родителю р. По родителю р определяют, в каком его поле, leftchild или rightchild, находится указатель на узел n, т.е. является ли узел n левым или правым сыном, и в соответствии с этим печатается 0 (для левого сына) или 1(для правого сына). Затем выполняется переход к родителю узла р и определяется, является ли его сын р правым или левым, и в соответствии с этим печатается следующая 1 или 0. Таки образом продолжается до корня дерева. В результате код символа будет напечатан в виде последовательности битов, но в обратном порядке. Чтобы распечатать полученную последовательность в прямом порядке, нужно каждый очередной бит помещать в стек, а затем распечатать содержимое стека в обычном порядке.

Лекции 11-12

План лекции:

1. Идеально сбалансированные бинарные деревья.

2. Бинарные деревья поиска.

3. Сбалансированные деревья поиска.

4. Операции над деревьями.

5. Вставка элемента в АВЛ-дерево.

Не нашли, что искали? Воспользуйтесь поиском: