Алгоритм Хаффмана для n ичной системы счисления — различия между версиями
(→Корректность алгоритма Хаффмана для n-ичной системы счисления) |
(→Пример) |
||
Строка 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" | ||
Строка 37: | Строка 37: | ||
Таким образом, закодированное слово ''"кириллица"'' будет выглядеть как ''"+--+0-0000-0+0-"''. Длина закодированного слова {{---}} 15 бит. Стоит заметить, что если бы мы использовали для кодирования каждого символа из шести по 2 бита, длина закодированного слова составила бы 18 бит. | Таким образом, закодированное слово ''"кириллица"'' будет выглядеть как ''"+--+0-0000-0+0-"''. Длина закодированного слова {{---}} 15 бит. Стоит заметить, что если бы мы использовали для кодирования каждого символа из шести по 2 бита, длина закодированного слова составила бы 18 бит. | ||
− | |||
== Корректность алгоритма Хаффмана для <tex>n</tex>-ичной системы счисления == | == Корректность алгоритма Хаффмана для <tex>n</tex>-ичной системы счисления == |
Версия 18:28, 17 декабря 2013
Содержание
Алгоритм
Для построения
-ичного кода Хаффмана надо использовать операцию сжатия алфавита, при которой каждый раз сливаются не две, а букв исходного алфавита, имеющих наименьшие вероятности.Сжатие алфавита, при котором букв заменяются на одну, приводит к уменьшению числа букв на ; так как для построения -ичного кода, очевидно, требуется, чтобы последовательность сжатий в конце концов привела нас к алфавиту из букв (сопоставляемых сигналам кода), то необходимо, чтобы число букв первоначального алфавита было представимо в виде , . Этого, однако, всегда можно добиться, добавив, если нужно, к первоначальному алфавиту еще несколько фиктивных букв, вероятности которых считаются равными нулю. После этого построение -ичного кода Хаффмана проводится уже точно так же, как и в случае двоичного кода.Пример
Для примера возьмём слово "кириллица".Возьмем
(троичная система счисления).Алфавит будет к, и, р, л, ц, а , а набор весов . Будем действовать согласно алгоритму выше;у нас число букв первоначального алфавита равно 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 a[1..n] //исходный массив частот всех n символов,встречающихся в тексте" sum=0; do sort(a) //сортируем массив по возрастанию a[2] = a[1]+a[2] sum =+ a[2] n-- delete(a[1]) //убираем из массива ненужный элемент и больше его не рассматриваем while n!=1 //пока не останется одна частота в массиве return sum