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

П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вале

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