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

На шаге 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.

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

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

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