Алгоритм Хаффмана

Пример

Для примера возьмём слово "Миссисипи". Тогда алфавит будет [math]A= \{[/math] и, м, п, с [math]\} [/math], а набор весов [math]W=\{4, 1, 1, 3\}[/math]:

Узел	и	м	п	с
Вес	4	1	1	3

По алгоритму возьмем два символа с наименьшей частотой - это м и п. Сформируем из них новый узел мп весом 2 и добавим его к списку узлов:

Узел	и	мп	с
Вес	4	2	3

Затем объединим в один узел узлы мп и c:

Узел	и	мпс
Вес	4	5

И, наконец, объединяем два узла и и мпс. Итак, мы получили дерево:

Конечно же, здесь будет нормальная картинка

Соответствующая ему таблица кодов:

Символ	и	м	п	с
Код	0	100	101	11

Таким образом, закодированное слово "миссисипи" будет выглядеть как "1000111101101010". Длина закодированного слова - 16 бит. Стоит заметить, что если бы мы использовали для кодирования каждого символа из четырёх по 2 бита, длина закодированного слова составила бы 18 бит.