4.3.5. Кодирование источника дискретных сообщений методом Хаффмена

Рассмотрим еще один подход к кодированию, предложенный Хаффменом [6], на примере источника сообщений, заданного в табл. 4.3.

Таблица 4.3. Построение кода Хаффмена

Алгоритм построения сжимающего кода Хаффмена включает в себя следующие действия.

1.   Все  символов дискретного источника располагаются в таблице в порядке убывания вероятностей.

2.   Два символа, имеющих наименьшие вероятности, объединяются в один блок, а их вероятности суммируются.

3.   Ветви скобки, идущей к большей вероятности, присваивается символ «1», а идущей к меньшей – символ «0».

4.   Операции 2 и 3 повторяются до тех пор, пока не сформируется один блок с вероятностью единица.

5.   Записывается код для каждого символа источника; при этом считывание кода осуществляется справа налево.

Среднее число символов на одну букву для полученного кода

.

Таким образом, для данного примера кодирование методами Хаффмена и Шеннона–Фано приводит к одинаковой эффективности. Однако опыт кодирования показывает, что код Хаффмена часто оказывается экономичнее кода Шеннона–Фано.

Рассмотренные методы построения сжимающих кодов широко известны и имеют практическое применение. Длина кодовой комбинации таких кодов зависит от вероятности выбора соответствующей буквы алфавита: наиболее вероятным буквам сопоставляются короткие кодовые комбинации, а менее вероятным – более длинные.