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

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

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

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


Характеристики[ | ]

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

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

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

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

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

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

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

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

Используя метод арифметического ирования, можно достичь почти оптимального представления для заданного набора символов и их вероятностей (согласно теории энтропийного ирования источника Шеннона оптимальное представление будет стремиться к числу −log2P бит на каждый символ, вероятность которого 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. История развития теории сжатия информации Архивная копия от 28 декабря 2010 на Wayback Machine / Compression.ru, Sarmin Alexey, 10 марта 2011
  2. Dr. Dobb's Data Compression Newsletter Архивная копия от 11 декабря 2017 на Wayback Machine, August 13, 2001

Ссылки[ | ]