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

Метод Хаффмана является простым и эффективным, однако, как было замечено в § 1.4, он порождает наилучшие коды переменной длины (коды, у которых средняя длина равна энтропии алфавита) только когда вероятности символов алфавита являются степенями числа 2, то есть равны 1/2, 1/4, 1/8 и т.п. Это связано с тем, что метод Хаффмана присваивает каждому символу алфавита код с целым числом битов. Теория информации предсказывает, что при вероятности символа, скажем, 0.4, ему в идеале следует присвоить код длины 1.32 бита, поскольку . А метод Хаффмана присвоит этому символу код длины 1 или 2 бита.

(Перед тем как углубиться в теорию арифметического кодирования, стоит указать две работы [Moffat et al. 98] и [Witter 87], где рассмотрены основные принципы этого метода и приведено множество примеров.)

Арифметическое кодирование решает эту проблему путем присвоения кода всему, обычно, большому передаваемому файлу вместо кодирования отдельных символов. (Входным файлом может быть текст, изображение или данные любого вида.) Алгоритм читает входной файл символ за символом и добавляет биты к сжатому файлу. Чтобы понять метод, полезно представлять себе получающийся код в виде числа из полуинтервала . (Здесь  обозначает числа от  до , включая  и исключая . Конец  замкнут, а конец  открыт.) Таким образом, код «9746509» следует интерпретировать как число «0.9746509» однако часть «0.» не будет включена в передаваемый файл.

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

В первом примере мы рассмотрим три символа  и  с вероятностями ,  и , соответственно. Интервал  делится между этими тремя символами на части пропорционально их вероятностям. Порядок следования этих подынтервалов не существенен. В нашем примере трем символам будут соответствовать подынтервалы ,  и . Чтобы закодировать строку «», мы начинаем с интервала . Первый символ  сокращает этот интервал, отбросив от него 40% в начале и 10% в конце. Результатом будет интервал . Второй символ  сокращает интервал  в той же пропорции до интервала . Третий символ  переводит его в . Наконец, символ  отбрасывает от него 90% в начале, а конечную точку оставляет без изменения. Получается интервал . Окончательным кодом нашего метода может служить любое число из этого промежутка. (Заметим, что подынтервал  получен из  с помощью следующих преобразований его концов:  и ).

На этом примере легко понять следующие шаги алгоритма арифметического кодирования:

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

2. Повторить следующие действия для каждого символа  входного файла.

2.1. Разделить текущий интервал на части пропорционально вероятностям каждого символа.

2.2. Выбрать подынтервал, соответствующий символу , и назначить его новым текущим интервалом.

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

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

Следующий пример будет немного более запутанным. Мы продемонстрируем шаги сжатия для строки «SWISS_MISS». В табл. 1.24 указана информация, приготовленная на предварительном этапе (статистическая модель данных). Пять символов на входе можно упорядочить любым способом. Для каждого символа сначала вычислена его частота, затем найдена вероятность ее появления (частота, деленная на длину строки, 10). Область  делится между символами в любом порядке. Каждый символ получает кусочек или подобласть, равную его вероятности. Таким образом, символ «S» получает интервал  длины 0.5, а символу «I» достается интервал  длины 0.2. Столбец CumFreq (накопленные частоты) будет использоваться алгоритмом декодирования на стр. 71. CumFreq равно сумме частот всех предыдущих символов, например, для «W», .

Табл. 1.24. Частоты и вероятности 5 символов.

Символы и частоты табл. 1.24 записываются в начало выходного файла до битов кода сжатия.

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

После обработки первого символа «S», переменные Low и High равны 0.5 и 1, соответственно. Окончательным сжатым кодом всего входного файла будет число из этого интервала . Для лучшего понимания процесса кодирования хорошо представить себе, что новый интервал  делится между пятью символами нашего алфавита в той же пропорции, что и начальный интервал . Результатом будет пять подынтервалов , , ,  и . После поступления следующего символа «V» выбирается четвертый интервал, который снова делится на пять подынтервалов.

Табл. 1.25. Процесс арифметического кодирования.

С каждым поступившим символом переменные Low и High пересчитываются по правилу:

;

;

где , a HighRange(X) и LowRange(X) обозначают верхний и нижний конец области символа X. В нашем примере второй символ это «W», поэтому новые переменные будут , . Новый интервал  покрывает кусок  подобласти символа «S». В табл. 1.25 приведены все шаги, связанные с кодированием строки «SWISS_MISS». Конечный код - это последнее значение переменной Low, равное 0.71753375, из которого следует взять лишь восемь цифр 71753375 для записи в сжатый файл (другой выбор кода будет обсуждаться позже).

Декодер работает в обратном порядке. Сначала он узнаёт символы алфавита и считывает табл. 1.24. Затем он читает цифру «7» и узнаёт, что весь код имеет вид 0.7... Это число лежит внутри интервала  символа «S». Значит, первый символ был S. Далее декодер удаляет эффект символа S из кода с помощью вычитания нижнего конца интервала S и деления на длину этого интервала, равную 0.5. Результатом будет число 0.4350675, которое говорит декодеру, что второй символ был «W» (поскольку область «W» - ).

Чтобы удалить влияние символа X, декодер делает следующее преобразование над кодом: , где Range обозначает длину интервала символа X. В табл. 1.26 отражен процесс декодирования рассмотренной строки.

Табл. 1.26. Процесс арифметического декодирования.

Следующий пример имеет дело с тремя символами, вероятности которых приведены в табл. 1.27а. Заметим, что эти вероятности сильно отличаются друг от друга. Одна - большая, 0.975, а другие - существенно меньше. Это случай асимметричных вероятностей.

Кодирование строки  выдаёт числа с точностью в 16 знаков, приведенные в табл. 1.28, в которой для каждого символа в двух строках записаны последовательные значения Low и High.

На первый взгляд кажется, что полученный код длиннее исходной строки, однако в § 1.7.3 показано, как правильно определять степень сжатия, достигаемого арифметическим кодированием.

Декодирование этой строки показано в табл. 1.29. Оно обнаруживает особую проблему. После удаления эффекта от  в строке 3 стоит число 0. Ранее мы неявно предполагали, что это означает конец процесса декодирования, но теперь мы знаем, что еще имеется два символа , которые следует декодировать. Это показано в строках 4 и 5 таблицы. Эта проблема всегда возникает, если последний символ входного файла является символом, чья область начинается в нуле. Для того, чтобы различить такой символ и конец входного файла, необходимо ввести один дополнительный символ «eof», обозначающий конец файла (end of file). Этот символ следует добавить в таблицу частот, приписав ему маленькую вероятность (см. табл. 1.27b), и закодировать его в конце входного файла.

Табл. 1.27. (Асимметрические) вероятности трех символов.

Табл. 1.28. Кодирование строки .

Табл. 1.29. Декодирование строки .

В табл. 1.30 и 1.31 показано, как строка  будет закодирована маленькой дробью 0.0000002878086184764172, а потом корректно декодирована. Без символа eof строка из одних  была бы закодирована числом 0.

Обратите внимание на то, что нижнее значение было 0, пока не дошли до eof, а верхнее значение быстро стремится к нулю. Как уже отмечалось, окончательным кодом может служить любое число из промежутка от нижнего до верхнего конечного значения, а не обязательно нижний конец. В примере с  кодом может служить более короткое число 0.0000002878086 (или 0.0000002878087, или даже 0.0000002878088).

Табл. 1.30. Кодирование строки .

(На рис. 1.32 приведена программа для системы Matematica, которая вычисляет табл. 1.28.)

Табл. 1.31. Декодирование строки .

Пример: В табл. 1.33 приведены шаги кодирования строки одинаковых символов . Из-за высокой вероятности символа  переменные Low и High начинаются с сильно различающихся начальных значений и приближаются друг к другу достаточно медленно.

Если размер входного файла известен, тогда можно его кодировать без символа eof. Кодер может начать с записи его размера (в несжатом виде) в заголовок выходного файла. Декодер прочитает этот размер, начнет процесс декомпрессии и остановится после извлечения всех символов. Если декодер читает сжатый файл байт за байтом, то кодер может добавить в конце несколько нулевых битов, чтобы сжатый файл мог быть прочитан блоками по 8 бит.

Рис. 1.32. Программа для вычисления табл. 1.28.

Табл. 1.33. Кодирование строки .