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

Определение

Определение:

Арифметическое кодирование (Arithmetic coding) — алгоритм сжатия информации без потерь.

Данный метод (как и алгоритм Хаффмана) является энтропийным т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически символу [math]a[/math] с вероятностью появления [math]p(a)[/math] допустимо ставить в соответствие код длины [math]-log_2(p(a))[/math], следовательно при кодировании Хаффманом это достигается только с вероятностями, равными обратным степеням двойки).

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

Кодирование

Алгоритму передаются текст для кодирования и список частот встречаемости символов.

1. Рассмотрим отрезок [math][0; 1)[/math] на координатной прямой.
2. Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
3. Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Этот отрезок разделим на части, пропорциональные частотам встречаемости символов.
4. Повторим пункт (3) до конца входного потока.
5. Выберем любое число из получившегося отрезка (предпочтительно степень двойки). Это и будет результат арифметического кодирования.

left = 0
right = 1
while !eof
    read(symb)
    newRight = left + (right - left) * segment[symb].right  //segment[symb] — подотрезок отрезка [0; 1), соответствующий символу symb  
    newLeft = left + (right - left) * segment[symb].left
    left = newLeft
    right = newRight
ans = (left + right) / 2

Декодирование

Алгоритм по вещественному числу восстанавливает исходный текст.

1. Выберем на отрезке [math][0; 1)[/math], разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ.
2. Нормируем подотрезок и вещественное число.
3. Повторим п. (1—2) до тех пор, пока не получим ответ (до конца файла).

do
for i = 1 to n
    if code >= segment[i].left && code < segment[i].right
        write(segment[i].character)
        code = (code – segment[i].left) / (segment[i].right – segment[i].left)
        break  
while (segment[i].character != eof)

Замечание

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

Пример работы

Рассмотрим в качестве примера строку [math]abacaba[/math]

Кодирование

Пример работы кодировщика

Символ	Частота появления
[math]a[/math]	[math]0.571429[/math]
[math]b[/math]	[math]0.285714[/math]
[math]c[/math]	[math]0.142857[/math]

Считанный символ	Левая граница отрезка	Правая граница отрезка
	[math]0[/math]	[math]1[/math]
[math]a[/math]	[math]0[/math]	[math]0.571429[/math]
[math]b[/math]	[math]0.326531[/math]	[math]0.489796[/math]
[math]a[/math]	[math]0.326531[/math]	[math]0.419825[/math]
[math]c[/math]	[math]0.406497[/math]	[math]0.419825[/math]
[math]a[/math]	[math]0.406497[/math]	[math]0.414113[/math]
[math]b[/math]	[math]0.410849[/math]	[math]0.413025[/math]
[math]a[/math]	[math]0.410849[/math]	[math]0.412093[/math]

Код: [math]0.411471[/math]

Декодирование

Код: [math]0.411471[/math]

Пример работы декодировщика

Декодируемый символ	Код
[math]a[/math]	[math]0.411471[/math]
[math]b[/math]	[math]0.720074[/math]
[math]a[/math]	[math]0.520259[/math]
[math]c[/math]	[math]0.910454[/math]
[math]a[/math]	[math]0.373178[/math]
[math]b[/math]	[math]0.653061[/math]
[math]a[/math]	[math]0.285714[/math]

Замечание

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