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

Арифметическое кодирование — один из алгоритмов энтропийного сжатия.

В отличие от алгоритма Хаффмана, не имеет жесткого постоянного соответствия входных символов группам бит выходного потока. Это даёт алгоритму большую гибкость в представлении дробных частот встречаемости символов.

Как правило, превосходит алгоритм Хаффмана по эффективности сжатия, позволяет сжимать данные с энтропией, меньшей 1 бита на кодируемый символ, но некоторые версии имеют патентные ограничения от компании IBM.

Характеристики

Обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ требуется почти $H$ бит, где $H$ — информационная энтропия источника.

В отличие от алгоритма Хаффмана, метод арифметического кодирования показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов. Однако в случае равновероятного распределения символов, например, для строки бит 010101…0101 длины s метод арифметического кодирования приближается к префиксному коду Хаффмана и даже может занимать на один бит больше.

Принцип действия

Пусть имеется некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок от 0 до 1.

Назовём этот отрезок рабочим. Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа, и каждый такой отрезок будет соответствовать одному символу.

Теперь возьмём символ из потока и найдём для него отрезок среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.

Пример работы метода арифметического кодирования

Вероятностная модель

Используя метод арифметического кодирования, можно достичь почти оптимального представления для заданного набора символов и их вероятностей (согласно теории энтропийного кодирования источника Шеннона, оптимальное представление будет стремиться к числу −log₂P бит на каждый символ, вероятность которого P). Алгоритмы сжатия данных, использующие в своей работе метод арифметического кодирования, перед непосредственным кодированием формируют модель входных данных на основании количественных или статистических характеристик, а также найденных в кодируемой последовательности повторений или паттернов — любой дополнительной информации, позволяющей уточнить вероятность появления символа P в процессе кодирования. Очевидно, что чем точнее определена или предсказана вероятность символа, тем выше эффективность сжатия.

Рассмотрим простейший случай статической модели для кодирования информации, поступающей с системы обработки сигнала. Типы сигналов и соответствующие им вероятности распределены следующим образом:

• 60%-я вероятность нейтрального значения сигнала, или NEUTRAL.
• 20%-я вероятность положительного значения сигнала, или POSITIVE.
• 10%-я вероятность отрицательного значения сигнала, или NEGATIVE.
• 10%-я вероятность признака конца кодируемой последовательности, или END-OF-DATA.

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

В качестве алфавита вероятностной модели метода можно рассматривать любой набор символов, исходя из особенностей решаемой задачи. Более эвристические подходы, использующие основную схему метода арифметического кодирования, применяют динамические или адаптивные модели. Идея данных методов заключается в уточнении вероятности кодируемого символа за счёт учёта вероятности предшествующего или будущего контекста (то есть, вероятность появления кодируемого символа после определённого k-го числа символов слева или справа, где k — это порядок контекста).

Кодирование сообщения

Возьмём для примера следующую последовательность:

NEUTRAL NEGATIVE END-OF-DATA

Сначала разобьём отрезок от 0 до 1 согласно частотам сигналов. Разбивать отрезок будем в порядке, указанном выше: NEUTRAL — от 0 до 0,6; NEGATIVE — от 0,6 до 0,8; END-OF-DATA — от 0,8 до 1.

Теперь начнём кодировать с первого символа. Первому символу — NEUTRAL соответствует отрезок от 0 до 0,6. Разобьём этот отрезок аналогично отрезку от 0 до 1.

Закодируем второй символ — NEGATIVE. На отрезке от 0 до 0,6 ему соответствует отрезок от 0,48 до 0,54. Разобьём этот отрезок аналогично отрезку от 0 до 1.

Закодируем третий символ — END-OF-DATA. На отрезке от 0,48 до 0,54 ему соответствует отрезок от 0,534 до 0,54.

Так как это был последний символ, то кодирование завершено. Закодированное сообщение — отрезок от 0,534 до 0,54 или любое число из него, например, 0,538.

Декодирование сообщения

На диаграмме представлено декодирование итогового интервального значения 0,538 согласно модели в приведённом примере. Область интервала разбивается на подинтервальные области согласно вероятностным характеристикам появления соответствующих символов. Затем, очередной выбранный интервал разбивается аналогичным способом.

Предположим, что нам необходимо раскодировать сообщение методом арифметического кодирования согласно описанной выше модели. Сообщение в закодированном виде представлено дробным значением 0,538 (для простоты используется десятичное представление дроби, вместо двоичного основания). Предполагается, что закодированное сообщение содержит ровно столько знаков в рассматриваемом числе, сколько необходимо для однозначного восстановления первоначальных данных.

Начальное состояние процесса декодирования совпадает с процессом кодирования и рассматривается интервал [0,1). На основании известной вероятностной модели дробное значение 0,538 попадает в интервал [0, 0,6). Это позволяет определить первый символ, который был выбран кодировщиком, поэтому его значение выводится как первый символ декодированного сообщения.

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

Как и алгоритм Хаффмана, арифметическое кодирование может быть адаптивным (см. также Адаптивный алгоритм Хаффмана). Такой алгоритм позволяет строить разбиение каждого интервала на подинтервалы в поточном режиме (без предварительного сканирования данных), не имея никаких начальных знаний из исходного распределения, что позволяет за один проход сжать данные. Преимуществом этого способа является возможность кодировать на лету (аналогично адаптивному алгоритму Хаффмана).

Известно, что совсем необязательно, чтобы подинтервалы более частых символов располагались ближе к началу рабочего интервала, порядок может быть абсолютно любым. Поэтому для адаптивного арифметического кодирования можно расставить подинтервалы, соответствующие каждому символу, в порядке появления этих символов в тексте, зарезервировав последний подинтервал для случая, когда очередной символ встречается во входном потоке первый раз. В этом случае передается сначала этот последний подинтервал, а затем сам символ, что позволяет декодеру "опознать" его. Когда известных с начала входного потока символов несколько, их кумулятивные частоты можно хранить в обычном массиве, если же их число достигает сотни и больше, удобно применять такую структуру данных, как бинарное сбалансированное дерево, в котором каждая ветвь хранит два значения: непосредственную частоту символа и сумму частот всех символов, входящих в эту ветвь. При появлении очередного символа его частота в дереве увеличивается на 1, но лишь после изменения рабочего интервала, иначе декодирование станет невозможным.

Другой вариант алгоритма для входного потока, структура которого заранее известна, предложен здесь: . В этом случае не резервируется подинтервал для нового символа, а подинтервалы для всех символов с самого начала имеют "вес", равный 1 (и в дальнейшем он всегда на 1 больше, чем в первом варианте).

Ссылки

• (August 13, 2001) Dr. Dobb’s Data Compression Newsletter