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