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

Две характерные черты арифметического кодирования позволяют легко расширить этот метод сжатия.

1. Основной шаг кодирования состоит из двух операций

;

.

Это означает, что для кодирования символа X необходимо сообщить кодеру накопленные частоты этого символа и символа, расположенного над ним (см. табл. 1.24 с примером накопленных частот). Но тогда частота X (или ее вероятность) может изменяться каждый раз после кодирования, при условии, что кодер и декодер будут это делать согласованно.

2. Порядок символов в табл. 1.24 не имеет значения. Символы могут даже менять свое место в таблице, если это делать согласованно с декодером.

Имея это в виду, легко понять, как может работать процесс адаптивного арифметического кодирования. Алгоритм кодирования состоит из двух частей: вероятностная модель и арифметический кодер. Вероятностная модель читает следующий символ из входного файла и вызывает кодер, сообщая ему символ и две текущие накопленные частоты. Затем модель увеличивает на единицу счетчик символов и изменяет накопленные частоты. Главным здесь является то, что вероятности символов определяются моделью по старым значениям счетчиков, которые увеличиваются только после кодирования данного символа. Это позволяет декодеру делать зеркальные действия. Кодер знает символ, который ему предстоит закодировать, а декодер должен его распознать по сжатому коду, поэтому декодер знает только старые значения счетчиков, но может увеличивать и изменять их значения точно так же как и кодер.

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

11	12	12	2	5	1	2	19	12	8
(а)
19	12	12	12	11	8	5	2	2	1
(b)

Табл. 1.36. Алфавит из 10 символов и их счетчики.

Оказывается, что такой массив легко организовать в виде структуры, которая позволит делать поиск и обновление этого массива. Такой структурой является двоичное сбалансированное дерево. (Сбалансированным двоичным деревом служит полное дерево, в котором некоторые правые нижние узлы отсутствуют.) На дереве должны быть узлы для каждого символа алфавита, и поскольку оно сбалансировано, его высота равна , где  - размер алфавита. При  высота сбалансированного дерева равна 8, поэтому начав с корня, поиск символа займет не более 8 шагов. Дерево организовано так, что более вероятный символ (у которого самый большой счетчик) находится ближе к корню дерева, что ускоряет процесс его поиска. В табл. 1.36а показан пример алфавита из 10 символов вместе со счетчиками. В табл. 1.36b этот же алфавит упорядочен по значениям счетчиков.

Упорядоченный массив размещен на дереве, изображенном на рис. 1.38а. Это простой и элегантный способ построения дерева. Сбалансированное двоичное дерево можно построить без использования указателей. Правило такое: первый элемент массива (с индексом 1) находится в корне, два узла-потомка элемента с индексом  имеют индексы  и , а родительский узел узла  имеет индекс  . Легко видеть, как процесс упорядочения массива разместит символы с большими счетчиками ближе к корню.

В дополнение к символу и его счетчику в каждом узле дерева будет храниться общая сумма счетчиков его левого поддерева. Эти величины будут использоваться при подсчете накопленных частот. Соответствующий массив показан в табл. 1.37а.

19	12	12	12	11	8	5	2	2	1
40	16	8	2	1	0	0	0	0	0
(а)
19	13	12	12	11	8	5	2	2	1
41	16	8	2	1	0	0	0	0	0
(b)

Табл. 1.37. Алфавит из 10 символов и их счетчики.

Предположим, что следующий прочитанный из входного файла символ был . Его счетчик изменяется с 12 до 13. Модель, имея упорядоченный массив, ищет самый дальний слева от  элемент, у которого счетчик меньше или равен счетчику .

Этот поиск может быть просто линейным, если массив короткий, или двоичным, если массив длинный. В нашем случае это будет элемент , который следует переставить с  (табл. 1.37b).

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

На рис. 1.38b показано дерево после этой перестановки. Обратите внимание на то, как меняются счетчики левых поддеревьев.

Наконец покажем, как вычисляются накопленные частоты с помощью этого дерева. Когда необходимо найти эту величину для символа X, модель идет по веткам из корня до узла содержащего X, добавляя числа в переменную af. Каждый раз, когда выбирается правая ветвь из внутреннего узла N, к переменной af добавляются два числа (счетчик символа и счетчик левого дерева), лежащие в этом узле. При выборе левой ветви переменная af не меняется. Когда узел, содержащий X найден, счетчик левого дерева этого узла добавляется к af. Теперь значение переменной af равно в точности величине LowCumFreq[X].

Для примера проследим на рис. 1.38а из корня дерева до символа , чья накопленная частота равна 28. Правая ветвь выбрана в узле , поэтому в af добавлена сумма . В узле  выбрана левая ветвь, поэтому к af ничего не добавлено. В результате , что можно проверить на рис. 1.38с. Величина HighCumFreq[X] получается прибавлением счетчика  (равного 1) к LowCumFreq[X].

При проходе по дереву от корня до символа  алгоритм выполняет следующие действия.

1. Находит  в массиве с помощью двоичного поиска по дереву. В нашем примере  находится в позиции 10 массива.

2. Делит 10 на 2. Остаток равен 0. Это означает, что  является левым потомком своего родителя. Частное 5 равно индексу в массиве его родителя.

3. Находит в позиции 5 символ . Делит 5 пополам. Остаток 1 говорит о том, что  является правым потомком своего родителя, имеющего индекс 2.

4. Элемент массива с индексом 2 равен . Алгоритм делит 2 пополам. Остаток равен 0, то есть,  - левый потомок родителя, который имеет индекс 1 и находится в корне, поэтому процесс останавливается.

Метод компрессии РРМ, описанный в [Cleary, Witten 84] и [Moffat 90], является хорошим примером статистической модели, использующей арифметическое кодирование.

Статистика подобна бикини. То, что она показывает,
соблазнительно, а то, что скрывает - жизненно важно.
Аарон Левинытейн