1.8. Адаптивное арифметическое кодированиеДве характерные черты арифметического кодирования позволяют легко расширить этот метод сжатия. 1. Основной шаг кодирования состоит из двух операций
Это означает, что для кодирования символа X необходимо сообщить кодеру накопленные частоты этого символа и символа, расположенного над ним (см. табл. 1.24 с примером накопленных частот). Но тогда частота X (или ее вероятность) может изменяться каждый раз после кодирования, при условии, что кодер и декодер будут это делать согласованно. 2. Порядок символов в табл. 1.24 не имеет значения. Символы могут даже менять свое место в таблице, если это делать согласованно с декодером. Имея это в виду, легко понять, как может работать процесс адаптивного арифметического кодирования. Алгоритм кодирования состоит из двух частей: вероятностная модель и арифметический кодер. Вероятностная модель читает следующий символ из входного файла и вызывает кодер, сообщая ему символ и две текущие накопленные частоты. Затем модель увеличивает на единицу счетчик символов и изменяет накопленные частоты. Главным здесь является то, что вероятности символов определяются моделью по старым значениям счетчиков, которые увеличиваются только после кодирования данного символа. Это позволяет декодеру делать зеркальные действия. Кодер знает символ, который ему предстоит закодировать, а декодер должен его распознать по сжатому коду, поэтому декодер знает только старые значения счетчиков, но может увеличивать и изменять их значения точно так же как и кодер. Модель должна накапливать символы, их счетчики (частоты появления) и накопленные частоты в некотором массиве. Этот массив следует хранить упорядоченно по значениям счетчиков символов. При чтении очередного символа происходит увеличение его счетчика, затем модель обновляет накопленные частоты и смотрит, надо ли менять порядок символов для соблюдения упорядоченности всего массива.
Табл. 1.36. Алфавит из 10 символов и их счетчики. Оказывается, что такой массив легко организовать в виде структуры, которая позволит делать поиск и обновление этого массива. Такой структурой является двоичное сбалансированное дерево. (Сбалансированным двоичным деревом служит полное дерево, в котором некоторые правые нижние узлы отсутствуют.) На дереве должны быть узлы для каждого символа алфавита, и поскольку оно сбалансировано, его высота равна Упорядоченный массив размещен на дереве, изображенном на рис. 1.38а. Это простой и элегантный способ построения дерева. Сбалансированное двоичное дерево можно построить без использования указателей. Правило такое: первый элемент массива (с индексом 1) находится в корне, два узла-потомка элемента с индексом В дополнение к символу и его счетчику в каждом узле дерева будет храниться общая сумма счетчиков его левого поддерева. Эти величины будут использоваться при подсчете накопленных частот. Соответствующий массив показан в табл. 1.37а.
Табл. 1.37. Алфавит из 10 символов и их счетчики. Предположим, что следующий прочитанный из входного файла символ был Этот поиск может быть просто линейным, если массив короткий, или двоичным, если массив длинный. В нашем случае это будет элемент Рис. 1.38. Адаптивное арифметическое кодирование. На рис. 1.38b показано дерево после этой перестановки. Обратите внимание на то, как меняются счетчики левых поддеревьев. Наконец покажем, как вычисляются накопленные частоты с помощью этого дерева. Когда необходимо найти эту величину для символа X, модель идет по веткам из корня до узла содержащего X, добавляя числа в переменную af. Каждый раз, когда выбирается правая ветвь из внутреннего узла N, к переменной af добавляются два числа (счетчик символа и счетчик левого дерева), лежащие в этом узле. При выборе левой ветви переменная af не меняется. Когда узел, содержащий X найден, счетчик левого дерева этого узла добавляется к af. Теперь значение переменной af равно в точности величине LowCumFreq[X]. Для примера проследим на рис. 1.38а из корня дерева до символа При проходе по дереву от корня до символа 1. Находит 2. Делит 10 на 2. Остаток равен 0. Это означает, что 3. Находит в позиции 5 символ 4. Элемент массива с индексом 2 равен Метод компрессии РРМ, описанный в [Cleary, Witten 84] и [Moffat 90], является хорошим примером статистической модели, использующей арифметическое кодирование. Статистика подобна бикини. То, что она показывает,
|