Методы арифметического кодирования информации и сравнение их коэффициентов сжатия
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Пусть дан {i, j, k}-код и пусть количество единиц в унарной части (экспоненты) равно Q. Тогда число n (закодированное число) равно (1.7):
, (1.7)
где ? - мантисса записанного кода, Dec(x) - функция, переводящая x в десятичную систему счисления.
Получение {i, j, k}-start-step-stop кода по заданному числу n
Теперь наоборот, пусть задано число n. Для получения его кода необходимо найти такое минимальное положительное число Q0, чтобы выполнялось неравенство (1.8):
.(1.8)
При этом сам код будет выглядеть так (1.9):
?(Q0 ? 1) : ?(n + 2IQ0 ? S). (1.9)
Замечание
В качестве частных случаев Start-step-stop кодов могут быть получены следующие коды и они сведены в таблицу 1.14:
Таблица 1.14 - Частный случай старт-шаг-стоп кодов
{i, j, k}Диапазонk, 1, kпростой бинарный код для целых чисел0, 1, ??-код Элиасаk, k, ??-код Элиаса по основанию 2k
.12 Код Хаффмана
Код Хаффмана (Huffman code) ещё называют минимально-избыточным префиксным кодом (minimum-redundancy prefix code). Идея, лежащая в основе кода Хаффмана, достаточно проста. Вместо того чтобы кодировать все символы одинаковым числом бит (как это сделано, например, в ASCII кодировке, где на каждый символ отводится ровно по 8 бит), символы которые встречаются чаще, кодируются меньшим числом бит, чем те, которые встречаются реже. Код при этом должен быть оптимален или, другими словами, минимально-избыточен.
Первым такой алгоритм опубликовал Дэвид Хаффман в 1952 году. Алгоритм Хаффмана двухпроходный. На первом проходе строится частотный словарь и генерируются коды. На втором проходе происходит непосредственно кодирование.
Стоит отметить, что за 50 лет со дня опубликования, код Хаффмана ничуть не потерял своей актуальности и значимости. Так с уверенностью можно сказать, что мы сталкиваемся с ним, в той или иной форме (дело в том, что код Хаффмана редко используется отдельно, чаще работая в связке с другими алгоритмами), практически каждый раз, когда архивируем файлы, смотрим фотографии, фильмы, посылаем факс или слушаем музыку.
Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева. Общая схема построения дерева Хаффмана:
1.Составляется список кодируемых символов (при этом каждый символ рассматривается как одноэлементное бинарное дерево, вес которого равен весу символа).
2.Из списка выбирается 2 узла с наименьшим весом.
.Формируется новый узел и к нему присоединяется, в качестве дочерних, два узла выбранных из списка. При этом полагается, что вес сформированного узла равен сумме весов дочерних узлов.
.Сформированный узел добавляется к списку.
.Если в списке больше одного узла, то повторяется 2-5.
2. ОБОСНОВАНИЕ И ОПИСАНИЕ АЛГОРИТМОВ КОДИРОВАНИЯ
.1 Описание алгоритма, реализующего код Хаффмана
Суть алгоритма:
Во входящей последовательности для каждого символа подсчитывается частота его встречаемости в ней. Затем по полученным частотам строится бинарное дерево по восходящему принципу: листья - это самые низкие частоты; узлы, которые стоят выше листьев по иерархии - это суммарное количество частот листьев-детей; корень дерева - это сумма всех частот.
По бинарному дереву составляется бинарный код для каждого символа последовательности по принципу: совершается обход дерева с корня до необходимого символа, при проходе влево - в код записывается 0, вправо - 1.
Благодаря такому подходу символ, который встречается чаще всего, кодируется меньшим количеством битов, чем символ с меньшей частотой.
Ниже приведен пример кодирования последовательности adamand кодом Хаффмана. Итак, пошагово распишем действия:
. Следует подсчитать частоты встречаемости всех символов во входящей последовательности:
a - 3 ; d - 2 ; m - 1 ; n - 1
. Строим бинарное дерево, исходя из частот встречаемости. Полученное дерево изображено на рисунке 2.1:
Рисунок 2.1- Бинарное дерево Хаффмана
. Выписываем полученные коды:
a - 0
d - 10
m - 110
n - 111
. Итак, закодированная последовательность имеет вид: 0100110011110.
Блок-схемы, описывающие логику вышеописанного алгоритма, показаны на рисунках 2.2 - 2.5.
Рисунок 2.2 - Блок-схема алгоритма кодирования методом Хаффмана
Рисунок 2.3 - Блок-схема алгоритма построения дерева для кода Хаффмана
Рисунок 2.4 - Блок-схема алгоритма обхода дерева, формирования кодовой таблицы
Рисунок 2.5 - Блок-схема алгоритма декодирования методом Хаффмана
2.2 Описание алгоритма, реализующего код Голомба
Суть алгоритма кодирования:
Этот метод требует ввод определенного параметра М. Если значение M равно двойке в целой положительной степени, то код Голомба переходит в свой частный случай - код Райса.
Пусть есть число N, которое требуется закодировать, и фиксированное число М.
Шаги алгоритма:
. Находим частное q = N /М - деление целочисленное.
. Находим остаток от деления N /М: r = N %М.
. Закодированное число N имеет формат:
.1 Код q является просто унарным кодированием числа q, то есть представимо в виде: 111…110, где количество единиц равно самому числу q.
.2 Для нахождения кода r введем параметр b=[log2(M)], причем b округляется в сторону большего целого, и параметр с = 2b-M. Далее, если число 0 ? r < c, то код r - это просто бинарный код числа r, помещенный в количество бит, равное b-1;
если же r ? c, то ко?/p>