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

Сопоставим каждой последовательности бит множество всех вещественных чисел, лежащих в интервале [a; b). Разным файлам будут соответствовать различные интервалы.

Разобьем исходную последовательность на отдельные элементы так, чтобы по ним можно было ее однозначно восстановить. Расположим эти элементы в определенном порядке. Каждый такой элемент будет представлять собой дискретную случайную величину. Будем рассматривать эти элементы последовательно. В начале сопоставим всей последовательности интервал [0; 1).

Пусть на некотором шаге обрабатывается элемент с номером i и текущий интервал равен [a_i-1; b_i-1). Пусть i-й элемент может принимать K_i значений (пусть это будут целые числа от 1 до K) и известны вероятности этих значений P_i1, P_i2, ..., P_iK. Каждому возможному значению j i-го элемента соответствует некоторый интервал [c_ij; d_ij), причем c_i1=a_i-1, d_iK=b_i-1, c_ij=d_i,j-1 (2≤j≤K_i), т.е. интервалы всех возможных значений не пересекаются и полностью покрывают текущий интервал [a_i-1; b_i-1). Пусть ширина каждого интервала будет прямо пропорциональна вероятности соответствующего значения. Тогда для всех j от 2 до K_i можно записать . Если в данной последовательности значение текущего элемента равно v, то интервал [a_i-1; b_i-1) заменяется интервалом [a_i; b_i)=[c_iv; d_iv). После сужения интервала для текущего элемента происходит переход к следующему элементу, и.т.д.

После обработки всех элементов сжимаемой последовательности для ее однозначного восстановления необходимо знать любое из вещественных чисел, лежащих в полученном интервале [a; b) и ожидаемую структуру последовательности (т.е. количество ее элементов, возможные значения каждого элемента и вероятности этих значений).

Рассмотрим процесс восстановления элементов исходной последовательности по некоторому числу из интервала [a; b). В начале текущий интервал положим равным [0; 1). Любое входное число попадает в этот интервал.

Пусть на некотором шаге текущий интервал равен [a_i-1; b_i-1), а текущий рассматриваемый элемент с номером i может принимать K_i значений с вероятностями P_i1, P_i2, ..., P_iK, каждому из которых соответствует интервал [c_ij; d_ij). Пусть входное число лежит в интервале [a_i-1; b_i-1). Поскольку все интервалы [c_ij; d_ij) (1≤j≤K) не пересекаются и полностью покрывают интервал [a_i-1; b_i-1), то входное число принадлежит ровно одному из них. Если это интервал [c_iv; d_iv), то он становится текущим интервалом [a_i; b_i) (при этом входное число по-прежнему лежит в текущем интервале), а v становится значением текущего рассматриваемого элемента i. После этого рассматривается следующий элемент, и.т.д. После нахождения всех элементов по ним строится исходная последовательность.

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

Если при кодировании неизвестны законы распределения отдельных элементов последовательности, то используются их приближенные оценки. Чем ближе эти оценки к истинным законам распределений, тем ближе размер сжатой последовательности, выраженный в битах, к величине информационной энтропии этой последовательности. Из этого следует, что эффективность сжатия напрямую зависит от точности используемых оценок законов распределения ее элементов.

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