Алгоритм Хаффмана для n ичной системы счисления — различия между версиями
(→Построение кода Хаффмана) |
м (rollbackEdits.php mass rollback) |
(не показана 1 промежуточная версия 1 участника) | |
(нет различий)
|
Текущая версия на 19:27, 4 сентября 2022
Алгоритм
Для построения
-ичного кода Хаффмана надо использовать операцию сжатия алфавита, при которой каждый раз сливаются не две, а букв исходного алфавита, имеющих наименьшие вероятности.Сжатие алфавита, при котором букв заменяются на одну, приводит к уменьшению числа букв на ; так как для построения -ичного кода, очевидно, требуется, чтобы последовательность сжатий в конце концов привела нас к алфавиту из букв (сопоставляемых сигналам кода), то необходимо, чтобы число букв первоначального алфавита было представимо в виде , . Этого, однако, всегда можно добиться, добавив, если нужно, к первоначальному алфавиту еще несколько фиктивных букв, вероятности которых считаются равными нулю. После этого построение -ичного кода Хаффмана проводится уже точно так же, как и в случае двоичного кода.Пример
Для примера возьмём слово "кириллица".Возьмем
(троичная система счисления).Алфавит будет к, и, р, л, ц, а , а набор весов . Будем действовать согласно алгоритму выше;у нас число букв первоначального алфавита равно 6.Если подставить значения и в формулу для оптимального кодирования ,то получится что не является целым.Но если увеличить число на 1 (добавлением фиктивной буквы "я" с весом 0) , то можно подобрать целое равное 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 бит.
Корректность алгоритма Хаффмана для -ичной системы счисления
Доказательство аналогично тому,что представлено в теме алгоритм Хаффмана.Только вместо двух символом с минимальными частотами надо брать символов с минимальными частотами (по алгоритму вес символа также может равняться 0).
Задача о подсчете числа бит
Имеются частоты символов,встречающихся в исходном тексте.Необходимо подсчитать суммарное число бит,необходимое для кодирования этого текста.
Возьмем
. На каждом шаге выбираем две наименьшие частоты,объединяем их сумму в одну частоту и добавляем в список вместо двух исходных.Новую частоту прибавляем к с присваиванием.Шаги заканчиваются тогда,когда в списке останется только одна частота.В-итоге,
- число бит необходимое для кодирования этого текстаСложность алгоритма
.Псевдокод алгоритма:
int//исходный массив частот всех n символов,встречающихся в тексте" = 0 do for = 1.. find( , ) //отыскиваем индексы двух минимальных элементов массива swap( [1], [min1]) swap( [2], [min2]) //теперь первые два элемента массива минимальные [2] = [1] + [2] += [2] -- delete( [1]) //убираем из массива ненужный элемент и больше его не рассматриваем while != 1 //пока не останется одна частота в массиве return
Построение кода Хаффмана
В приведенном ниже псевдокоде предполагается,что
- множество,состоящее из символов,и что каждый из символов - объект с определенной частотой .В алгоритме строится оптимальное дерево ,соответствующее оптимальному коду,причем построение идет в восходящем направлении.Процесс построения начинается с множества,состоящего из листьев,после чего последовательно выполняется операций "слияния",в результате,которых образуется конечное дерево.HUFFMAN() struct Node //Звено дерева int , char //пара ключ и значение Node *left,*right = queue <char> char [ ] , int [ ] //массив c содержит алфавит из n различных символов,массив f - соответствующий ему набор положительных целых весов. for = 1 to .insert( [ ], [ ]) for = 1 to - 1 ( , ) = .extract_min() .left = ( , ) = .extract_min() .right = = + .insert( , ) return
Алгоритм работает за для алфавита из символов.