Код Хафмена

Код Хафмена строится на базе кодового дерева.

Кодовое дерево – специальный граф, отображающий запись всех возможных K-ичных n-разрядных чисел, используемых в качестве кодовых комбинаций для кодирования сообщений в количестве M Ј Kⁿ. При этом каждое число отображается одним из узлов графа. Из каждого узла выходит K ветвей, которые связывают этот узел с другими. Количество символов, входящих в число, соответствующее данному узлу, называется его порядком.

Рассмотрим граф для двоичного трехэлементного кода.

Рис. 13 Кодовое дерево двоичного трехэлементного кода

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

• сообщению с наибольшей вероятностью должен соответствовать узел наименьшего порядка;
• по крайней мере два сообщения с минимальными вероятностями должны кодироваться узлами максимального порядка;
• если выбран некоторый узел порядка i, то все узлы более высокого порядка, связанные с ним, не могут быть использованы для кодирования, иначе не будет выполняться однозначная различимость комбинаций, основанная на том, что ни одна из них не должна быть началом другой;
• для кодирования сообщений могут не быть использованы все возможные узлы максимального порядка; это означает, что не все узлы предыдущего порядка являются полными (полным называется узел, из которого выходят все возможные K ветвей);
• если объединить все сообщения, закодированные узлами i-го порядка, то узел (i – 1)-го порядка будут соответствовать сообщению с эквивалентной вероятностью
  .

При укрупнении сообщений, то есть при переходе от узлов порядка i к узлам порядка (i – 1) количество сообщений уменьшается на (K – 1), если узел порядка (i – 1) был неполным, либо на (m₀ – 1), если узел порядка (max – 1) был неполным и если из него выходило m₀ ветвей, заканчивающихся m₀ узлами порядка max (max – максимальный порядок узлов дерева).

Величина m₀ заключена в следующих пределах:

2 Ј m₀ Ј K

Определим точное значение m₀. Предположим, что реализуется процесс укрупнения сообщений в направлении от узлов максимального порядка к корню дерева. Если общее количество исходных сообщений было M, то

M = 1 + a(K – 1) + (m₀ – 1)

где M – общее количество сообщений; a – число полных узлов, встретившихся в процессе укрупнения; (a – целое число).

Из этого соотношения можно определить m₀, подбирая целые числа a так, чтобы выполнялось условие:

2 Ј m₀ Ј K.

Построение кода Хафмена начинается с определения m₀, то есть числа тех наименее вероятных сообщений, которые должны быть объединены на первом этапе построения кода (кодового дерева).

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

Следует отметить, что метод Хафмена применим для источника сообщений, появляющимися с любой вероятностью, а не только с вероятностью целой степени основания кода.

Пример 1. Дан ансамбль сообщений:

Построить двоичный код Хафмена.

Так как основание кода K = 2, m₀ = 2, то есть вообще не будет неполных узлов.

Кодовое дерево для данного кода представлено на рис. 14.

Рис. 14

Пример 2. Закодировать источник сообщения из примера 1 троичным кодом.

По правилам построения кодов Хафмена сначала нужно определить m₀:

Если a = 1, то m₀= 4 > 3, поэтому m₀ = 4 не подходит.

Если a = 2, то m₀ = 2 < 3, следует принять m₀= 2.

Процесс построения кода изображен на рис.15.

Рис. 15

---