Алгоритм Хаффмана для 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]m = n + k(n - 1)[/math] ,[math]k \in \mathbb{Z}[/math]. Этого, однако, всегда можно добиться, добавив, если нужно, к первоначальному алфавиту еще несколько фиктивных букв, вероятности которых считаются равными нулю. После этого построение [math]n[/math]-ичного кода Хаффмана проводится уже точно так же, как и в случае двоичного кода.

Пример

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

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

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

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

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

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

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

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

int DamerauLevenshteinDistance(char S[1..M], char T[1..N])
   int d[0..M, 0..N]
   int i, j, cost
     
   // База динамики
   for i from 0 to M
      d[i, 0] = i
   for j from 1 to N
      d[0, j] = j
    
   for i from 1 to M
      for j from 1 to N           
         // Стоимость замены
         if S[i] == T[j] then replaceCost = 0
            else replaceCost = 1
          
         d[i, j] = minimum(
                              d[i-1, j  ] + deleteCost,           // удаление
                              d[i  , j-1] + insertCost,           // вставка
                              d[i-1, j-1] + replaceCost           // замена
                          )
          if(i > 1 and j > 1 
                   and S[i] == T[j-1] 
                   and S[i-1] == T[j]) then
             d[i, j] = minimum(
                                  d[i, j],
                                  d[i-2, j-2] + transposeCost // транспозиция
                              )
    
   return d[M, N]