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

== Алгоритм ==
Для построения <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>-ичного кода Хаффмана проводится уже точно так же, как и в случае двоичного кода.

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

== Корректность алгоритма Хаффмана для <tex>n</tex>-ичной системы счисления ==
Доказательство аналогично тому,что представлено в теме [[алгоритм Хаффмана]].Только вместо двух символом с минимальными частотами надо брать <tex>n</tex> символов с минимальными частотами (по алгоритму вес символа также может равняться 0).

==Задача о подсчете числа бит==
Имеются частоты символов,встречающихся в исходном тексте.Необходимо подсчитать суммарное число бит,необходимое для кодирования этого текста.

Возьмем <tex>sum=0</tex>.На каждом шаге выбираем две наименьшие частоты,объединяем их сумму в одну частоту и добавляем в список вместо двух исходных.Новую частоту прибавляем к <tex>sum</tex> с присваиванием.Шаги заканчиваются тогда,когда в списке останется только одна частота.

В-итоге,<tex>sum</tex>-число бит необходимое для кодирования этого текста

Псевдокод алгоритма:

      '''int''' a[1..n]      ''//исходный массив частот всех n символов,встречающихся в тексте"
       <math>\mathrm{sum}</math> = 0
    do
       sort(a)               ''//сортируем массив по возрастанию''
       a[2] = a[1]+a[2]
       sum =+ a[2]
       <math>\mathrm{n}</math>--
       delete(a[1])          ''//убираем из массива ненужный элемент и больше его не рассматриваем'' 
    while <math>\mathrm{n}</math>!=1               ''//пока не останется одна частота в массиве''
       '''return''' <math>\mathrm{sum}</math>