Пример № 2.

Пример № 1.

, .

, .

Средняя длина двоичной последовательности на выходе кодера – это . Лучший код без памяти – это код, для которого средняя длина минимальна. Для того чтобы это выполнялось, необходимо найти соответствующий вектор Крафта . Простым перебором такую задачу при больших k осуществить трудно.

11.3.1 Код Хаффмана.Алгоритм кодирования Хаффмана дает эффективный способ поиска оптимального вектора Крафта. Код, получаемый с использованием этого оптимального вектора, называется кодом Хаффмана.

Далее приведен алгоритм построения кодового дерева Хаффмана (H-дерева):

Шаг 1. Инициализация. Список подлежащих обработки узлов состоит из узлов, где – мощность алфавита входных сообщений (количество букв в этом алфавите). Каждому из узлов приписывается вероятность появления буквы.

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

Теорема 2.Код Хаффмана является оптимальным.

Пусть дан ансамбль сообщений (алфавит): .

Энтропия ансамбля (алфавита): бит.

На рисунке 11.4 приведено кодовое дерево для ансамбля X. Движение при кодировании и декодировании происходит справа налево.

Рисунок 11.4 –Кодовое дерево Хаффмана

Таким образом, имеем:

Найдены кодовые слова и вектор Крафта: .

Проверим выполнение неравенства Крафта (11.4):

,

значит найденный код оптимальный.

Средняя длина двоичной последовательности, вычисленная по формуле (11.3) составляет

бит.

Очевидно, эта длина не меньше энтропии ( бит).

Найдем избыточность данного неравномерного кода:

бит.

Вычисленная избыточность показывает, что при данном кодировании тратится на 0,05 бит больше, чем могло бы быть затрачено в принципе при теоретически лучшем принципе кодирования.

Для декодирования выходной последовательности используется тоже двоичное кодовое дерево (дерево просматривается справа налево); если в потоке встречается нулевой бит, то берется верхняя ветвь, иначе – нижняя. Так продолжается до тех пор, пока не получен лист дерева, соответствующий исходному символу последовательности.

Средняя длина кодовых слов для данного алгоритма удовлетворяет неравенству

бит,

что и было показано ранее в примере № 2.

Закодируем при помощи построенного кода Хаффмана сообщение «abba»:

Видно, что длина кодовой цепочки символов составляет 8 бит = 1 байт.

Если бы сообщение «abba» кодировалось при помощи кодой таблицы ASCII (American Standard Code of Information Interchange – американский стандартный код информационного обмена), то длина кодовой цепочки символов составляет 4 байт (каждая буква кодируется одним байтом). Следовательно, в данном случае коэффициент сжатия, рассчитанный по формуле (11.1), составит

.

Выводы

1. Построенный в примере № 2 код Хаффмана действительно является оптимальным.

2. Средняя длина двоичной последовательности построенного кода Хаффмана составляет 2,45 бит.

3. Избыточность данного неравномерного кода составляет 0,05 бит.

4. Коэффициент сжатия сообщение «abba» кода Хаффмана составляет 4 для случая, когда размер источника сообщений определялся на основе кодой таблицы ASCII.