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

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

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

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

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

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

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

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

Для описания алгоритма на некотором алфавите с данными о частотности использования символов используется отрезок $[0;1]$, называемый «рабочим», на котором располагаются точки таким образом, что длины образованных отрезков будут равны частоте использования символа, и каждый такой отрезок соответствует одному символу.

Для символа из потока выбирается соответствующий ему отрезок, после чего он становится рабочим отрезком. Далее отрезок разбивается его таким же образом, как был разбит $[0;1]$; операция выполняется для некоторого числа последовательных символов. Затем выбирается произвольное число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и считаются результатом арифметического кодирования использованных символов потока.

Пример

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

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

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

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

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

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

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

Для кодирования последовательности «NEUTRAL POSITVE NEGATIVE END-OF-DATA» сначала разбивается отрезок от 0 до 1 согласно частотам сигналов: NEUTRAL — от 0 до 0,6; POSITVE — от 0,6 до 0,8; NEGATIVE — от 0,8 до 0,9; END-OF-DATA — от 0,9 до 1. Далее, осуществляется кодирование, начиная с первого символа: NEUTRAL соответствует отрезок от 0 до 0,6. Отрезок от 0 до 0,6 разбивается, и кодируется второй символ — NEGATIVE, на отрезке от 0 до 0,6 ему соответствует отрезок от 0,48 до 0,54. На полученном рабочем отрезке кодируется END-OF-DATA, этому символу соответствует отрезок от 0,534 до 0,54.

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

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

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

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

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

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

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

Ссылки

• (August 13, 2001) Dr. Dobb’s Data Compression Newsletter
• Реализация арифметического кодирования на C#