Арифметическое кодирование
Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов. Арифметическое кодирование является оптимальным, достигая теоретической границы степени сжатия . Арифметическое кодирование – блочное и выходной код является уникальным для каждого из возможных входных сообщений; его нельзя разбить на коды отдельных символов, в отличие от кодов Хаффмана , которые являются неблочными, т.е. каждой букве входного алфавита ставится в соответствие определенный выходной код.
Текст, сжатый арифметическим кодером, рассматривается как некоторая двоичная дробь из интервала ), а интервал для /-го кодируемого символа потока как ; Ь[с]), включающий 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) ;
Результат |
|||||
Нормализация |
|||||
Нормализация |
|||||
Нормализация |
Как уже было отмечено, чаще всего при нормализации не происходит переноса. Исходя из этого, Дмитрий Субботин 1 предложил отказаться от переноса вовсе. Оказалось, что потери в сжатии совсем незначительны, порядка нескольких байтов. Впрочем, выигрыш по скорости тоже оказался не очень заметен. Главное достоинство такого подхода - в простоте и компактности кода. Вот как выглядит функция нормализации для 32-разрядной арифметики:
♦define CODEBITS 24
♦define TOP (l«CODEBITS)
♦define BOTTOM (TOP»8)
♦define BIGBYTE (0xFF«(CODEBITS-8))
void encode_normalize(void) { while(range < BOTTOM) {
if(low & BIGBYTE == BIGBYTE &&
range + (low & BOTTOM-1) >= BOTTOM) range = BOTTOM - (low & BOTTOM-1); output_byte (low»24) ; range<<=8; low«=8; })
Можно заметить, что избежать переноса нам позволяет своевременное принудительное уменьшение значения размера интервала. Оно происходит
тогда, когда второй по старшинству байт low принимает значение OxFF, а при добавлении к low значения размера интервала range возникает перенос. Так выглядит оптимизированная процедура нормализации:
void encode_normalize(void) { while((low " low+range)
void decode_normalize(void) { while((low л low+range)
Упражнение. Применить интервальное кодирование без переноса для строки "ков.корова".