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

Алгоритм

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

Пример

Для примера возьмём слово "кириллица".Возьмем $n=3$ (троичная система счисления).Алфавит будет $A= \{$ к, и, р, л, ц, а $\}$, а набор весов $W=\{1, 3, 1, 2, 1, 1\}$. Будем действовать согласно алгоритму выше;у нас число букв первоначального алфавита $m$ равно 6.Если подставить значения $n$ и $m$ в формулу для оптимального кодирования $m = n + k(n - 1)$ ,то получится что $k$ не является целым.Но если увеличить число $m$ на 1 (добавлением фиктивной буквы "я" с весом 0) , то можно подобрать целое $k$ равное 2. Таким образом можно записать:

Узел	к	и	р	л	ц	а	я
Вес	1	3	1	2	1	1	0

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

Узел	якр	и	л	ц	а
Вес	2	3	2	1	1

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

Узел	якр	и	лца
Вес	2	3	4

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

Символ	к	и	р	л	ц	а	я
Код	+-	-	+0	00	0+	0-	++

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

Корректность алгоритма Хаффмана для $n$-ичной системы счисления

Доказательство аналогично тому,что представлено в теме алгоритм Хаффмана.Только вместо двух символом с минимальными частотами надо брать $n$ символов с минимальными частотами (по алгоритму вес символа также может равняться 0).

Задача о подсчете числа бит

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

Возьмем $\mathrm{sum = 0}$. На каждом шаге выбираем две наименьшие частоты,объединяем их сумму в одну частоту и добавляем в список вместо двух исходных.Новую частоту прибавляем к $\mathrm{sum}$ с присваиванием.Шаги заканчиваются тогда,когда в списке останется только одна частота.

В-итоге, $\mathrm{sum}$ - число бит необходимое для кодирования этого текста

Сложность алгоритма $O(n^2)$.

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

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