Просмотр исходного текста страницы Алгоритм Хаффмана для 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).

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

Возьмем <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> операций "слияния",в результате,которых образуется конечное дерево.Для идентификации двух наименее часто встречающихся объектов,подлежащих слиянию,используется очередь с приоритетами <tex>Q</tex>,ключами в которой являются частоты <tex>f</tex>.В результате слияния двух объектов образуется новый объект,частота появления которого является суммой частот объединенных объектов:
 HUFFMAN(<tex>C</tex>)
 1  queue <char> <math>\mathrm{Q}</math>  
 2  <math>\mathrm{n}</math> = <math>\mathrm{|C|}</math>
 3  <math>\mathrm{Q}</math> = <math>\mathrm{C}</math>
 4  '''for''' <math>\mathrm{i}</math> = 1 '''to''' <math>\mathrm{n}</math> - 1     
 5        <math>\mathrm{x}</math> = <math>\mathrm{Q}</math>.extract_min()               //extract_min - изъятие из множества наименьшего элемента
 6        <math>\mathrm{z}</math>.left = <math>\mathrm{x}</math>
 7        <math>\mathrm{y}</math> = <math>\mathrm{Q}</math>.extract_min()
 8        <math>\mathrm{z}</math>.right = <math>\mathrm{y}</math>
 9        <math>\mathrm{f}</math>[<math>\mathrm{z}</math>] = <math>\mathrm{f}</math>[<math>\mathrm{x}</math>] + <math>\mathrm{f}</math>[<math>\mathrm{y}</math>]
 10       Insert(<math>\mathrm{Q}</math>, <math>\mathrm{z}</math>)
 11 '''return'''  <math>\mathrm{z}</math>                                                                            //Возврат корня дерева

Цикл '''for''' в строках '''4 - 10''' поочередно извлекает по два узла,<tex>x</tex> и <tex>y</tex>,которые характеризуются в очереди с наименьшими частотами,и заменяет их в очереди с новым узлом <tex>z</tex>,представляющим объединение упомянутых выше элементов.Частота появления <tex>z</tex> вычисляется в строке '''9''' как сумма частот <tex>x</tex> и <tex>y</tex>.Узел <tex>x</tex> является левым дочерним узлом <tex>z</tex>, а  <tex>y</tex> - его правым дочерним узлом.(Этот порядок является произвольным;перестановка левого и правого дочерних узлов приводит к созданию другого кода с той же стоимостью.) После <tex>n-1</tex> объединений в очереди остается один узел - корень дерева кодов,который возвращается в строке '''11'''.

Алгоритм работает за <tex> {O(n\log{n}}) </tex> для алфавита из <math>\mathrm{n}</math> символов.