Арифметическое кодирование для сжатия данных

Ключевые слова и синонимы

Энтропийное кодирование; статистическое сжатие данных

Постановка задачи

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

Задача (статистическое сжатие данных)

Дано: последовательность из m событий [math]\displaystyle{ a_1, a_2, ..., a_m }[/math]. i-е событие [math]\displaystyle{ a_i }[/math] берется из набора n различных возможных событий [math]\displaystyle{ e_{i, 1}, e_{i, 2}, ..., e_{i, n} }[/math] с точной оценкой распределения вероятностей [math]\displaystyle{ P_i }[/math] этих событий. Распределения [math]\displaystyle{ P_i }[/math] не обязательно должны быть одинаковыми для каждого события [math]\displaystyle{ a_i }[/math].

Требуется: найти сокращенное кодирование событий, которое может быть декодировано для восстановления точной исходной последовательности событий.

Цель заключается в достижении оптимальной или близкой к оптимальной длины кодирования. Шеннон [10] доказал, что наименьшим возможным ожидаемым количеством бит, необходимым для кодирования i-го события, является энтропия [math]\displaystyle{ P_i }[/math], обозначаемая как [math]\displaystyle{ H(P_i) = \sum_{k = 1}^n -p_{i, k} \; log_2 \; p_{i, k} }[/math] где [math]\displaystyle{ p_{i, k} }[/math] – вероятность того, что в качестве i-го события произойдет [math]\displaystyle{ e_k }[/math]. Для кодирования события, вероятность наступления которого равна p, оптимальный код выдает [math]\displaystyle{ - log_2 \; p }[/math] бит.

Хорошо известные коды Хаффмана [6] являются оптимальными только среди префиксных (или мгновенных) кодов, т. е. таких, в которых кодировка одного события может быть декодирована до начала кодирования следующего события. Коды Ху-Таккера представляют собой префиксные коды, аналогичные кодам Хаффмана, и производятся с помощью аналогичного алгоритма с дополнительным ограничением на сохранение порядка исходных сообщений в коде.

В часто встречающихся ситуациях, когда мгновенные коды не нужны, арифметическое кодирование дает ряд преимуществ, в первую очередь за счет ослабления ограничения, согласно которому длина кода должна быть целым числом: (1) длина кода оптимальна ([math]\displaystyle{ - log_2 \; p }[/math] бит для события с вероятностью p), даже если вероятности не являются целыми степенями [math]\displaystyle{ \frac{1}{2} }[/math]; (2) эффективность кодирования не снижается даже для событий с вероятностью, близкой к 1; (3) можно тривиально работать с распределениями вероятностей, которые меняются от события к событию; (4) соответствия порядка следования входных и выходных сообщений в кодировании Ху-Таккера можно достичь с минимальными дополнительными усилиями.

Рассмотрим для примера входной алфавит из 5 символов. Вероятности символов, коды и длины кодов приведены в табл. 1.

Символ	Вероятность		Хаффман		Ху-Таккер		Арифметическое
[math]\displaystyle{ e_k }[/math]	[math]\displaystyle{ p_k }[/math]	[math]\displaystyle{ - log_2 \; p_k }[/math]	Код	Длина	Код	Длина	Длина
a	0,04	4,644	1111	4	000	3	4,644
b	0,18	2,474	110	3	001	3	2,474
с	0,43	1,218	0	1	01	2	1,218
d	0,15	2,737	1110	4	10	2	2,737
e	0,20	2,322	10	2	11	2	2,322

Таблица 1. Сравнение кодов при кодировании по Хаффману, по Ху-Таккеру, а также арифметическом кодировании для 5-символьного алфавита

Средняя длина кода составляет 2,13 бита на входной символ для кода Хаффмана, 2,22 бита на символ для кода Ху-Таккера и 2,03 бита на символ для арифметического кодирования.

Основные результаты

В теории, при использовании метода арифметического кодирования каждой возможной входной последовательности присваивается одно «кодовое слово». Кодовые слова состоят из полуоткрытых подынтервалов полуоткрытого единичного интервала [0,1) и выражаются путем указания достаточного количества бит, которое позволяет отличить подынтервал, соответствующий актуальной последовательности, от всех остальных возможных подынтервалов. Более короткие коды соответствуют большим подинтервалам и, соответственно, более вероятным входным последовательностям. На практике подынтервал уточняется постепенно, используя вероятности отдельных событий, при этом биты выводятся, как только они становятся известны. Арифметические коды почти всегда дают лучшее сжатие, чем префиксные, но в них отсутствует прямое соответствие между событиями во входной последовательности и битами или группами бит в кодированном выходном файле.

Концептуально алгоритм кодировки файла с помощью арифметического кодирования выглядит следующим образом:

1. «Текущий интервал» [L, H) инициализируется значениями [0, 1).

2. Для каждого события в файле выполняются два шага.

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

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

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

Длина конечного подынтервала, очевидно, равна произведению вероятностей отдельных событий, что и является вероятностью p конкретной общей последовательности событий. Можно показать, что для отличия файла от всех других возможных файлов достаточно [math]\displaystyle{ \lfloor - log_2 \; \rfloor p + 2 }[/math] бит.

Для файлов конечной длины необходимо указать конец файла. При арифметическом кодировании это легко сделать, введя специальное маловероятное событие, которое может быть добавлено во входной поток в любой момент. Это добавляет всего O(log m) бит к кодированной длине m-символьного файла.

На шаге 2 необходимо вычислить только подынтервал, соответствующий событию [math]\displaystyle{ a_i }[/math], которое фактически происходит. Для этого удобно использовать две «кумулятивные» вероятности: кумулятивную вероятность [math]\displaystyle{ P_C = \sum_{k = 1}^{i - 1} p_k }[/math] и следующую кумулятивную вероятность [math]\displaystyle{ P_N = P_C + p_i = \sum_{k = 1}^i p_k }[/math]. Новый подынтервал имеет вид [math]\displaystyle{ [L + P_C(H - L), L + P_N(H - L)) }[/math]. Необходимость хранения и предоставления кумулятивных вероятностей требует от модели сложной структуры данных – например, как у Моффата [7] – особенно когда возможно намного больше двух событий.

Моделирование

Целью моделирования при статистическом сжатии данных является предоставление кодировщику вероятностной информации. Процесс моделирования состоит из структурного и вероятностного компонентов, каждый из которых может быть адаптивным (начиная с нейтральной модели, структура и вероятности постепенно наращиваются в зависимости от встречающихся событий), полуадаптивным (задается начальная модель, описывающая события, которые будут встречаться в данных, затем в процессе кодирования модель модифицируется так, чтобы она описывала только те события, которые еще предстоит закодировать) или статическим (задается начальная модель и используется без модификации в процессе кодирования).

Кроме того, существуют две стратегии оценки вероятности. Первая заключается в индивидуальной оценке вероятности каждого события на основе частоты его встречаемости во входной последовательности. Вторая представляет собой оценку вероятностей в совокупности, предполагая распределение вероятностей определенной формы и оценивая параметры распределения прямо или косвенно. При прямом оценивании можно по данным получить оценку параметра (например, дисперсии); при косвенном [5] можно начать с небольшого числа возможных распределений и вычислить длину кода, который будет получен при каждом из них, а затем выбрать распределение с наименьшей длиной кода. Этот метод является максимально общим и может быть использован даже для распределений из разных семейств, не имеющих общих параметров.

Арифметическое кодирование часто применяется для сжатия текста. Событиями являются символы в текстовом файле, а модель состоит из вероятностей появления символов, рассматриваемых в некотором контексте. В простейшей модели в качестве вероятностей используются суммарные частоты появления символов в файле; это марковская модель нулевого порядка, энтропия которой обозначается [math]\displaystyle{ H_0 }[/math]. Вероятности могут оцениваться адаптивно, начиная с количества, равного 1 для всех символов, и увеличиваться после кодирования каждого символа; также количества символов могут быть заданы до кодирования самого файла и либо изменяться в процессе кодирования (декрементный полуадаптивный код), либо оставаться неизменными (статический код). Во всех случаях длина кода не зависит от порядка следования символов в файле.

Теорема 1. Для всех входных файлов кодовая длина [math]\displaystyle{ L_A }[/math] адаптивного кода с начальными 1-весами равна кодовой длине [math]\displaystyle{ L_{SD} }[/math] полуадаптивного декрементного кода плюс кодовая длина [math]\displaystyle{ L_M }[/math] входной модели, кодируемой в предположении, что все распределения символов равновероятны. Эта кодовая длина меньше [math]\displaystyle{ L_S = mH_0 + L_M }[/math] – кодовой длины статического кода с той же входной моделью. Иными словами, [math]\displaystyle{ L_A = L_{SD} + L_M \lt mH_0 + L_M = L_S }[/math].

Значительно более эффективного сжатия текста можно добиться, используя марковские модели более высокого порядка. Первыми это сделали Клири и Виттен [2] с помощью своего метода PPM, который требует адаптивного моделирования и кодирования вероятностей, близких к 1, и активно использует арифметическое кодирование.

Вопросы реализации

Инкрементный вывод.

Базовая реализация арифметического кодирования, описанная выше, имеет две основные трудности: уменьшение текущего интервала требует использования арифметики высокой точности, а вывод не производится до тех пор, пока не будет прочитан весь файл. Наиболее простым решением обеих этих проблем является вывод каждого старшего бита, как только он становится известен, а затем удвоение длины текущего интервала таким образом, чтобы он отражал только неизвестную часть конечного интервала. Виттен, Нил и Клири [11] добавили остроумный механизм, предотвращающий чрезмерное сокращение текущего интервала, когда конечные точки близки к [math]\displaystyle{ \frac{1}{2} }[/math], но расходятся с [math]\displaystyle{ \frac{1}{2} }[/math]. В этом случае следующий бит вывода еще не известен – но, каким бы он ни был, следующий за ним бит будет иметь противоположное значение; можно просто отслеживать этот факт и расширять текущий интервал симметрично относительно [math]\displaystyle{ \frac{1}{2} }[/math]. Эта процедура может повторяться любое количество раз, так что размер текущего интервала всегда будет строго больше [math]\displaystyle{ \frac{1}{4} }[/math].

До выхода работы [11] другие механизмы инкрементной передачи и арифметики фиксированной точности разрабатывались в течение многих лет рядом исследователей, начиная с Паско [8]. Идея Лэнгдона и других сотрудников IBM [9] о заполнении битами, ограничивающая распространение переносов при сложении, выполняет функцию, аналогичную описанной выше процедуре следования.

Использование целочисленной арифметики.

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

Арифметическое кодирование с ограниченной точностью.

Арифметическое кодирование в том виде, в котором оно обычно реализуется, оказывается медленным из-за умножений (а в некоторых реализациях и делений), необходимых при разбиении текущего интервала в соответствии с вероятностной информацией. Поскольку небольшие ошибки в оценках вероятности приводят к очень незначительному увеличению длины кода, контролируемое введение аппроксимаций в процесс арифметического кодирования позволяет повысить скорость кодирования без существенного снижения производительности сжатия. В разработанном в IBM [9] алгоритме Q-Coder трудоемкие умножения заменяются сложениями и сдвигами, а младшие биты игнорируются.

Ховард и Виттер [4] описали другой подход к приближенному арифметическому кодированию. Дробные биты, характерные для арифметического кодирования, хранятся в кодере как информация о состоянии. Идея, получившая название квазиарифметического кодирования, заключается в уменьшении числа возможных состояний и замене арифметических операций поиском по таблицам, причем таблицы для поиска могут быть вычислены заранее.

Число возможных состояний (после применения процедуры расширения интервала) арифметического кодера, использующего целочисленный интервал [0, N), равно [math]\displaystyle{ 3N^2/16 }[/math]. Очевидным способом уменьшения числа состояний до такого, при котором использование таблиц поиска становится практичным, является уменьшение значения N. Двоичное квазиарифметическое кодирование приводит к незначительному увеличению длины кода по сравнению с чисто арифметическим кодированием.

Теорема 2. В квазиарифметическом кодере, основанном на полном интервале [0, N), использующем корректные оценки вероятностей и исключающем очень большие и очень малые вероятности, количество бит на входное событие, при котором средняя длина кода, полученного квазиарифметическим кодером, превышает длину кода, полученного точным арифметическим кодером, составляет не более [math]\displaystyle{ \frac{4}{ln \; 2} \bigg( log_2 \; \frac{2}{e \; ln \; 2} \bigg) \frac{1}{N} + O \bigg( \frac{1}{N^2} \bigg) \approx \frac{0,497}{N} + O \bigg( \frac{1}{N^2} \bigg), }[/math]

а доля, на которую средняя длина кода, полученная квазиарифметическим кодером, превышает длину кода, полученную точным арифметическим кодером, составляет не более [math]\displaystyle{ \bigg( log_2 \; \frac{2}{e \; ln \; 2} \bigg) \frac{1}{log_2 \; N} + O \bigg( \frac{1}{(log_2 \; N)^2} \bigg) \approx \frac{0,0861}{log_2 \; N} + O \bigg( \frac{1}{(log_2 \; N)^2} \bigg). }[/math]

Алгоритмы общего назначения для параллельного кодирования и декодирования с использованием как хаффмановского, так и квазиарифметического кодирования приведены в [3].

Применение

Арифметическое кодирование может применяться в большинстве приложений, связанных со сжатием данных. Основная польза от него заключается в получении максимального сжатия при сочетании с адаптивной моделью или в случаях, когда вероятность одного события близка к 1. Арифметическое кодирование широко используется при сжатии текстов. Оно также применялось при сжатии изображений в международных стандартах сжатия изображений JPEG и является неотъемлемой частью международных стандартов двухуровневого сжатия изображений JBIG. Многие быстрые реализации арифметического кодирования, особенно для двухсимвольного алфавита, защищены патентами; значительные усилия были потрачены на корректировку базового алгоритма, чтобы не нарушать эти патенты.

Открытые вопросы

Технические проблемы, связанные с арифметическим кодированием, полностью решены. Оставшиеся нерешенными задачи связаны с моделированием – разложением входного набора данных на последовательность событий, причем набор событий, возможных в каждой точке набора данных, должен быть описан распределением вероятностей, пригодным для ввода в кодер. Вопросы моделирования полностью зависят от конкретного применения.

Экспериментальные результаты

Некоторые экспериментальные результаты для корпусов Calgary и Canterbury обобщены в отчете Арнольда и Белла [1].

Наборы данных

В качестве наиболее распространенных наборов данных, пригодных для исследований в области арифметического кодирования, можно назвать Calgary Corpus: (ftp://ftp.cpsc.ucalgary.ca/pub/projects), Canterbury Corpus (http://corpus.canterbury.ac.nz) и Pizza&Chili Corpus (http://pizzachili.dcc.uchile.cl).

Ссылка на код

Ряд реализаций арифметического кодирования доступен на странице «Compression Links Info» по адресу http://www.compression-links.info/ArithmeticCoding. Особенно полезным для понимания арифметического кодирования является код на FTP-сайте ftp://ucalgary.ca, основанный на работе [ ].

См. также

• Усиление степени сжатия текста
• Преобразование Барроуза-Уилера

Литература

1. Arnold, R., Bell, T.: A corpus for the evaluation of lossless compression algorithms. In: Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, March 1997, pp. 201-210

2. Cleary, J.G., Witten, I.H.: Data compression using adaptive coding and partial string matching. IEEE Transactions on Communications, COM-32, pp. 396-402 (1984)

3. Howard, P.G., Vitter, J.S.: Parallel lossless image compression using Huffman and arithmetic coding. In: Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, March 1992, pp. 299-308

4. Howard, P.G., Vitter, J.S.: Practical implementations of arithmetic coding. In: Storer, J.A. (ed.) Images and Text Compression. Kluwer Academic Publishers, Norwell, Massachusetts (1992)

5. Howard, P.G., Vitter, J.S.: Fast and efficient lossless image compression. In: Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, March 1993, pp. 351-360

6. Huffman, D.A.: A method for the construction of minimum redundancy codes. Proceedings of the Institute of Radio Engineers, 40, pp. 1098-1101 (1952)

7. Moffat, A.: An improved data structure for cumulative probability tables. Softw. Prac. Exp. 29,647-659 (1999)

8. Pasco, R.: Source Coding Algorithms for Fast Data Compression, Ph.D. thesis, Stanford University (1976)

9. Pennebaker, W.B., Mitchell, J.L., Langdon, G.G., Arps, R.B.: An overview of the basic principles of the Q-coder adaptive binary arithmetic coder. IBM J. Res. Develop. 32,717-726 (1988)

10. Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27, 398-403 (1948)

11. Witten, I.H., Neal, R.M., Cleary, J.G.: Arithmetic coding for data compression. Commun. ACM 30, 520-540 (1987)