Изменения
Нет описания правки
== Алгоритм ==
Для построения <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 = m + k(m n - 1)</tex> ),<tex>k \in \mathbb{Z}</tex>. Этого, однако, всегда можно добиться, добавив, если нужно, к первоначальному алфавиту еще несколько фиктивных букв, вероятности которых считаются равными нулю. После этого построение <tex>n</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.
Таким образом можно записать:
{| class="wikitable"
! Узел || к || и || р || л || ц || а || я
|-
| Вес || 1 || 3 || 1 || 2 || 1 || 1 || 0
|}
По алгоритму возьмем два символа с наименьшей частотой {{---}} это ''м'' и ''п''. Сформируем из них новый узел ''мп'' весом 2 и добавим его к списку узлов:
{| class="wikitable"
! Узел || и || мп || с
|-
| Вес || 4 || 2 || 3
|}
Затем объединим в один узел узлы ''мп'' и ''c'':
{| class="wikitable"
! Узел || и || мпс
|-
| Вес || 4 || 5
|}
И, наконец, объединяем два узла ''и'' и ''мпс''. Итак, мы получили дерево Хаффмана и соответствующую ему таблицу кодов:
{| class="wikitable"
! Символ || и || м || п || с
|-
| Код || 0 || 100 || 101 || 11
|}
Таким образом, закодированное слово ''"миссисипи"'' будет выглядеть как ''"1000111101101010"''. Длина закодированного слова {{---}} 16 бит. Стоит заметить, что если бы мы использовали для кодирования каждого символа из четырёх по 2 бита, длина закодированного слова составила бы 18 бит.
== Корректность алгоритма Хаффмана для <tex>n</tex>-ичной системы счисления ==
Доказательство аналогично тому,что представлено в теме [[Алгоритм Хаффмана]].Только вместо двух символом с минимальными частотами надо брать <tex>n</tex> символов с минимальными частотами(по алгоритму частота вес символа также может равняться 0)
