Описание алгоритма

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

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

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

Каждый шаг алгоритма начинается с полуоткрытого интервала [L, H), который инициализируется значением [0,1). Кроме того, используется счетчик следования (follow counter), инициализируемый значением 0:

1. Текущий интервал разбивается на подынтервалы по одному для каждого
возможного символа. Длина каждого подынтервала пропорциональна веро­ятности появления соответствующего символа.

2. Выбирается подынтервал, соответствующий текущему символу.

3. Следующие шаги выполняются в цикле до тех пор, пока не выполнится
условие выхода из цикла:

a. Если новый подынтервал не попадает целиком в один из следующих интервалов: [0, 0,5), [0,25, 0,75) или [0,5,1), — выйти из цикла.

b. Если новый подынтервал попадает в интервал [0,0,5), вывести бит 0, пос­ле которого ноль или более битов 1, соответствующих значению счетчика следования, после чего значение счетчика следования установить на ноль. Удвоить размер подынтервала, линейно расширив [0, 0,5) до [0,1). То есть установить L = 2L и H = 2Н.

c. Если новый подынтервал попадает в интервал [0,5, 1,0), вывести бит 1,
после которого ноль или более битов 0, соответствующих значению счет­чика следования, после чего значение счетчика следования установить на ноль. Удвоить размер подынтервала, линейно расширив [0,5,1) до [0,1). То есть установить L = 2(1 - 0,5) и H= 2(H- 0,5).

d. Если новый подынтервал попадает в интервал [0,25 0,75), увеличить на
единицу значение счетчика следования. Удвоить размер подынтервала,,
линейно расширив [0,25, 0,75) до [0,1). То есть установить L = 2(L - 0,25)
и H=2(H-0,25).

Шаги с 1 по 3 повторяются до тех пор, пока не будет обработано все сообщение. Вот что, по сути, выполняет данный алгоритм. Если новый подынтервал цели­ком попадает в интервал [0,0,5) или [0,5,1,0), алгоритм формирует ведущий бит, указывающий, в какую половину интервала попадает новый подынтервал, после чего интервал удваивается, так что новый интервал отражает только неизвестную часть конечного интервала. Посмотрим, как это работает. Предположим, что на первом шаге формируется подынтервал в верхней половине единичного интервала Таким образом мы узнаем, что конечный подынтервал также должен находиться в верхней половине единичного интервала, и поэтому старший бит конечного кода должен быть равен 1. Когда этот бит становится извест­ным, вторую половину единичною интервала можно проигнорировать, а подын­тервал удвоить для определения следующего бита кода.

Если конечные точки текущего интервала близки к точке 0,5, но находятся по разные стороны от этой точки, тогда расположение следующего результата еще не определено. Однако каким бы он ни был, следующий бит будет иметь противопо­ложное значение. Читатель может сам поэкспериментировать с несколькими зна­чениями, чтобы убедиться, что это так. Поэтому алгоритм следит за следующим битом и симметрично расширяет интервал вокруг значения 0,5.