Каждый лист имеет вес, который равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение

 

Этапы алгоритма Хаффмана:

Присвоение листьям дерева частоты вращения.

Выбираются два свободных листа с наименьшими весами. Создается родительский узел, равный сумме весов листьев.

Полученный родительский узел добавляется в список свободных листов, а соответствующие листья удаляются.

Одной дуге выходящей ставится в соответствие 1, а другой 0.

Шаги с первого по четвертый повторяются до тех пор, пока не останется свободный узел - корень дерева.

 

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

Среднее кол-во разрядов:

Энтропия

Как мы видим, величина среднего кол-ва разрядов получилась достаточно близкой к энтропии, следовательно, код можно считать эффективным. При этом для сравнения можно вычислить величину K для равномерного кода: