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

Метод Хаффмана является простым и эффективным, но порождает наилучшие коды переменной длины только тогда, когда вероятности символов алфавита являются степенями числа 2. Это связано с тем, что метод Хаффмана присваивает каждому символу алфавита код с целым числом битов. Например, при вероятности символа 0,4 ему в идеальном случае соответствует код с длиной, равной энтропии, то есть 1,32. Метод Хаффмана позволяет лишь получить код длиной 1 или 2 бита.

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

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

В первом примере рассмотрим три символа a₁, a₂, a₃ с вероятностями p₁ = 0,4, p₂ = 0,5, p₃ = 0,1 соответственно. Интервал [0, 1) делится между этими тремя символами на части пропорционально их вероятностям. Порядок следования этих подынтервалов не существенен. В нашем примере трём символам соответствуют подынтервалы [0, 0,4), [0,4, 0,9) и [0,9, 1). Для того, чтобы закодировать строку a₂ a₂ a₂ a₃ начинаем рассмотрение с интервала [0, 1). Первый символ сокращает интервал, отбросив от него 40% в начале и 10% в конце. Результатом будет интервал [0,4, 0,9). Второй символ a₂ сокращает интервал [0,4, 0,9) в той же пропорции до интервала [0,6, 0,865). Третий символ a₂ приводит к интервалу [0,7, 0,825). Наконец, символ a₃ отбрасывает от интервала 90% в начале, оставляя конечную точку без изменений. Получается интервал [0,8125, 0,825). Окончательным кодом символа может служить любое число, принадлежащее этому интервалу.

Алгоритм арифметического сжатия включает в себя следующие шаги.

1. Задать «текущий интервал» [0, 1).

2. Повторить для каждого символа s следующие действия: 1) разделить текущий интервал на части пропорционально вероятностям каждого символа; 2) выбрать подынтервал, соответствующий символу s, и назначить его новым текущим интервалом.

3. Когда весь входной файл будет обработан, выходом алгоритма объявляется любая точка, которая однозначно определяет текущий интервал (то есть любая точка внутри этого интервала).

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

Рассмотрим арифметическое сжатие строки ­­­­­­­SWISS_MISS. В таблице 12.2 приведена информация, подготовленная на предварительном этапе (статистическая модель данных). Пять символов на входе можно упорядочить любым способом. Для каждого символа сначала вычислена частота, а потом – вероятность его появления. Область [0, 1) делится между символами в любом порядке. Каждый символ получает подынтервал, длина которого пропорциональна вероятности появления символа. Символы и частоты таблицы 12.2 записываются в начало выходного файла до результатов сжатия.

Таблица 12.2

Процесс кодирования начинается с инциализации двух переменных Low и High значениями 0 и 1 соответственно. Они определяют интервал [Low, High). По мере поступления и обработки символов значения переменных Low и High начинают сближаться, уменьшая длину интервала. С каждым поступившим символом переменные Low и High пересчитываются по правилу:

Range = OldHigh­ – OldLow,

NewHigh = OldLow + Range*HighRange(x),

NewLow = OldLow + Range*LowRange(x),

где HighRange(x) и LowRange(x) – верхняя и нижняя границы интервала символа x. Процесс кодирования показан в таблице 12.3. Результирующий код – последнее значение переменной Low, равное 0,71753375, из которого последние восемь цифр (71753375) записываются в сжатый файл.

Таблица 12.3

Декодер работает в обратном порядке. Сначала считывается статистическая модель, содержащаяся в таблице 12.2. Затем считывается цифра 7, соответствующая коду 0,7. Это число лежит внутри интервала [0,5, 1), поэтому первым декодированным символом является символ S. Далее удаляется эффект символа S путём вычитания нижнего конца интервала S из текущего значения кода и деления разности на длину этого интервала. Результатом будет число 0,4350675, которое говорит о том, что второй декодируемый символ – W (интервал символа W – [0,4, 0,5)). Процесс продолжается до тех пор, пока текущее значение кода не станет равным 0 (табл. 12.4).

Таблица 12.4