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

1. Основной шаг кодирования состоит из двух операций
Low := Low+(High-Low+l)*LowCmnFreq[X]/10;
High := Low+(High-Low+l)*HighCuinFreq[X]/10-l.
Это означает, что для кодирования символа X необходимо сообщить кодеру накопленные частоты этого символа и символа, расположенного над ним. Но тогда частота X (или ее вероятность) может изменяться каждый раз после кодирования, при условии, что кодер и декодер будут это делать согласованно.

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

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

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

Такой структурой является двоичное сбалансированное дерево. (Сбалансированным двоичным деревом служит полное дерево, в котором некоторые правые нижние узлы отсутствуют.) На дереве должны быть узлы для каждого символа алфавита, и поскольку оно сбалансировано, его высота равна [log2 n], где n - размер алфавита. При n = 256 высота сбалансированного дерева равна 8, поэтому начав с корня, поиск символа займет не более 8 шагов. Дерево организовано так, что более вероятный символ (у которого самый большой счетчик) находится ближе к корню дерева, что ускоряет процесс его поиска.

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

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