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

Алгоритм

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

Пример

Возьмем какое-то слово,состоящее из букв:[math]\[/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