При ответе на данный вопрос необходимо объяснить понятие «арифметическое кодирование», сравнить его с другими известными вам способами кодирования и рассказать об алгоритме построения арифметического кода некоторого сообщения.
Арифметическое кодирование - один из алгоритмов энтропийного сжатия. Алгоритм арифметического кодирования обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ требуется почти H бит, где H - информационная энтропия источника.
Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов и является наиболее оптимальным, т.к. достигается теоретическая граница степени сжатия.
Предполагаемая требуемая последовательность символов , при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала ), а интервал для /-го кодируемого символа потока как ; Ь[с]), включающий 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)
Упражнение. Применить интервальное кодирование без переноса для строки "ков.корова".
2.3 Арифметическое кодирование
Алгоритмы Шеннона-Фено и Хаффмена в лучшем случае не могут кодировать каждый символ сообщения менее чем 1 битом информации. Предположим, в сообщении, состоящем из 0 и 1, единицы встречаются 10 раз чаще. Энтропия такого сообщения HX ≈0,469 (бит /сим ). В таком случае желательно иметь схему кодирования, позволяющую кодировать символы сообщения менее чем 1 битом информации. Одним из лучших алгоритмов такого кодирования информации является арифметическое кодирование.
По исходному распределению вероятностей д.с.в. строится таблица, состоящая из пересекающихся в граничных точках отрезков для каждого из значений д.с.в. Объединение этих отрезков должно образовывать интервал , а их длины пропорциональны вероятностям кодируемых значений.
Алгоритм кодирования заключается в построении отрезка, однозначно определяющего конкретную последовательность символов сообщения. По мере поступления входных символов отрезок сообщения сужается. Отрезки строятся следующим образом. Если имеется отрезок сообщения длиной n -1 , то для построения отрезка сообщения длиной n символов, предыдущий интервал разбивается на столько частей, сколько значений включает алфавит источника. Начало и конец каждого нового интервала сообщения определяется путем прибавления к началу предыдущего интервала произведения его ширины на значения границ отрезка, соответствующего текущему новому символу (по исходной таблице вероятностей символов и назначенных им интервалов) . Затем из полученных отрезков выбирается тот, который соответствует конкретной последовательности символов сообщения длиной n .
Для построенного отрезка сообщения находится число, принадлежащее этому отрезку, обычно, это целое число, делённому на минимально возможную степень 2. Это вещественное число и будет кодом для рассматриваемой последовательности . Все возможные коды – числа строго больше 0 и меньше 1, поэтому лидирующий 0 и десятичная точка не учитываются.
По мере кодирования исходного текста его интервал сужается, соответственно количество разрядов, служащих для его представления, возрастает. Очередные символы входного текста сокращают ширину отрезка в зависимости от их вероятностей. Более вероятные символы сужают интервал в меньшей степени, чем менее вероятные, и, следовательно, добавляют меньшее количество разрядов к результату.
Принципиальное отличие арифметического кодирования от методов сжатия Шеннона-Фено и Хаффмена в его непрерывности, т.е. в отсутствии необходимости блокирования сообщения. Эффективность арифметического кодирования растёт с ростом длины сжимаемого сообщения, однако требует больших вычислительных ресурсов.
Поясним идею арифметического кодирования на конкретных примерах.
Пример 1 Закодируем текстовую строку « МАТЕМАТИКА » по алгоритму арифметического кодирования.
Алфавит кодируемого сообщения содержит следующие символы: {М , А , Т , Е , И , К }.
Определим частоту каждого из символов в сообщении и назначим каждому из них отрезок, длина которого пропорциональна вероятности соответствующего символа (табл. 2.7 ).
Символы в таблице символов и интервалов можно располагать в любом порядке: по мере их появления в тексте, в алфавитном или по возрастанию вероятностей – это не принципиально. Результат кодирования может быть разным, но эффект будет одинаковым.
Таблица 2.7
Символ |
Вероятность |
Интервал |
||||||
М |
0,2 |
11 |
(8/9; 1 ] |
111 |
(26/27; 1 ] " 31/32 ® |
|||
110 |
(8/9; 26/27 ] " 15/16 ® |
|||||||
10 |
(2/3; 8/9 ] |
101 |
(22/27; 8/9 ] " 7/8 ® |
|||||
100 |
(2/3; 22/27 ] " 3/4 ® |
|||||||
0 |
(0 ; 2/3 ] |
01 |
(4/9; 2/3 ] |
101 |
(16/27; 2/3 ] " 5/8 ® |
|||
100 |
(4/9; 16/27 ] " 1/2 ® |
|||||||
00 |
(0; 4/9 ] |
001 |
(8/27; 4/9 ] " 3/8 ® |
|||||
000 |
(0; 8/27 ] " 1/4 ® |
Средняя длина кода на единицу сообщения
Приведем процедуру арифметического кодирования для последовательности произвольной длины:
While there are still input symbols do
get an input symbol
code_range = high - low.
high = low + code_range*high_range(symbol)
low = low + code_range*low_range(symbol)
Декодеру , как и кодеру, известна таблица распределения отрезков, выделенных символам алфавита источника. Декодирование арифметического кода сообщения происходит по следующему алгоритму:
Шаг 1 По таблице отрезков символов алфавита определяется интервал, содержащий текущий код сообщения – и по этому интервалу из той же таблицы однозначно определяется символ исходного сообщения. Если это маркер конца сообщения, то конец, иначе – переход к шагу 2 .
Шаг 2 Из текущего кода вычитается нижняя граница содержащего его интервала. Полученная разность делится на длину этого интервала. Полученное значение считается новым текущим кодом. Переход к шагу 1 .
Рассмотрим пример декодирования сообщения, сжатого по алгоритму арифметического кодирования.
Пример 3 Длина исходного сообщения 10 символов. Двоичный арифметический кодсообщения 000101000001100001011111 2 =1316259 10 .
Вещественное число, принадлежащее интервалу, однозначно определяющему закодированное сообщение, . Это число и будет текущим кодом сообщения.
По
исходной таблице значений д.с.в. и назначенных им интервалов (таблица
2.7
)
определяется отрезок, которому принадлежит это число, - }