О точности вычислений

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

Арифметическое кодирование может быть использовано, когда степень сжатия важнее, чем затраты на сжатие информации.

   Для того чтобы избежать этой ситуации, немного изменим алгоритм.    Если две старшие цифры границ не совпадают, то, если они отличаются на единицу, проверим следующие по значимости цифры границ. Если они равны 0 у верхней границы и 9 у нижней, значит алгоритм на пути к зацикливанию и надо принимать меры.    Сделаем следующее: удалим вторые по значимости цифры границ и остальные менее значимые сдвинем влево по описанным правилам. Старшие цифры останутся на месте. Затем увеличим специальный счетчик, чтобы запомнить то, что мы выбросили цифры. Эти действия могут выглядеть, например, так:

	До	После
Верхняя граница	30585	35859
Нижняя граница	29786	27860
Счетчик	0	1

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

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

   На практике число, представляющее собой код сообщения, может занимать сотни килобайтов памяти, и поэтому "идеальный" алгоритм арифметического декодирования, описанный ранее, работать не будет.    Как и кодер, арифметический декодер может работать на 16 или 32-битовых целочисленных регистрах. Он использует три регистра. Первые два в точности такие, как у кодера, третий - регистр кода - содержит очередные биты декодируемого сообщения. Значение в регистре кода всегда находится между значениями верхней и нижней границ.    Верхняя и нижняя границы на каждом шаге имеют абсолютно те же значения, которые они имели при кодировании, и обновляются одинаковым образом. Так же осуществляется проверка на зацикливание. Выполняя эту проверку, декодер определяет, когда необходимо помещать очередную цифру из входного потока в регистр кода. На основании содержимого регистров кода и границ декодер принимает решение о раскодируемом символе.    Перед началом декодирования регистры верхней и нижней границ инициализируются так же, как и перед началом кодирования.

ВерхняяГраница: 99999 (99999999...до бесконечности) НижняяГраница : 00000 (00000000...до бесконечности)

Регистр кода заполняется первыми цифрами кода декодируемого сообщения (в нашем примере код сообщения равен 0.25721677520):

РегистрКода : 25721

В "идеальном" алгоритме, описанном ранее, возможно определить текущий символ для декодирова-ния, просто просматривая таблицу интервалов вероятностей символов в данном сообщении. В целочисленной реализации интервал вероятностей определяется не как диапазон от 0.0 до 1.0, а как разница между текущими значениями верхней и нижней границ.    Целочисленная реализация арифметического де-кодирования использует четыре шага для декодирования каждого символа.

 На первом шаге определяется текущий интервал вероятностей.

 На втором шаге текущее значение регистра кода масштабируется на основе значений текущего интервала вероятностей, регистров кода и границ.

 На третьем шаге на основе масштабированного значения регистра кода определяется очередной символ восстановленного сообщения.

 На четвертом шаге код декодированного символа удаляется из входного потока.