Главная Промышленная автоматика.

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

Пример 3.11. В табл. 3.2 показаны две возможные кодировки для нащих пяти символов. Ясно, что первый код обладает префиксным свойством, поскольку любая последовательность из трех битов будет префиксом для другой последовательности из трех битов; другими словами, любая префиксная последовательность однозначно идентифицируется символом. Алгоритм декодирования для этого кода очень прост: надо поочередно брать по три бита и преобразовать каждую группу битов в соответствующие символы. Например, последовательность 001010011 соответствует исход-, ному сообщению bed.

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

Символ

Вероятность

Код 1

Код 2

0.12

0.40

0.15

0.08

0.25

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

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

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

* Отсюда следует очевидный вывод, что символы с большими вероятностями появления должны иметь самые короткие коды. - Прим. ред.



меньшего множества символов (где символы а и Ь заменены одним символом х). Код для исходного множества символов получается из кодов замешаюших символов путем добавления О и 1 перед кодом замешаюшего символа, и эти два новых кода принимаются как коды заменяемых символов. Например, код символа а будет соответствовать коду символа х с добавленным нулем перед этим кодом, а для кода символа Ъ перед кодом символа х будет добавлена единица.

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

Пример 3.12. Двоичные деревья для кодов 1 и 2 из табл. 3.2 показаны на рис. 3.14 (дерево слева соответствует коду 1, а дерево справа - коду 2). □


а b с d е ad

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

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

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

Пример 3.13. Последовательные шаги выполнения алгоритма Хаффмана для кодируемых символов и их вероятностей, заданных в табл. 3.2, представлены на рис. 3.15. Здесь видно (рис. 3.15,д), что символы а, Ь, с, d и е получили соответственно коды 1111, О, ПО, 1110 и 10. В этом примере сушествует только одно нетривиальное дерево, соответствуюшее оптимальному коду, но в обшем случае их может быть несколько. Например, если бы символы 6 и е имели вероятности соответственно 0.33 и 0.32, то после шага алгоритма, показанного на рис. 3.15,в, можно было бы комбинировать Ь и е, а не присоединять е к большому дереву, как это сделано на рис. 3.15,г. D



0.12 0.40 0.15 0.08 0.25

а b С d е а. Исходная ситуация

0.20 0.40 0.15 0.25

d а b с е б. Слияние а с d

0.60

0.35


0.40 0.25

b е d а

в Слияние а, с/ с с

1.00


0.40

d а г. Слияние а, с, d с е

d а д. Законченное дерево

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

Теперь опишем необходимые структуры данных. Во-первых, для представления двоичных деревьев мы будем использовать массив TREE (Дерево), состояший из записей следующего типа:

record

leftchild: integer; rightchild: integer; parent: integer

Указатели в поле parent (родитель) облегчают поиск путей от листа к корню при записи кода символов. Во-вторых, мы используем массив ALPHABET (Алфавит), также состояший из записей, которые имеют следующий тип:

record

symbol: char; probability: real; leaf: integer { курсор }

В этом массиве каждому символу (поле symbol), подлежащему кодированию, ставится в соответствие вероятность его появления (поле probability) и лист, меткой которого он является (поле leaf). В-третьих, для представления непосредственно деревьев необходим массив FOREST (Лес). Этот массив будет состоять из записей с полями weight (вес) и root (корень) следующего типа:





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 [27] 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0037