Изменения

Для построения <tex>n</tex>-ичного кода Хаффмана надо использовать операцию сжатия алфавита, при которой каждый раз сливаются не две, а <tex>n</tex> букв исходного алфавита, имеющих наименьшие вероятности.Сжатие алфавита, при котором <tex>n</tex> букв заменяются на одну, приводит к уменьшению числа букв на <tex>n-1</tex>; так как для построения <tex>n</tex>-ичного кода, очевидно, требуется, чтобы последовательность сжатий в конце концов привела нас к алфавиту из <tex>n</tex> букв (сопоставляемых <tex>n</tex> сигналам кода), то необходимо, чтобы число <tex>m</tex> букв первоначального алфавита было представимо в виде <tex>m = n + k(n - 1)</tex> ,<tex>k \in \mathbb{Z}</tex>. Этого, однако, всегда можно добиться, добавив, если нужно, к первоначальному алфавиту еще несколько фиктивных букв, вероятности которых считаются равными нулю. После этого построение <tex>n</tex>-ичного кода Хаффмана проводbтся проводится уже точно так же, как и в случае двоичного кода.

Для примера возьмём слово ''"Кириллицакириллица"''.Возьмем <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.

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

! Узел || якр || и || мп л || ц || с а

| Вес || 4 2 || 3 || 2 || 31 || 1

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

! Узел || якр || и || мпс лца

| Вес || 4 2 || 3 || 5 4

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

! Символ || к || и || м р || л || ц || п а || ся

| Код || +- || - || +0 || 0 || 100 0+ || 101 0- || 11++

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