Арифметический код

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

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

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

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

Пусть алфавит состоит из двух символов: A и B, с вероятностями P(A) = 0,6 и P(B) = 0,4. Разобьём интервал [0, 1) на подинтервалы: A: [0; 0,6), B: [0,6; 1,0). Для кодирования последовательности «ABA»:

1. Начало: интервал [0, 1).
2. Символ A: интервал сужается до [0; 0,6).
3. Символ B: внутри интервала [0; 0,6) выделяем подинтервал B (длина 0,4 от 0,6 = 0,24). Новый интервал: [0,6 * 0,6; 0,6) = [0,36; 0,6).
4. Символ A: внутри интервала [0,36; 0,6) выделяем подинтервал A (длина 0,6 от 0,24 = 0,144). Новый интервал: [0,36; 0,36 + 0,144) = [0,36; 0,504).

Итоговый интервал — [0,36; 0,504). Любое число из этого интервала, например 0,4, является кодом сообщения «ABA».

Декодирование

Декодирование выполняется аналогично, но в обратном порядке. Декодер, зная вероятности символов и получив число-код, последовательно определяет, в какой подинтервал текущего интервала попадает это число, и восстанавливает соответствующий символ. Процесс продолжается до тех пор, пока не будет восстановлено всё сообщение или не будет достигнут специальный символ конца сообщения.

Математическая основа

Арифметическое кодирование базируется на теореме Шеннона о кодировании источника. Для последовательности из n символов, где каждый символ i встречается с вероятностью p_i, минимально возможная средняя длина кода на символ равна энтропии H:

\[ H = -\sum_{i} p_i \log_2 p_i \]

Коды Хаффмана, будучи оптимальными для целочисленных кодов, в среднем дают длину, не превышающую H + 1 бит на символ. Арифметическое кодирование позволяет приблизиться к энтропии сколь угодно близко, особенно при кодировании длинных сообщений, так как оно оперирует вещественными числами. Ключевым свойством является то, что код для всего сообщения представляет собой одно число, длина которого в битах примерно равна суммарной энтропии сообщения.

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

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

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

Недостатки

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

Применение

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

• Сжатие изображений: В стандартах JPEG 2000, JPEG-LS, а также в форматах PNG (опционально) и TIFF.
• Сжатие видео: В стандартах H.264/AVC, H.265/HEVC, AV1, VP9 для кодирования битовых потоков.
• Сжатие аудио: В некоторых аудиокодеках, например, в MPEG-4 ALS (Audio Lossless Coding).
• Сжатие текста: В архиваторах, таких как 7-Zip (LZMA), RAR, и в алгоритмах, основанных на контекстном моделировании (PPM, PAQ).
• Сжатие данных общего назначения: В библиотеках bzip2, zlib (опционально), LZMA.

Связь с другими методами

Арифметическое кодирование часто сравнивают с кодированием Хаффмана. Хотя Хаффман проще в реализации и быстрее, арифметическое кодирование обеспечивает более высокую степень сжатия, особенно для источников с сильно неравномерным распределением вероятностей. Существует также двоичное арифметическое кодирование, которое оперирует только двумя символами (0 и 1) и используется в современных видеокодеках (CABAC в H.264/AVC). Оно позволяет эффективно сочетать арифметическое кодирование с контекстным моделированием.

Реализация и практические аспекты

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

Современные реализации, такие как rANS (Asymmetric Numeral Systems), являются более быстрыми аналогами арифметического кодирования, сохраняющими схожую степень сжатия, но с меньшими вычислительными затратами.

Источники

1. Witten, I. H., Neal, R. M., & Cleary, J. G. (1987). Arithmetic coding for data compression. Communications of the ACM, 30(6), 520-540.
2. Salomon, D. (2007). Data Compression: The Complete Reference (4th ed.). Springer.
3. Sayood, K. (2017). Introduction to Data Compression (5th ed.). Morgan Kaufmann.
4. Rissanen, J., & Langdon, G. G. (1979). Arithmetic coding. IBM Journal of Research and Development, 23(2), 149-162.
5. Bell, T. C., Cleary, J. G., & Witten, I. H. (1990). Text Compression. Prentice Hall.