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

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

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

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

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

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

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

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

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

'''Теорема 1 Для всех входных файлов кодовая длина LA адаптивного кода с начальными 1-весами равна кодовой длине LSD полуадаптивного декрементирующего кода плюс кодовая длина LM входной модели, кодируемой в предположении, что все распределения символов равновероятны. Эта кодовая длина меньше LS = mH0 + LM – кодовой длины статического кода с той же входной моделью. Иными словами, LA = LSD + LM < mH0 + LM = LS.'''

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

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

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

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

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

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

'''а доля, на которую средняя длина кода, полученная квазиарифметическим кодером, превышает длину кода, полученную точным арифметическим кодером, не превышает'''

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