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

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

Введение

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

Написано по статье Иринёва Антона и Каширина Виктора [1]

Алгоритм

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

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

Пример

Произведем кодирование слова “ABBACD”

На первом шаге веса всех символов равны единице. Текущий интервал [0,1]. Первым кодируется символ A. Так как символов 4, и их веса одинаковые, то мы берем четверть от исходного отрезка. Получается интервал [0, 1/4]. Символ A обработан, увеличиваем его вес на единицу. Общий вес так же увеличился на 1. Следующим кодируется символ B. Разбиваем текущий интервал соответственно отношениям весов символов к весу всех символов. Выбираем интервал, соответствующий символу B - [1/10, 3/20]. Увеличиваем вес символа B на единицу, и так далее. Все шаги подробно описаны в таблице:

A	B	C	D	Общий вес	Кодируемая буква	Текущая длина промежутка	Получившийся интервал
1	1	1	1	4	A	1	[0, 1/4]
2	1	1	1	5	B	1/4	[1/10, 3/20]
2	2	1	1	6	B	1/20	[7/60, 8/60]
2	3	1	1	7	A	1/60	[7/60, 51/420]
3	3	1	1	8	C	1/210	[202/1680, 203/1680]
3	3	2	1	9	D	1/1680	[1826/15120, 1827/15120]

1979/16384 = 1979/2¹⁴, отсюда получаем, что исходное сообщение можно представить двоичным числом 0.00011110111011₂ є [1826/15120, 1827/15120]. Таким образом, мы закодировали сообщение с помощью 14 битов. ML = 2.3 бит/сим.

распакуем код 00011110111011, зная множество символов, из которых состояло исходное сообщение. Итак, 00011110111011₂ = 1979/16384. Результаты расчетов приведены в таблице:

A	B	C	D	Число-код и его интервал	Декодируемый символ	Длина интервала
1	1	1	1	1979/16384 є [0, 1/4]	A	1/4
2	1	1	1	1979/4096 є [2/5, 3/5]	B	1/5
2	2	1	1	1703/4096 є [1/3, 2/3]	B	1/3
2	3	1	1	1013/4096 є [0, 2/7]	A	2/7
3	3	1	1	7091/8192 є [6/8, 7/8]	C	1/8
3	3	2	1	7576/8192 є [8/9, 1]	D	1/9

Реализация кодера

Реализация декодера

Применение

Необходимость применения адаптивного алгоритма возникает в том случае, если вероятностные оценки для символов сообщения неизвестны до начала работы алгоритма:

• сжатие поточных данных

Литература

1. Семенюк В. В. Экономное кодирование дискретной информации. – СПб.: СПбГИТМО (ТУ), 2001 (доступна на [2]).