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

Арифметическое кодирование — это метод сжатия данных без потерь, который представляет последовательность символов в виде одного числа (дроби) из интервала [0, 1). В отличие от методов кодирования с фиксированной длиной кода (например, кода Хаффмана), арифметическое кодирование может кодировать сообщение дробным числом битов, что позволяет достигать энтропии источника (теоретического предела сжатия) с высокой точностью.

Принцип работы

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

Пример кодирования

Пусть алфавит состоит из двух символов: A (вероятность 0,75) и B (вероятность 0,25). Исходный интервал — [0, 1). Символу A соответствует подынтервал [0, 0,75), символу B — [0,75, 1).

Для кодирования последовательности «AAB»:

1. Символ A: интервал сужается до [0, 0,75).
2. Символ A: интервал сужается до [0, 0,5625) (0,75 * 0,75 = 0,5625).
3. Символ B: интервал сужается до [0, 421875, 0,5625) (левая граница: 0,5625 0,75 = 0,421875; правая граница: 0,5625 1 = 0,5625).

Любое число из этого интервала, например 0,5, является кодом сообщения «AAB». Для декодирования необходимо знать вероятности символов и последовательно определять, в какой подынтервал попадает число.

Преимущества и недостатки

Преимущества

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

Недостатки

• Вычислительная сложность: Арифметическое кодирование требует операций с плавающей точкой высокой точности (или целочисленной арифметики с большими числами), что делает его медленнее, чем методы с фиксированной длиной кода, такие как код Хаффмана.
• Чувствительность к ошибкам: Ошибка в одном бите закодированного числа может привести к полной потере данных при декодировании, так как алгоритм основан на точном определении интервала.
• Патентные ограничения: В конце XX — начале XXI века многие реализации арифметического кодирования были защищены патентами, что ограничивало их использование в свободном программном обеспечении. Однако большинство ключевых патентов к настоящему времени истекли.

Применение

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

• Сжатие изображений: Входит в состав стандартов JPEG (в режиме сжатия без потерь) и JPEG 2000.
• Сжатие видео: Используется в кодеках H.264/AVC, H.265/HEVC, AV1 и VP9 для кодирования битового потока (энтропийное кодирование).
• Сжатие аудио: Применяется в некоторых аудиокодеках, например, в MPEG-4 ALS (Audio Lossless Coding).
• Сжатие текста: Используется в архиваторах, таких как PAQ, которые достигают рекордных показателей сжатия на тестовых наборах данных.
• Сжатие данных в научных и инженерных приложениях: Применяется для сжатия результатов численных симуляций, телеметрических данных и других потоков с высокой избыточностью.

Разновидности

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

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

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

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

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

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

Сравнение с кодом Хаффмана

Историческая справка

Идея арифметического кодирования была впервые предложена Питером Элиасом в 1960-х годах, но не была опубликована. Независимо от него, в 1976 году Дж. Риссанен опубликовал первую практическую реализацию алгоритма. В 1987 году Иэн Уиттен, Радфорд Нил и Джон Клири разработали эффективную целочисленную версию, которая стала основой для многих последующих реализаций. В 1990-х годах арифметическое кодирование было включено в стандарты сжатия изображений и видео, что способствовало его широкому распространению.

Интересные факты

• Арифметическое кодирование может сжимать данные настолько эффективно, что для кодирования одного символа может потребоваться менее одного бита. Например, если символ встречается с вероятностью 90%, его код может занимать около 0,15 бита.
• Алгоритм арифметического кодирования лежит в основе многих рекордных результатов на тестовых наборах данных для сжатия без потерь (например, Calgary Corpus, Canterbury Corpus).
• В отличие от кода Хаффмана, который является асимптотически оптимальным, арифметическое кодирование является оптимальным в точном смысле, то есть его длина кода может быть сколь угодно близка к энтропии.

Источники

• Witten, I. H., Neal, R. M., & Cleary, J. G. (1987). Arithmetic coding for data compression. Communications of the ACM, 30(6), 520-540.
• Rissanen, J. (1976). Generalized Kraft inequality and arithmetic coding. IBM Journal of Research and Development, 20(3), 198-203.
• Salomon, D. (2007). Data Compression: The Complete Reference (4th ed.). Springer.
• Sayood, K. (2017). Introduction to Data Compression (5th ed.). Morgan Kaufmann.