### 6. Арифметический код

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

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

1) Вычислим кумулятивные вероятности ,

2) Разобьем интервал (т.е. интервал [0,1)) на отдельные интервалы так, чтобы каждой букве алфавита источника соответствовал свой интервал, равный ее вероятности (см. рис. 7). Таким образом, символу соответствует интервал , .

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

На рисунке 7 показан процесс кодирования последовательности

Рисунок 7 Схема арифметического кодирования

Для удобства вычислений введем следующие обозначения:
- нижняя граница отрезка, соответствующего i -той букве исходного сообщения;
- верхняя граница этого отрезка;
- длина отрезка , т.е. .
Инициализируем начальные значения этих величин

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

где m - порядковый номер кодируемой буквы в алфавите источника m=1,...,n, а i– номер кодируемого символа в сообщении.

Таким образом, окончательная длина интервала равна произведению вероятностей всех встретившихся символов, а начало интервала зависит от порядка расположения символов в кодируемой последовательности.

Для однозначного декодирования исходной последовательности достаточно взять разрядов двоичной записи любой точки из интервала , где - длина интервала после кодирования символов сообщения источника.

Пример 6.1. Рассмотрим кодирование арифметическим кодом бесконечной последовательности , которая порождается источником с алфавитом с вероятностями , , , .

Вычислим кумулятивные вероятности

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

Для второго символа кодируемого сообщения границы интервала будут следующие:

и т.д.

В результате всех вычислений получаем следующую последовательность интервалов для сообщения

Кодом последовательности будет двоичная запись любой точки из интервала [0.56112, 0.5616), например, 0.56112. Для однозначного декодирования возьмем разрядов, получим код 100011111010.

Таким образом, при арифметическом кодировании сообщение представляется вещественными числами в интервале [0,1). По мере кодирования сообщения отображающий его интервал уменьшается, а количество битов для представления интервала возрастает. Очередные символы сообщения сокращают величину интервала в зависимости от значений их вероятностей. Более вероятные символы делают это в меньшей степени, чем менее вероятные, и следовательно, добавляют меньше битов к результату.

Алгоритм на псевдокоде

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

В начале декодирования известен конечный интервал (например, [0.56112; 0.5616)) или любое число из этого интервала (например, 0.56112). Сразу можно определить, что первым закодированным символом был , т. к. число 0.56112 лежит в интервале [0.5; 0.7), который соответствует символу . Затем в качестве интервала берется [0.5; 0.7) и в нем определяется диапазон, соответствующий числу 0.56112. Это интервал [0.52, 0.6), выделенный символу и т.д. Для декодирования необходимо знать количество закодированных символов и исходные вероятности символов.

Алгоритм на псевдокоде

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

Обозначим

Заметим, что при кодировании и декодировании для экономии памяти достаточно использовать не массивы, а переменные l, r и h.

При реализации арифметического кодирования возникают две проблемы:

- необходима арифметика с плавающей точкой теоретически неограниченной точности;
- результат кодирования становится известен только после окончания входного потока.

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