Просмотр исходного текста страницы Алгоритм Хаффмана для n ичной системы счисления

== Пример ==
Для примера возьмём слово ''"кириллица"''.Возьмем <tex>n=3</tex> (троичная система счисления).Алфавит будет <tex>A= \{</tex> ''к, и, р, л, ц, а'' <tex>\} </tex>, а набор весов <tex>W=\{1, 3, 1, 2, 1, 1\}</tex>.
Будем действовать согласно алгоритму выше;у нас число букв первоначального алфавита <tex>m</tex> равно 6.Если подставить значения <tex>n</tex> и <tex>m</tex> в формулу для оптимального кодирования <tex>m = n + k(n - 1)</tex> ,то получится что <tex>k</tex> не является целым.Но если увеличить число <tex>m</tex> на 1 (добавлением фиктивной буквы "я" с весом 0) , то можно подобрать целое <tex>k</tex> равное 2.
Таким образом можно записать:
{| class="wikitable"
! Узел || к || и || р || л || ц || а || я
|-
| Вес || 1 || 3 || 1 || 2 || 1 || 1 || 0
|}

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

{| class="wikitable"
! Узел || якр || и || л || ц || а 
|-
| Вес || 2 || 3 || 2 || 1 || 1
|}

Затем объединим в один узел узлы ''л'',''ц'',''а'':

{| class="wikitable"
! Узел || якр || и || лца 
|-
| Вес || 2 || 3 || 4 
|}

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

{| class="wikitable"
! Символ || к || и || р || л || ц || а || я
|-
| Код || +- || - || +0 || 00 || 0+ || 0- || ++
|}

Таким образом, закодированное слово ''"кириллица"'' будет выглядеть как ''"+--+0-0000-0+0-"''. Длина закодированного слова {{---}} 15 бит. Стоит заметить, что если бы мы использовали для кодирования каждого символа из шести по 2 бита, длина закодированного слова составила бы 18 бит.