Триколор 

Open Library - открытая библиотека учебной информации. Теория информации

Классический вариант алгоритма

Сжатие по методу Хаффмана постепенно вытесняется арифметическим сжатием. Свою роль в этом сыграло то, что закончились сроки действия па­тентов, ограничивающих использование арифметического сжатия. Кроме того, алгоритм Хаффмана приближает относительные частоты появления символов в потоке частотами, кратными степени двойки (например, для символов а, Ъ, с, d с вероятностями 1/2, 1/4, 1/8, 1/8 будут использованы ко­ды О, 10, 110, 111), а арифметическое сжатие дает лучшую степень прибли­жения частоты. По теореме Шеннона наилучшее сжатие в двоичной ариф­метике мы получим, если будем кодировать символ с относительной часто­той f с помощью -log 2 (f) бит.

0.3 0,4 0.5 0.6 0.7

Относительная частота символа

"^~" Оптимальное сжатие
---- Метод Хаффмана

Рис. 1.1. График сравнения оптимального кодирования и кодирования по методу Хаффмана

На графике выше приводится сравнение оптимального кодирования и кодирования по методу Хаффмана. Хорошо видно, что в ситуации, когда относительные частоты не являются степенями двойки, сжатие становится менее эффективным (мы тратим больше битов, чем это необходимо). На­пример, если у нас два символа а и Ь с вероятностями 253/256 и 3/256, то в идеале мы должны потратить на цепочку из 256 байт -log 2 (253/256)-253-bg 2 (3/256)-3 = 23.546, т. е. 24 бита. При кодировании по Хаффману мы за­кодируем а и Ъ как 0 и 1 и нам придется потратить 1 -253+1 -3=256 бит, т. е. в 10 раз больше. Рассмотрим алгоритм, дающий результат, близкий к опти­мальному.

Арифметическое сжатие - достаточно изящный метод, в основе которого лежит очень простая идея. Мы представляем кодируемый текст в виде дро­би, при этом строим дробь таким образом, чтобы наш текст был представ­лен как можно компактнее. Для примера рассмотрим построение такой дро­би на интервале ; Ь[с]), а интервал для /-го кодируемого символа потока как ; Ь[с]), включающий 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) }

Упражнение. Применить интервальное кодирование без переноса для строки "ков.корова".

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

Пpи аpифметическом кодиpовании, в отличие от рассмотренных нами методов, когда кодируемый символ (или группа символов) заменяется соответствующим им кодом, результат кодирования всего сообщения пpедставляется одним или парой вещественных чисел в интеpвале от 0 до 1 . По меpе кодиpования исходного текста отобpажающий его интеpвал уменьшается, а количество десятичных (или двоичных) разрядов, служащих для его пpедставления, возpастает. Очеpедные символы входного текста сокpащают величину интеpвала исходя из значений их веpоятностей, определяемых моделью. Более веpоятные символы делают это в меньшей степени, чем менее веpоятные, и, следовательно, добавляют меньше разрядов к pезультату.Поясним идею арифметического кодирования на простейшем примере. Пусть нам нужно закодировать следующую текстовую строку: РАДИОВИЗИР.

Пеpед началом pаботы кодера соответствующий кодируемому тексту исходный интеpвал составляет . На самом деле, для однозначного декодирования теперь достаточно знать только одну границу интервала – нижнюю или верхнюю, то есть результатом кодирования может служить начало конечного интервала - 0,8030349772. Если быть еще более точным, то любое число, заключенное внутри этого интервала, однозначно декодируется в исходное сообщение. К примеру, это можно проверить с числом 0,80303498, удовлетворяющим этим условиям. При этом последнее число имеет меньшее число десятичных разрядов, чем числа, соответствующие нижней и верхней границам интервала, и, следовательно может быть представлено меньшим числом двоичных разрядов.

Нетрудно убедиться в том, что, чем шире конечный интервал, тем меньшим числом десятичных (и, следовательно, двоичных) разрядов он может быть представлен. Ширина же интервала зависит от распределения вероятностей кодируемых символов – более вероятные символы сужают интервал в меньшей степени и, следовательно, добавляют к результату кодирования меньше бит. Покажем это на простом примере.

Допустим, нам нужно закодировать следующую строку символов:
A A A A A A A A A # , где вероятность буквы А составляет 0,9. Процедура кодирования этой строки и получаемый результат будут выглядеть в этом случае следующим образом:

Входной символ Нижняя граница Верхняя граница

A 0,0 0,9

A 0,0 0,81

A 0,0 0,729

A 0,0 0,6561

A 0,0 0,59049

A 0,0 0,531441

A 0,0 0,4782969

А 0,0 0,43046721

А 0,0 0,387420489

# 0,3486784401 0,387420489

Результатом кодирования теперь может быть, к примеру, число 0.35 , целиком попадающее внутрь конечного интервала 0.3486784401 – 0.387420489. Для двоичного представления этого числа нам понадобится 7 бит (два десятичных разряда соответствуют примерно семи двоичным), тогда как для двоичного представления результатов кодирования из предыдущего примера – 0,80303498 – нужно 27 бит!!!

При декодировании пpедположим, что все что декодер знает о тексте, – это конечный интеpвал . Декодеру, как и кодеру, известна также таблица распределения выделенных алфавиту интервалов. Он сpазу же понимает, что пеpвый закодиpованный символ есть Р , так как результат кодирования целиком лежит в интеpвале Сколько существует трехразрядных шестнадцатеричных чисел, для которых будут одновременно

Лекция 13 Приемы и методы работы со сжатыми данными Лектор Ст. преподаватель Купо А.Н. Характерной особенностью большинства «классических» типов данных, с которыми традиционно работают люди, является определенная

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования Поволжский государственный университет телекоммуникаций и информатики кафедра ТОРС Задание и методические

УДК 519.6 Особенности кодирования текста с помощью алгоритма Хаффмана Кизянов Антон Олегович Приамурский государственный университет имени Шолом-Алейхема Студент Кузьмина Богдана Сергеевна Приамурский

ЛАБОРАТОРНАЯ РАБОТА Способы задания и основные характеристики сверточных кодов Сверточные коды широко применяются в самых различных областях техники передачи и хранения информации. Наиболее наглядными

УДК 004.8 ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ УПРАВЛЕНИЯ ПРОЕКТИРОВАНИЕМ ШКОЛЬНОГО РАСПИСАНИЯ Гущина О. А. Генетический алгоритм (ГА) адаптивный поисковый алгоритм, основанный на эволюционных факторах

Дискретная математика Часть 2 Кочетов Юрий Андреевич http://www.math.nsc.ru/lbrt/k5/dm.html Лекция 1 Алгоритмы, сортировки, AVL деревья 1 Алгоритмы и их сложность Компьютеры выполняют (пока) лишь корректно

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 ) определяется отрезок, которому принадлежит это число, - }