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

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

Математическая механика процесса основана на рекурсивном сужении текущего числового интервала. Исходный интервал [0, 1) делится на подынтервалы, длина каждого из которых пропорциональна вероятности появления соответствующего символа в текущей модели источника. Для кодирования очередного символа выбирается подынтервал, соответствующий этому символу, который становится новым текущим интервалом. Процесс повторяется для каждого символа сообщения. По завершению кодирования для однозначного декодирования достаточно передать любое число из итогового интервала (обычно его нижнюю границу или середину) и длину сообщения. Декодер, используя ту же вероятностную модель, выполняет обратную операцию, последовательно определяя, какому символу соответствует полученное число.

В современной индустрии арифметическое кодирование является ключевым компонентом многих стандартов сжатия. Оно используется в алгоритмах сжатия изображений (JPEG, JPEG2000), видео (H.264/AVC, HEVC) и данных (7-Zip, ZPAQ). Его главное преимущество — способность эффективно работать с контекстно-зависимыми вероятностными моделями, что позволяет достигать высокой степени сжатия для источников с избыточностью, такой как естественный язык или специфические форматы данных. В области искусственного интеллекта, как отмечено в исследовании arXiv:2604.02343v1, арифметическое кодирование на основе крупных языковых моделей (LLM) демонстрирует значительный прогресс. Использование адаптеров LoRA, дообученных на конкретной предметной области, позволяет улучшить сжатие в 2 раза по сравнению с базовой LLM, поскольку модель точнее оценивает условные вероятности символов в специализированных текстах.

Основное ограничение классического арифметического кодирования — вычислительная сложность, связанная с необходимостью работы с высокой точностью вещественной арифметики и актуальным обновлением вероятностной модели. Это может замедлять процесс кодирования и декодирования. Современные исследования, включая упомянутую работу, смещают фокус на преодоление «границы сжатие-вычисления»: достижение большего сжатия за счет увеличения вычислительных ресурсов, например, с использованием более мощных LLM для предсказания вероятностей. Перспективным направлением является интеграция арифметического кодирования в гибридные и интерактивные протоколы сжатия, такие как «сжатие с вопросами» (QA), где для достижения экстремальных коэффициентов сжатия (порядка 0.0006) взаимодействие между моделями заменяет прямую передачу данных. Это открывает путь к эффективной дистилляции знаний и сжатию сложных семантических данных.