Арифметическое кодирование формулы. Обзор алгоритмов сжатия без потерь

Арифметическое кодирование

Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов. Арифметическое кодирование является оптимальным, достигая теоретической границы степени сжатия . Арифметическое кодирование – блочное и выходной код является уникальным для каждого из возможных входных сообщений; его нельзя разбить на коды отдельных символов, в отличие от кодов Хаффмана , которые являются неблочными, т.е. каждой букве входного алфавита ставится в соответствие определенный выходной код.

Текст, сжатый арифметическим кодером, рассматривается как некоторая двоичная дробь из интервала ), а интервал для /-го кодируемого символа потока как ; Ь[с]), включающий 0.341. Перебором всех возможных символов по приведенной выше таблице находим, что только интервал -(fti-j - li-i); hi = li.! + b ■ {hi.! - li.i); if {{l t <= value) && (value < hi)) break; }; DataFile.WriteSymbol(c^) ;

где value - прочитанное из потока число (дробь), а с - записываемые в вы­ходной поток распаковываемые символы. При использовании алфавита из 256 символов Cj внутренний цикл выполняется достаточно долго, однако его можно ускорить. Заметим, что поскольку Ь[с^ {\=a; II delitel=10

First_qtr - (h 0 +l)/4; // - 16384

Half = First_qtr*2; // - 32768

Third_qtr - First_qtr*3;// = 49152

bits_to_follow =0; // Сколько битов сбрасывать

while (not DataFile.EOFO) {

с = DataFile.ReadSymbol(); // Читаем символ
j = IndexForSymbol(с); i++; // Находим его индекс
li = li.j + b*{h i . 1 - li-x + l)/delitel;
hi = li.! + b ;
First_qtr = (h 0 +l)/4; // = 16384

Half = First_qtr*2; // = 32768

Third_qtr = First_qtr*3; // = 49152

value=CompressedFile.Readl6Bit();

for(i=l; i< CompressedFile.DataLengthO; i++){

freq=((value-2 i . 1 +l)*delitel-l)/(h i . I - 1 ± . х + 1) ;

for(j=l; b<=freq; j++); // Поиск символа

li = 1ы + blj-l]*{bi.! - li- u + l)/delitel;

hi = Im + b*{h i . 1 - li.! + l)/delitel - 1;

for(;;) { // Обрабатываем варианты

if (hi < Half) // переполнения

; // Ничего else ifdi >= Half) {

2i-= Half; hi-= Half; value-= Half; }

else if (di >= First_qtr)&& (hi < Third_qtr)) { 2i-= First_qtr; hi-= First_qtr; value-= First_qtr,-} else break; 2i+=2 i; hi+= hi+1;

value+=value+CompressedFile.ReadBit(); } DataFile.WriteSymbol(c););

Упражнение. Предложите примеры последовательностей, сжимаемых алго­ритмом с максимальным и минимальным коэффициентом.

Как видно, с неточностями арифметики мы боремся, выполняя отдель­ные операции над /, и А, синхронно в компрессоре и декомпрессоре.

Незначительные потери точности (доли процента при достаточно боль­шом файле) и, соответственно, уменьшение степени сжатия по сравнению с идеальным алгоритмом происходят во время операции деления, при округ­лении относительных частот до целого, при записи последних битов в файл. Алгоритм можно ускорить, если представлять относительные частоты так, чтобы делитель был степенью двойки (т. е. заменить деление операцией по­битового сдвига).

Для того чтобы оценить степень сжатия арифметическим алгоритмом конкретной строки, нужно найти минимальное число N, такое, чтобы длина рабочего интервала при сжатии последнего символа цепочки была бы меньше 1/2^.. Этот критерий означает, что внутри нашего интервала заведо­мо найдется хотя бы одно число, в двоичном представлении которого после N-ro знака будут только 0. Длину же интервала, дорчитать просто, поскольку она равна произведению вероятностей всех символов.

Рассмотрим приводившийся ранее пример строки из двух символов л и Ъ с вероятностями 253/256 и 3/256. Длина последнего рабочего интервала для цепочки из 256 символов а и Ь с указанными вероятностями равн. Легко подсчитать, что искомое N=24 (1/2 24 = 5.96-10" 8), поскольку 23 дает слишком большой интервал (в 2 раза шире), а 25 не является минимальным числом, удовлетворяющим критерию. Выше было показано, что алгоритм Хаффмана кодирует данную цепочку в 256 бит. То есть для рассмотренного примера арифметический алгоритм дает десятикратное преимущество, пе­ред алгоритмом Хаффмана и требует менее 0.1 бита на символ.

Упражнение. Подсчитайте оценку степени сжатия для строки "КОВ.КОРОБА".

Следует сказать пару слов об адаптивном алгоритме арифметического сжатия. Его идея заключается в том, чтобы перестраивать таблицу вероят­ностей b[f] по ходу упаковки и распаковки непосредственно при получении очередного символа. Такой алгоритм не требует сохранения значений веро­ятностей символов в выходной файл и, как правило, дает большую степень сжатия. Так, например, файл вида а 1000 £ 1000 с 1000 б/ 1000 (где степень означает число повторов данного символа) адаптивный алгоритм сможет сжать, эф­фективнее, чем потратив 2 бита на символ. Приведенный выше алгоритм достаточно просто превращается в адаптивный. Ранее мы сохраняли табли­цу диапазонов в файл, а теперь мы считаем прямо по ходу работы компрес­сора и декомпрессора, пересчитываем относительные частоты, корректируя в соответствии с ними таблицу диапазонов. Важно, чтобы изменения в таб­лице происходили в компрессоре и декомпрессоре синхронно, т. е., напри­мер, после кодирования цепочки длины 100 таблица диапазонов должна быть точно такой же, как и после декодирования цепочки длины 100. Это условие легко выполнить, если изменять таблицу после кодирования и де­кодирования очередного символа. Подробнее об адаптивных алгоритмах смотрите в гл. 4.

Характеристики арифметического алгоритма:

Лучшая и худшая степень сжатия: лучшая > 8 (возможно кодирование менее бита на символ), худшая - 1.

Плюсы алгоритма: обеспечивает лучшую степень сжатия, чем алго-I ритм Хаффмана (на типичных данных на 1-10%).

Характерные особенности: так же как кодирование по Хаффману, не увеличивает размера исходных данных в худшем случае.

Интервальное кодирование

В отличие от классического алгоритма, интервальное кодирование пред­полагает, что мы имеем дело с целыми дискретными величинами, которые могут принимать ограниченное число значений. Как уже было отмечено, начальный интервал в целочисленной арифметике записывается в виде [ОД) или , где N- число возможных значений переменной, используемой для хранения границ интервала.

Чтобы наиболее эффективно сжать данные, мы должны закодировать каждый символ s посредством -log 2 (Ј) бит, где f, - частота символа s. Ко­нечно, на практике такая точность недостижима, но мы можем для каждого символа s отвести в интервале диапазон значений , Prev_freq[c], 10) ;