Метод Хафмена.

Более выгодным, чем код Шеннона — Фано, является так называемый код Хафмена. Пусть буквы (сообщения) входного алфавита имеют соответственно вероятности Предположим, что буквы в алфавите расположены в порядке убывания их вероятностей, т. е. Тогда алгоритм кодирования Хафмена состоит в следующем:

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

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

3. Повторяем шаги 1 и 2 до тех пор, пока не получим единственное сообщение, вероятность которого равна 1.

4. Проводя линии, объединяющие сообщения и образующие последовательные подмножества, получаем дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые слова можно построить, приписывая ветви, которые идут вниз, «0», а вверх — «1».

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

Построение кода Хафмена для сообщений, появляющихся с вероятностями 0,2; 0,2; 0,15; 0,13; 0,12; 0,1; 0,07; 0,03, изображено на рис. 5.3.

Как видно из рисунка, он совпадает с кодом Шеннона — Фано, рассмотренным в предыдущем разделе. Следовательно, по экономичности коды Шеннона — Фано и Хафмена в данном конкретном случае одинаковы. Это еще раз подтверждает, что код Шеннона — Фано достаточно хорош. Однако в общем случае код Хафмена экономичнее кода Шеннона — Фано.