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

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

Пример

Пусть имеются два символа, a и b, вероятности кото­рых зависят от положения в трехсимвольном общении:

Здесь Рr(а_i) представляет собой вероятность того, что символ а встретится в i-й позиции сообщения. В данном случае кодируется сообщение «bab».

На рисунке ниже показано арифметическое кодирование этого сообщения. Данному сообщению соответствует конечный интервал [23/30,5/6) = [0,766,0,833). В двоич­ном виде конечный интервал выглядит следующим образом: [0,110001..., 0,110101...). Обратите внимание на то, что все числа, начинающиеся с 0,110001, целиком по­падают в интервал, но существуют некоторые числа, начинающиеся с 0,1100, не попадающие в этот интервал (например, 0,1100001 < 23/30). Поэтому кода 11001 достаточно, чтобы однозначно идентифицировать интервал и, следовательно, однозначно идентифицировать сообщение. В общем случае, чем меньше конечный интервал (соответствующий менее вероятному сообщению), тем больше битов кода требуется для уникальной идентификации интервала.

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

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

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

Эти два шага повторяются до тех пор, пока не будет распаковано все сообще­ние. Существует несколько способов определить, что сообщение распаковано пол­ностью. К исходному сообщению может быть добавлен символ конца сообщения. В этом случае процесс декодирования остановится при обнаружении этого симво­ла. Другой способ состоит в том, чтобы при декодировании на каждом шаге прове­рять, все ли двоичные дроби, начинающиеся с кода, попадают в один интервал, и прекратить декодирование, когда это условие перестанет выполняться.

Процесс декодирования, как и процесс кодирования, иллюстрирует тем же рисунком. Численное значение конечного кода (0,78125 = 0,11001г) обозначается кружком на каждой линии процесса.

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

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