Код Хаффмана

Близким к коду Шеннона-Фано, но ещё более выгодным является код Хаффмана. Постро-ение этого кода опирается на простое преобразование того алфавита, на котором запи-сываются передаваемые по линиям связи сообщения. Это преобразование называется сжатиемалфавита.

Пусть имеется алфавит A, содержащий буквы A₁; A₂; : : : ; A_n, вероятности появления ко-торых в сообщении соответственно равны p₁; p₂; : : : ; p_n. При этом мы считаем буквы рас-положенными в порядке убывания их вероятности (p₁ > p₂ > : : : > p_n). Условимся не различать между собой две наименее вероятные буквы алфавита (a_n−1; a_n) - новая буква b алфавита A₁: a₁; a₂; : : : ; a_n−2; b и вероятностью появления p₁; p₂; : : : ; p_n−2; (p_n−1+ p_n).

Алфавит A₁ называется алфавитом, подученным из алфавита A c помощью одной опера-ции сжатия. Расположим буквы нового алфавита A₁ в порядке убывания их вероятностей и подвергнем сжатию алфавит A₁. При этом мы придём к алфавиту A₂, получаемому из алфавита A двукратным сжатием. Продолжая эту процедуру мы будем приходить ко всё более коротким алфавитам. После N − 2-кратного сжатия мы придём к алфавиту A_n−2, содержащему всего 2 буквы.

ПримерПустьn= 6(алфавит из6букв),вероятности которых равны соответственно

0:4; 0:2; 0:2; 0:1; 0:05; 0:05.

Рассмотрим наш алфавит из 6 букв с соответствующими вероятностями:

Условимся приписывать двум буквам последнего алфавита кодовые обозначения 1 и 0. Если кодовые обозначения уже приписаны всем буквам алфавита A_j, то буквам преды-дущего алфавита A_j−1, сохранившимся и в алфавите A_j мы припишем те-же кодовые обозначения, которые они имели в алфавите A_j. Двум буквам алфавита A_j−1 : A^′; A", слившимся в одну букву b алфавита A_j мы припишем обозначения, получающиеся из ко-дового обозначения буквы b добавлением цифр 1 и 0 в конце.

Легко увидеть, что из самого построения получаемого таким образом кода Хаффмана вы-текает, что он удовлетворяет условию: никакое кодовое обозначение не является здесь начало другого, более длинного, кодового обозначения. Заметим также, что кодирова-ние некоторого алфавита по методу Хаффмана также, как и по методу Шеннона - Фано не является однозначно определённой процедурой, однако отметим, что среднее чис-ло k элем сигналов, приходящихся на одну букву алфавита для всех построенных кодов всегда остаётся одинаковым. Можно показать, что код Хаффмана является самым эко-номнымиз всех возможных в том смысле,что ни для какого другого метода кодирова-ния букв некоторого алфавита среднее число k элементарных сигналов, приходящихся на одну букву не может быть меньше того, какое получается при кодировании по методу Хаффмана.