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

В 70-е годы у алгоритма Хаффмена появился достойный конкурент - арифметическое кодирование. Этот метод основан на идее преобразования входного потока в одно число с плавающей запятой. Естественно, что чем длиннее сообщение, тем длиннее получающееся в результате кодирования число. Итак, на выходе арифметического компрессора получается число, меньшее 1 и большее либо равное 0. Из этого числа можно однозначно восстановить последовательность символов, из которых оно было построено.     Рассмотрим работу арифметического компрессора на примере сообщения "BILL GATES".    Поставим в соответствие каждому символу сообщения вероятность его появления в сообщении (табл. 1).

Таблица 1 Вероятности появления символов в сообщении
Символ	Вероятность
Пробел	1/10
A	1/10
B	1/10
E	1/10
G	1/10
I	1/10
L	2/10
S	1/10
T	1/10

   Затем присвоим каждому символу интервал вероятности в промежутке от 0 до 1. Длина интервала для символа равна вероятности его появления в сообщении. Положение интервала вероятности каждого символа не имеет значения. Важно только то, чтобы и кодер, и декодер располагали символы по одинаковым правилам.

Интервалы вероятности для символов нашего сообщения приведены в табл. 2.

Таблица 2 Интервалы вероятностей для символов сообщения
Символ	Вероятность	Интервал
Пробел	1/10	[0.00, 0.10]
A	1/10	[0.10, 0.20]
B	1/10	[0.20, 0.30]
E	1/10	[0.30, 0.40]
G	1/10	[0.40, 0.50]
I	1/10	[0.50, 0.60]
L	2/10	[0.60, 0.80]
S	1/10	[0.80, 0.90]
T	1/10	[0.90, 1.00]

   В общем виде алгоритм арифметического кодирования может быть описан следующим образом:

НижняяГраница = 0.0; ВерхняяГраница= 1.0; Пока ((ОчереднойСимвол = ДайОчереднойСимвол()) != КОНЕЦ)    Интервал = ВерхняяГраница - НижняяГраница;    ВерхняяГраница = НижняяГраница + Интервал * ВерхняяГраницаИнтервалаДля(ОчереднойСимвол);    НижняяГраница = НижняяГраница + Интервал * НижняяГраницаИнтервалаДля(ОчереднойСимвол); Конец Пока Выдать (НижняяГраница)

Для нашего примера этот алгоритм будет работать следующим образом (табл. 3).

Таблица 3 Шаги алгоритма арифметического кодирования при обработке сообщения
Очередной символ	Нижняя граница	Верхняя граница
	0.0	1.0
B	0.2	0.3
I	0.25	0.26
L	0.256	0.258
L	0.2572	0.2576
ПРОБЕЛ	0.25720	0.25724
G	0.257216	0.257220
A	0.2572164	0.2572168
T	0.25721676	0.2572168
E	0.257216772	0.257216776
S	0.2572167752	0.2572167756

   Таким образом, согласно нашей схеме, число 0.2572167752 однозначно кодирует сообщение "BILL GATES". Алгоритм арифметического декодирования может быть описан следующим образом:

Число = ПрочитатьЧисло(); Всегда    Символ =Найти_Символ_В_интервал_Которого_Попадает_Число(Число)    Выдать (Символ) Интервал = ВерхняяГраницаИнтервалаДля (Символ) -НижняяГраницаИнтервалаДля (Символ);    Число = Число - НижняяГраницаИнтервалаДля(Символ);    Число = Число / Интервал; Конец Всегда

   В приведенном алгоритме не рассматривается вопрос остановки декодера. В листинге приведенной в конце статьи программы декодер останавливается при обнаружении специального символа EOF (конец файла).    Для нашего примера декодер будет работать следующим образом (табл. 4).

Таблица 4Шаги работы алгоритма арифметического декодирования
Число	Cимвол	Нижняя граница	Верхняя граница	Интервал
0.2572167752	B	0.2	0.3	0.1
0.572167752	I	0.5	0.6	0.1
0.72167752	L	0.6	0.8	0.2
0.6083876	L	0.6	0.8	0.2
0.041938	ПРОБЕЛ	0.0	0.1	0.1
0.41938	G	0.4	0.5	0.1
0.1938	A	0.2	0.3	0.1
0.938	T	0.9	1.0	0.1
0.38	E	0.3	0.4	0.1
0.8	S	0.8	0.9	0.1
0.0

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