Алгоритм построения кодового дерева кода Хаффмана.

1. Инициализация. Список «подлежащих обработке» узлов состоит из N₀ = N узлов, каждому из которых приписана вероятность одного из сообщений.

2. До тех пор, пока число узлов N₀ > 1, повторяются следующие действия:

                                                                                                            В списке необработанных узлов находим два узла с наименьшими вероятностями. Они исключаются из списка и вместо них вводится новый узел, которому приписывается суммарная вероятность двух исключенных узлов. Новый узел связывается ребрами с исключенными узлами. Число необработанных узлов N₀ уменьшается на 1, N₀ N₀ - 1

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

Пример. 12.3. Рассмотрим ансамбль буквенных сообщений {a, b, c, d, e, f} вероятностями букв {0,35, 0,2, 0,15, 0,1, 0,1, 0,1} соответственно. Кодовое дерево и код Хаффмана показаны на рис. 12.2. Энтропия источника H(x) = 2,4016. Средняя длина кодовых слов равна =2,45. Согласно свойствам 1-4 не существует кода для X со средней длиной кодовых слов меньшей, чем 2,45.

Избыточность кода Хаффмана

Из теоремы 12.3 следует, что для построенных по алгоритму Хаффмана кодов средняя длина кодовых слов удовлетворяет неравенству

,                                        (12.4)

где H(x) – энтропия ансамбля.

Разность  называется избыточностью неравномерного кода. При кодировании с избыточностью r на каждое сообщение тратится на r бит больше, чем в принципе можно было бы потратить, если использовать теоретически наилучший (возможно, нереализуемый) способ кодирования.

Итак, из (12.4) следует, что для кода Хаффмана избыточность r ≤ 1. Хотелось бы получить более точную оценку средней длины кодовых слов. Р. Галлагер, получил гораздо более точную оценку избыточности, наложив ограничение на максимальную из вероятностей сообщений.

Теорема 12.5. Пусть P₁ – наибольшая из вероятностей сообщений конечного дискретного ансамбля. Тогда избыточность кода Хаффмана для этого ансамбля удовлетворяет неравенствам

где H(P₁) = –P₁ log P₁ – (1– P₁)log(1– P₁) – энтропия двоичного ансамбля, и

s = 1 – log e – log log e» 0,08607.

Код Шеннона - Фано

Рассмотрим источник, выбирающий буквы из множества X ={1,...,N} с вероятностями {P₁,…,P_N}. Считаем, что буквы упорядочены по убыванию вероятностей, т.е. P₁ ≥ P₂ ≥ … ≥ P_N.

Кодирование Шеннона-Фано имеет большое сходство с кодированием Хаффмана. Рассмотрим алгоритм вычисления кодов Шеннона-Фано (для наглядности возьмём в качестве примера последовательность 'aa bbb cccc ddddd'. Для вычисления кодов, необходимо создать таблицу уникальных символов сообщения x_i и их вероятностей P(x_i), и отсортировать её в порядке невозрастания вероятности символов.

Далее, таблица символов делится на две группы таким образом, чтобы каждая из групп имела приблизительно одинаковую частоту по сумме символов. Первой группе устанавливается начало кода в '0', второй в '1'. Для вычисления следующих бит кодов символов, данная процедура повторяется рекурсивно для каждой группы, в которой больше одного символа. Таким образом для нашего случая получаем следующие коды символов:

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