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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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