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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Построение кода Хаффмана)
(Построение кода Хаффмана)
Строка 69: Строка 69:
 
Приведем жадный алгоритм Хаффмана, строящий оптимальный префиксный код. При этом предполагаем, что для любого символа <tex>c \in C</tex> задана его частота <math>\mathrm{f[c]}</math>. Также в алгоритме используется очередь с приоритетами <math>\mathrm{Q}</math>, которая позволяет найти два объекта с наименьшими частотами для их слияния.
 
Приведем жадный алгоритм Хаффмана, строящий оптимальный префиксный код. При этом предполагаем, что для любого символа <tex>c \in C</tex> задана его частота <math>\mathrm{f[c]}</math>. Также в алгоритме используется очередь с приоритетами <math>\mathrm{Q}</math>, которая позволяет найти два объекта с наименьшими частотами для их слияния.
  
n ← |C|
+
n ← |C|
Q ← C
+
Q ← C
for i ← 1 to n - 1
+
for i ← 1 to n - 1
do z ← Allocate-Node()  
+
do z ← Allocate-Node()  
x ← left[z] ← Extract-Min(Q)
+
x ← left[z] ← Extract-Min(Q)
y ← right[z] ← Extract-Min(Q)
+
y ← right[z] ← Extract-Min(Q)
f[z] ← f[x] + f[y]
+
f[z] ← f[x] + f[y]
Insert(Q, z)
+
Insert(Q, z)
return Extract-Min(Q)
+
return Extract-Min(Q)
  
 
Алгоритм строит оптимальное дерево префиксных кодов. Для этого в цикле выполняется выборка из очереди двух вершин <math>\mathrm{x}</math> и <math>\mathrm{y}</math> с наменьшими частотами (<math>\mathrm{f[x]}</math> и <math>\mathrm{f[y]}</math> соответственно), которые заменяются на одну вершину <math>\mathrm{z}</math> с частотой <math>\mathrm{f[x]}</math> <math>\mathrm{+}</math> <math>\mathrm{f[y]}</math> и детьми <math>\mathrm{x}</math> и <math>\mathrm{y}</math>.
 
Алгоритм строит оптимальное дерево префиксных кодов. Для этого в цикле выполняется выборка из очереди двух вершин <math>\mathrm{x}</math> и <math>\mathrm{y}</math> с наменьшими частотами (<math>\mathrm{f[x]}</math> и <math>\mathrm{f[y]}</math> соответственно), которые заменяются на одну вершину <math>\mathrm{z}</math> с частотой <math>\mathrm{f[x]}</math> <math>\mathrm{+}</math> <math>\mathrm{f[y]}</math> и детьми <math>\mathrm{x}</math> и <math>\mathrm{y}</math>.
  
 
Алгоритм работает за <tex> {O(n\log{n}}) </tex> для алфавита из <math>\mathrm{n}</math> символов.
 
Алгоритм работает за <tex> {O(n\log{n}}) </tex> для алфавита из <math>\mathrm{n}</math> символов.

Версия 15:12, 3 января 2014

Алгоритм

Для построения [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 \in C[/math] задана его частота [math]\mathrm{f[c]}[/math]. Также в алгоритме используется очередь с приоритетами [math]\mathrm{Q}[/math], которая позволяет найти два объекта с наименьшими частотами для их слияния.

n ← |C|
Q ← C
for i ← 1 to n - 1
do z ← Allocate-Node() 
x ← left[z] ← Extract-Min(Q)
y ← right[z] ← Extract-Min(Q)
f[z] ← f[x] + f[y]
Insert(Q, z)
return Extract-Min(Q)

Алгоритм строит оптимальное дерево префиксных кодов. Для этого в цикле выполняется выборка из очереди двух вершин [math]\mathrm{x}[/math] и [math]\mathrm{y}[/math] с наменьшими частотами ([math]\mathrm{f[x]}[/math] и [math]\mathrm{f[y]}[/math] соответственно), которые заменяются на одну вершину [math]\mathrm{z}[/math] с частотой [math]\mathrm{f[x]}[/math] [math]\mathrm{+}[/math] [math]\mathrm{f[y]}[/math] и детьми [math]\mathrm{x}[/math] и [math]\mathrm{y}[/math].

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