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

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

Поэтому хотелось бы иметь такой алгоритм кодирования, который позволял бы кодировать символы менее чем 1 бит. Одним из таких алгоритмов является арифметическое кодирование, представленное в 70-х годах 20 века. При рассмотрении этого алгоритма будем исходить из того факта, что сумма вероятностей символов (и соответствующим им относительным частотам появления этих символов), всегда равна 1.Отсительные частоты появления могут определяться путем текущих статистических измерений исходного сообщения (это первый « проход» процедуры кодирования). Особенностью арифметического кодирования является то, что для отображения последовательности символов на интервале [0,1] используются относительные частоты их появления.

Пример определения частоты появления символов в сообщении

BANANANBAB.

Результатом такого отображения является сжатие символов или посимвольное сжатие в соответствии с их вероятностями, т.е. результатом арифметического сжатия будет некоторая дробь из интервала [0,1], который представляется двоичной записью (это второй «проход» процедуры кодирования). Заметим, что такой двухпроходный алгоритм может быть реализован в ранее рассмотренных кодах Шеннона – Фано и Хаффмана.

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

Эффективность арифметического кодирования растет с увеличением длины сжимаемого сообщения. Заметим, что в кодах Шеннона – Фано и Хаффмана такого не происходит.

Арифметическое кодирование заключается в построении отрезка , однозначно определяющего заданную последовательность символов в соответствии с их вероятностями. Объединение всех отрезков, пересекающихся только в граничных точках, для вероятностей каждого символа должно образовывать формальный интервал [0,1]. Для последнего полученного интервала, соответствующего последнему принятому символу сообщения, находит число, принадлежащее его внутренней части. Это число в двоичном представлении и будет кодом для рассматриваемой последовательности.

Пример. Пусть задан алфавит X={a ,b}, p(a) =, p(b) = . Необходимо закодировать сообщение {aba}.

Шаг кодирования	Поступающий символ	Интервал
0	нет	[ 0,1 ]
1	a	[ 1]
2	b	[ ]
3	a

1

1

0

.

b

a

1

2.

b

a

1. ,

2. ,

3. 

3

.

a

b

1. ,

2. ,

3.

В таком алгоритме в конце сообщения должен стоять некий маркер, обозначающий конец сообщения.

Код сообщения {aba}=10000.

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

4. Алгоритм универсального кодирования методом Лемпела-Зива.

Этот алгоритм относится к классу универсальных потому, что он не требует априорных знаний о статистике символов. Такой метод носит менее математически обоснованный характер, но более практический.

Первый алгоритм разработан в 1971 году в Израиле Лемпелом и Зивом (LZ 77). Одной из причин популярности алгоритма LZ 77, а также семейства алгоритмов LZ 77, является их исключительная простота при высокой эффективности сжатия.

LZ 77 использует уже просмотренную часть сообщения как словарь, а чтобы добиться сжатия он пытается заменить очередной фрагмент сообщения на соответствующий указатель в содержимое словаря, т.е. LZ 77 использует как бы скользящее окно по сообщению, разделенное на две части. Большая часть окна - словарь, включающий уже просмотренную часть сообщения, меньшая часть окна является буфером, содержащим еще не закодированные символы входного потока.

Алгоритм пытается найти в словаре фрагмент сообщения, совпадающий с содержимым буфера. На практике размер словаря составляет несколько кбайт, а размер буфера - до 100 байт. В результате кодирования формируется совокупность групп по три элемента в каждой < a,l,z >, где a- относительный адрес в словаре, т.е. смещение в словаре относительно его начала до первого символа фрагмента, с которым совпадает содержимое буфера; l - число совпадений элементов буфера и словаря; z –первый несовпадающий со словарем символ в буфере.

Пример. КРАСНАЯ КРАСКА

Шаг кодирования	Словарь (8)	Буфер (5)	Код
1	……..	КРАСН	< 0,0,К>
2	…….К	РАСНА	< 0,0,Р>
3	……КР	АСНАЯ	< 0,0,А>
4	…..КРА	СНАЯ_	< 0,0,С>
5	….КРАС	НАЯ _К	< 0,0,Н>
6	…КРАСН	АЯ_КР	< 5,1,Я>
7	.КРАСНАЯ	_КРАС	< 0,0,_>
8	КРАСНАЯ_	КРАСК	< 0,4,К>
9	АЯ_КРАСК	А	< 0,0,А>

Для данного кода длину кодовой комбинации можно определить по следующей формуле:

- операция округления в большую сторону.

Такой алгоритм еще часто называют словарным. Очевидно, что сжатие будет иметь место, если длина полученной кодовой комбинации будет меньше кода того же сообщения при непосредственном кодировании. Для словарного кодирования учтено:

1.Часто повторяющиеся цепочки кодируются очень эффективно.

2.Редко повторяющиеся символы и их последовательности с течением времени удаляются из словаря.

3.Можно доказать, что словарное кодирование асимптотически оптимально, т.е. что длина кодового слова стремится к энтропии этого текста.

4.Практически достижимая степень сжатия для этих кодов 50-60 %.

В семейство алгоритмов LZ входит несколько моделей, которые модифицированы различными авторами в аспекте механизмов формирования кодовых групп, но во всех механизмах используется словарь. В настоящее время наибольшее распространение получил алгоритм LZW (1984 г.). В этом алгоритме длина кода уменьшается, так как не используется буфер. А кодирование проводится только по словарю, следовательно, кодовая группа определяется только длиной словаря.

Декодирование словарного кода происходит в обратном порядке и упрощается тем, что не требует поиска совпадений в словаре.

5. Особенности программ- архиваторов.

Если коды алгоритмов типа LZ передать для кодирования алгоритму Хаффмана или арифметическому алгоритму, то полученный двухшаговый алгоритм дает результат сжатия, подобный случайным программам-архиваторам, таким, как GZ, AGZ, PK zip. Наибольшую степень сжатия дают двухпроходные алгоритмы, которые последовательно сжимают два раза исходные данные, но они соответственно и работают в два раза медленнее. Большинство программ- архиваторов сжимают каждый файл по отдельности, хотя некоторые способны это делать в потоке файлов, что дает соответствующее увеличение степени сжатия, но и одновременно усложняет способы работы с полученным архивом. Например, замена в таком архиве файла на более новую версию может потребовать перекодирования всего архива. В общем потоке с файлами способен работать архиватор RAR, а в ОС Unix практически все архиваторы, такие как Gzip, Bzip2 и т.д.

Расширение файла	Программа-архиватор	Тип кодирования
ark	arc, PKazc	LZW, Хаффана
zip	zip, PKzip, unzip, PKunzip	LZW, LZ77, Хаффмана, Шеннона – Фано
azj	azj	LZ77, Хаффмана
pak	pak	LZW
gif	графика	LZW
tif, tiff	факс	LZW

5. Сжатие с потерями.

Сжатие с потерями используется в основном для трех видов данных:

1.Полноцветная графика.

2.Видеоинформация.

3.Звуковая информация.

Сжатие с потерями обычно происходит в два этапа:

1.Исходная информация с потерями приводится к виду, в котором ее можно эффективно сжимать алгоритмами второго этапа сжатия без потерь.

Основная идея сжатия графической информации с потерями состоит в следующем: каждая точка графической картинки характеризуется тремя равноценными атрибутами – яркость, цветность, насыщенность. Человек воспринимает их не как равные, т.е. полностью воспринимается информация о яркости, и гораздо меньшей степени о цветности и насыщенности, что позволяет отбрасывать часть информации о двух последних атрибутах без существенной потери качества изображения. Для сжатия графической информации с потерями в конце 80-х годов был установлен единый стандарт JPEG. В этом формате сложно регулировать степень сжатия, задавая степень потери качества.

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

На сегодняшний день существует много форматов сжатия видеоинформации, но наиболее распространенным является MPEG. Этот стандарт был предложен в 1988 году и является практически единственным для спутникового телевидения и записи информации на DVD, CD и т.д.

Сжатие звуковой информации с потерями осуществляется на основе ограничении спектра звукового сигнала диапазоном реальной слышимости человека. Используют для этого различные стандарты сжатия звуковых файлов и достаточно часто MPEG без видеоданных.