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

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

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

Пример

В табл. 3.8 приведены 5 векторов движения (-2, -1,0,1,2) вместе с их вероятностями из примера 1 в § 3.5.2. Каждому вектору приписывается подынтервал в пределах от 0,0 до 1,0, длина которого совпадает с вероятностью появления данного вектора. В этом примере вектор (-2) имеет вероятность 0,1, и ему приписан подинтервал (0;0,1) (т.е. 10% от обшей длины интервала (0,0; 1,0)). Вектор (-1) имеет вероятность 0,2, и ему отведено 20% от общего интервала — подинтервал (0,1;0,3). После назначения подынтервалов каждому вектору весь интервал (0,0;1,0) оказывается разделенным между символами данных (векторами в нашем случае) в соответствии с их вероятностями (рис. 3.48).

Рис. 3.48. Разбиение на подынтервалы.

Процедура кодирования для последовательности векторов (0,-1,0,2).

		Интервал	Символ
	Процедура кодирования	(L—Н)	(L—Н)	Подынтервал
1.	Задать начальный интервал.	0 - 1,0
2.	Для первого символа найти соответствующий ему подынтервал.		(0)	0,3-0,7
3.	Задать новый интервал (1), равный этому подынтервалу.	0,3—0,7
4.	Для следующего символа найти соответствующий ему подынтервал.		(-1)	0,1—0,3
5.	Задать новый интервал (2), пропорц. этому подынтервалу внутри предыдущего интервала.	0,34—0,42
6.	Найти следующий подынтервал.		(0)	0,3-0,7
7.	Задать новый интервал (3), пропорц. этому подынтервалу внутри предыдущего интервала.	0,364—0,396
8.	Найти следующий подынтервал.		(2)	0,9—1,0
9.	Задать новый интервал (4), пропорц. этому подынтервалу внутри предыдущего интервала.	0,3928-0,396

После кодирования очередного символа интервал (L, Н) постепенно уменьшается. В конце процедуры кодирования (четыре шага в этом примере) у нас остается некоторый конечный интервал. Вся исходная последовательность символов может быть закодирована любым числом из этого интервала. В предыдущем примере достаточно передать любое число из интервала от 0,3928 до 0,396, например, 0,394. На рис. 4.49 изображен процесс последовательного разделения исходного интервала на все более мелкие интервалы по мере обработки символов исходной последовательности. После кодирования первого символа (вектора 0) новым интервалом стал (0,3; 0,7). Следующий символ (вектор -1) выбирает новый интервал (0,34; 0,42) и т.д. Последний символ (вектор -2) выбирает интервал (0,3928; 0,396), и передаваемое число 0,394 попадает в этот интервал. Число 0,394 можно представить в виде десятичного числа с фиксированной десятичной точкой, для чего потребуется 9 бит. В итоге исходная последовательность (0, -1,0,2) будет закодирована в сжатом виде кода из 9 бит.

Процедура декодирования.

	Процедура декодирования	Интервал Подынтервал	Декод. символ
1.	Задать начальный интервал.	0—1,0
2.	Найти подынтервал, куда	0,3—0,7	(0)
	попадает принятое число. Это
	определит первый символ.
3.	Задать новый интервал (1),	0,3—0,7
	равный этому подынтервалу.
4.	Найти подынтервал нового	0,34—0,42	(-1)
	интервала, куда попадает
	принятое число. Это даст
	второй символ.
5.	Задать новый интервал (2),	0,34—0,42
	равный этому подынтервалу.
6.	Найти подынтервал этого	0,364—0,396	(0)
	интервала, куда попадает
	принятое число. Это даст
	третий символ.
7.	Задать новый интервал (3),	0,364—0,396
	равный предыдущему
	подынтервалу.
8.	Найти подынтервал этого	0,3928—0,396	(2)
	интервала, куда попадает
	принятое число. Это определит
	четвертый символ.

Таблица 3.8. Векторы движения, вероятности и подынтервалы (последовательность №1).

Вектор Вероятность Подынтервал
-2 0,1	3,32	(0,0, 0,1)
-1 0,2	2,32	(0,1, 0,3)
0 0,4	1,32	(0,3, 0,7)
+1 0,2	2,32	(0,7, 0,9)
+2 0,1	3,32	(0,9, 1,0)

Рис. 3.49. Пример арифметического кодирования.

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

бит.

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