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

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

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

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

Начальное состояние

Перед началом кодирования и декодирования устанавливается начальная модель вероятностей. Чаще всего используется равномерное распределение: все возможные символы алфавита считаются равновероятными. Для бинарного алфавита (0 и 1) это означает вероятность 0.5 для каждого бита. Для байтового алфавита (0–255) — вероятность 1/256 для каждого символа. В некоторых реализациях начальная модель может быть пустой, и первый символ кодируется с использованием фиксированного начального интервала.

Процесс кодирования

1. Инициализация: Устанавливается текущий интервал [0, 1). Выбирается начальная модель вероятностей (например, счётчики всех символов равны 1).
2. Чтение символа: Считывается следующий символ из входного потока.
3. Разбиение интервала: Текущий интервал делится на подынтервалы, пропорциональные текущим вероятностям символов. Вероятность каждого символа вычисляется как отношение его счётчика к сумме всех счётчиков.
4. Выбор подынтервала: Текущий интервал сужается до подынтервала, соответствующего считанному символу.
5. Обновление модели: Счётчик для считанного символа увеличивается на 1. Это изменяет вероятности для всех последующих символов.
6. Повторение: Шаги 2–5 повторяются для каждого следующего символа входного потока.
7. Завершение: После обработки всех символов выбирается любое число из финального интервала, которое и является выходным кодом. Обычно это число записывается в двоичном виде с фиксированной точностью.

Процесс декодирования

Декодирование выполняется симметрично, используя ту же самую адаптивную модель:

1. Инициализация: Устанавливается текущий интервал [0, 1). Инициализируется модель вероятностей (идентично начальной модели кодера).
2. Чтение кода: Считывается закодированное число (или его начальная часть).
3. Определение символа: Определяется, в какой подынтервал текущего интервала попадает считанное число. Этот подынтервал соответствует определённому символу.
4. Вывод символа: Определённый символ выводится в выходной поток.
5. Обновление модели: Счётчик для выведенного символа увеличивается на 1 (точно так же, как это делал кодер).
6. Сужение интервала: Текущий интервал сужается до подынтервала, соответствующего выведенному символу.
7. Повторение: Шаги 2–6 повторяются до тех пор, пока не будет восстановлен весь исходный поток данных.

Ключевой момент: кодер и декодер всегда синхронизированы, так как они обновляют модель на основе одних и тех же данных (кодер — на основе закодированных символов, декодер — на основе декодированных).

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

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

• Отсутствие необходимости в предварительном анализе: Не требуется двухпроходное сканирование данных (один проход для сбора статистики, второй — для кодирования). Это сокращает время обработки и объём памяти, особенно для больших файлов.
• Адаптация к локальным изменениям: Модель быстро подстраивается под изменение характера данных. Например, если в начале файла преобладают текстовые символы, а затем идут числовые данные, модель автоматически скорректирует вероятности.
• Компактность: Нет необходимости хранить таблицу вероятностей отдельно от сжатых данных, что уменьшает итоговый размер архива.
• Потоковая обработка: Алгоритм может работать в режиме реального времени, обрабатывая данные по мере их поступления (например, при передаче по сети).

Недостатки

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

Применение

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

• Сжатие изображений: Формат JPEG 2000 использует адаптивное арифметическое кодирование (MQ-кодер) на заключительном этапе сжатия.
• Сжатие видео: Стандарты H.264/AVC и H.265/HEVC (High Efficiency Video Coding) применяют адаптивное арифметическое кодирование (CABAC — Context-Adaptive Binary Arithmetic Coding) для кодирования битовых потоков.
• Сжатие аудио: Некоторые кодеки, такие как FLAC (Free Lossless Audio Codec), используют адаптивное арифметическое кодирование для сжатия остаточного сигнала.
• Общее сжатие данных: Алгоритмы семейства PAQ (например, PAQ8, ZPAQ), которые являются одними из самых эффективных в мире по степени сжатия, основаны на адаптивном арифметическом кодировании в сочетании с мощными моделями предсказания.
• Архиваторы: Некоторые архиваторы, такие как 7-Zip, используют арифметическое кодирование (в том числе адаптивные его варианты) как один из доступных методов сжатия.

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

Адаптивное арифметическое кодирование часто комбинируется с методами контекстного моделирования (Context Modeling). В этом случае вероятности символов зависят не только от их частоты, но и от контекста — предыдущих символов. Например, в CABAC (H.264/HEVC) используется несколько сотен контекстов, каждый из которых имеет свою адаптивную модель вероятностей. Это позволяет достичь высокой степени сжатия за счёт учёта статистических зависимостей между символами.

Реализация

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

Источники

• Witten, I. H., Neal, R. M., & Cleary, J. G. (1987). Arithmetic coding for data compression. Communications of the ACM, 30(6), 520-540.
• Sayood, K. (2017). Introduction to Data Compression (5th ed.). Morgan Kaufmann.
• Salomon, D. (2007). Data Compression: The Complete Reference (4th ed.). Springer.
• Marpe, D., Schwarz, H., & Wiegand, T. (2003). Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard. IEEE Transactions on Circuits and Systems for Video Technology, 13(7), 620-636.