Изменения

Для построения <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=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). ==Задача о подсчете числа бит==Имеются частоты символов,встречающихся в исходном тексте.Необходимо подсчитать суммарное число бит,необходимое для кодирования этого текста. Возьмем <math>\mathrm{sum = 0}</math>. На каждом шаге выбираем две наименьшие частоты,объединяем их сумму в одну частоту и добавляем в список вместо двух исходных.Новую частоту прибавляем к <math>\mathrm{sum}</math> с присваиванием.Шаги заканчиваются тогда,когда в списке останется только одна частота. В-итоге, <math>\mathrm{sum}</math> - число бит необходимое для кодирования этого текста Сложность алгоритма <tex>O(среди n^2)</tex>. Псевдокод алгоритма:  '''int''' <math>\mathrm{a[1..n]}</math> ''//исходный массив частот всех n символов,встречающихся в тексте" <math>\mathrm{sum}</math> = 0 do for <math>\mathrm{i}</math> = 1..<math>\mathrm{n}</math> find(<math>\mathrm{min1}</math>,<math>\mathrm{min2}</math>) ''//отыскиваем индексы двух минимальных элементов массива swap(<math>\mathrm{a}</math>[1],<math>\mathrm{a}</math>[min1]) swap(<math>\mathrm{a}</math>[2],<math>\mathrm{a}</math>[min2]) ''//теперь первые два элемента массива минимальные'' <math>\mathrm{a}</math>[2] = <math>\mathrm{a}</math>[1] + <math>\mathrm{a}</math>[2] <math>\mathrm{sum}</math> += <math>\mathrm{a}</math>[2] <math>\mathrm{n}</math>-- delete(<math>\mathrm{a}</math>[1]) ''//убираем из массива ненужный элемент и больше его не рассматриваем'' while <math>\mathrm{n}</math> != 1 ''//пока не останется одна частота в массиве'' '''return''' <math>\mathrm{sum}</math> ==Построение кода Хаффмана==€В приведенном ниже псевдокоде предполагается,что <tex>C</tex> - множество,состоящее из <tex>n</tex> символов,и что каждый из символов <tex>c \in C</tex>-ичных кодовобъект с определенной частотой <tex>f(c)</tex>.В алгоритме строится оптимальное дерево <tex>T</tex>,соответствующее оптимальному коду,причем построение идет в восходящем направлении.Процесс построения начинается с множества,состоящего из <tex>|C|</tex> листьев,после чего последовательно выполняется <tex>|C|-1</tex> операций "слияния",в результате,которых образуется конечное дерево. HUFFMAN(<tex>C</tex>) проводятся уже точно так же struct Node //Звено дерева int <math>\mathrm{key}</math>, как char <math>\mathrm{value}</math> //пара ключ и случае двоичного кодазначение Node *left,*right <math>\mathrm{n}</math> = <math>\mathrm{|C|}</math> queue <char> <math>\mathrm{Q}</math> char <math>\mathrm{c}</math>[<math>\mathrm{n}</math>] , int <math>\mathrm{f}</math>[<math>\mathrm{n}</math>] //массив c содержит алфавит из n различных символов,массив f - соответствующий ему набор положительных целых весов. '''for''' <math>\mathrm{i}</math> = 1 '''to''' <math>\mathrm{n}</math> <math>\mathrm{Q}</math>.insert(<math>\mathrm{f}</math>[<math>\mathrm{i}</math>],<math>\mathrm{c}</math>[<math>\mathrm{i}</math>]) '''for''' <math>\mathrm{i}</math> = 1 '''to''' <math>\mathrm{n}</math> - 1 (<math>\mathrm{min1}</math>,<math>\mathrm{x}</math>) = <math>\mathrm{Q}</math>.extract_min() <math>\mathrm{z}</math>.left = <math>\mathrm{x}</math> (<math>\mathrm{min2}</math>,<math>\mathrm{y}</math>) = <math>\mathrm{Q}</math>.extract_min() <math>\mathrm{z}</math>.right = <math>\mathrm{y}</math> <math>\mathrm{sum}</math> = <math>\mathrm{min1}</math> + <math>\mathrm{min2}</math> <math>\mathrm{Q}</math>.insert(<math>\mathrm{sum}</math>,<math>\mathrm{z}</math>) '''return''' <math>\mathrm{z}</math>   Алгоритм работает за <tex> {O(n\log{n}}) </tex> для алфавита из <math>\mathrm{n}</math> символов.