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

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

(Оптимальное кодирование)

Метод кодирования и построения кодового дерева, основанный на равновероятном использовании символов алфавита и  использующий статистическую независимость  символов,  приводит к коду с минимальной  средней длиной слова не всегда, а только в случае выполнения равенства p()=.

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

Процедура оптимального кодирования  сообщений заданного множества  и произвольного алфавита представлена ниже:

По заданию, мне надо было с помощью этого метода представить коды букв руссого алфавита в сжатом виде.

  Первоначально я расположил  буквы русского алфавита в  порядке убывания вероятностей (все  вероятности я умножил на , чтобы легче вести подчеты):

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

Теперь посчитаем Эффективность  кодирования по формуле