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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример)
м (rollbackEdits.php mass rollback)
 
(не показано 38 промежуточных версий 5 участников)
Строка 4: Строка 4:
 
== Пример ==
 
== Пример ==
 
Для примера возьмём слово ''"кириллица"''.Возьмем <tex>n=3</tex> (троичная система счисления).Алфавит будет <tex>A= \{</tex> ''к, и, р, л, ц, а'' <tex>\} </tex>, а набор весов <tex>W=\{1, 3, 1, 2, 1, 1\}</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.
+
Будем действовать согласно алгоритму выше;у нас число букв первоначального алфавита <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"
 
{| class="wikitable"
Строка 39: Строка 39:
  
 
== Корректность алгоритма Хаффмана для <tex>n</tex>-ичной системы счисления ==
 
== Корректность алгоритма Хаффмана для <tex>n</tex>-ичной системы счисления ==
Доказательство аналогично тому,что представлено в теме [[алгоритм Хаффмана]].Только вместо двух символом с минимальными частотами надо брать <tex>n</tex> символов с минимальными частотами(по алгоритму вес символа также может равняться 0)
+
Доказательство аналогично тому,что представлено в теме [[алгоритм Хаффмана]].Только вместо двух символом с минимальными частотами надо брать <tex>n</tex> символов с минимальными частотами (по алгоритму вес символа также может равняться 0).
  
 
==Задача о подсчете числа бит==
 
==Задача о подсчете числа бит==
 
Имеются частоты символов,встречающихся в исходном тексте.Необходимо подсчитать суммарное число бит,необходимое для кодирования этого текста.
 
Имеются частоты символов,встречающихся в исходном тексте.Необходимо подсчитать суммарное число бит,необходимое для кодирования этого текста.
  
Возьмем <tex>sum=0</tex>.На каждом шаге выбираем две наименьшие частоты,объединяем их сумму в одну частоту и добавляем в список вместо двух исходных.Новую частоту прибавляем к <tex>sum</tex> с присваиванием.Шаги заканчиваются тогда,когда в списке останется только одна частота.
+
Возьмем <math>\mathrm{sum = 0}</math>. На каждом шаге выбираем две наименьшие частоты,объединяем их сумму в одну частоту и добавляем в список вместо двух исходных.Новую частоту прибавляем к <math>\mathrm{sum}</math> с присваиванием.Шаги заканчиваются тогда,когда в списке останется только одна частота.
  
В-итоге,<tex>sum</tex>-число бит необходимое для кодирования этого текста
+
В-итоге, <math>\mathrm{sum}</math> - число бит необходимое для кодирования этого текста
 +
 
 +
Сложность алгоритма <tex>O(n^2)</tex>.
  
 
Псевдокод алгоритма:
 
Псевдокод алгоритма:
  
       '''int''' a[1..n]      ''//исходный массив частот всех n символов,встречающихся в тексте"
+
       '''int''' <math>\mathrm{a[1..n]}</math>     ''//исходный массив частот всех n символов,встречающихся в тексте"
      sum=0;
+
      <math>\mathrm{sum}</math> = 0
    do
+
      do
      sort(a)               ''//сортируем массив по возрастанию''
+
        for <math>\mathrm{i}</math> = 1..<math>\mathrm{n}</math>
      a[2] = a[1]+a[2]
+
          find(<math>\mathrm{min1}</math>,<math>\mathrm{min2}</math>)          ''//отыскиваем индексы двух минимальных элементов массива
      sum =+ a[2]
+
        swap(<math>\mathrm{a}</math>[1],<math>\mathrm{a}</math>[min1])       
      n--
+
        swap(<math>\mathrm{a}</math>[2],<math>\mathrm{a}</math>[min2])         ''//теперь первые два элемента массива минимальные''
      delete(a[1])          ''//убираем из массива ненужный элемент и больше его не рассматриваем''  
+
        <math>\mathrm{a}</math>[2] = <math>\mathrm{a}</math>[1] + <math>\mathrm{a}</math>[2]
    while n!=1              ''//пока не останется одна частота в массиве''
+
        <math>\mathrm{sum}</math> += <math>\mathrm{a}</math>[2]
      '''return''' sum
+
        <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> символов.

Текущая версия на 19:27, 4 сентября 2022

Алгоритм

Для построения [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]\mathrm{sum = 0}[/math]. На каждом шаге выбираем две наименьшие частоты,объединяем их сумму в одну частоту и добавляем в список вместо двух исходных.Новую частоту прибавляем к [math]\mathrm{sum}[/math] с присваиванием.Шаги заканчиваются тогда,когда в списке останется только одна частота.

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

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

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

     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]

Построение кода Хаффмана

€В приведенном ниже псевдокоде предполагается,что [math]C[/math] - множество,состоящее из [math]n[/math] символов,и что каждый из символов [math]c \in C[/math] - объект с определенной частотой [math]f(c)[/math].В алгоритме строится оптимальное дерево [math]T[/math],соответствующее оптимальному коду,причем построение идет в восходящем направлении.Процесс построения начинается с множества,состоящего из [math]|C|[/math] листьев,после чего последовательно выполняется [math]|C|-1[/math] операций "слияния",в результате,которых образуется конечное дерево.

  HUFFMAN([math]C[/math])
  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]            


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