Arithmetic coding

Arithmetic coding – близкая к оптимальной lossless-техника сжатия, превращающая поток символов в последовательность бит настолько короткую, насколько позволяет нижняя энтропийная граница. В отличие от более старых техник вроде Huffman, присваивающих каждому символу целое число бит, arithmetic coding может закодировать один символ дробным числом бит – то есть не тратит место на округление вверх до следующего бита. На миллионах символов типичного видеокадра экономия складывается в несколько процентов.

Интуиция: arithmetic coding представляет всё входное сообщение как одно дробное число между 0 и 1, где каждый символ дальше сужает диапазон. Частые символы почти не меняют диапазон (тратят почти нет бит); редкие – сужают резко (тратят много бит). Финальное число выписывается ровно тем числом бинарных разрядов, которое однозначно идентифицирует выбранный диапазон. Вместе с context-adaptive оценками вероятностей, обновляемыми по мере прохода энкодера по кадру, получается кодирование, адаптирующееся к локальной статистике в реальном времени.

Для продуктовой команды arithmetic coding – математический фундамент CABAC (H.264, HEVC) и варианта под названием daala_bool (AV1). Он вносит примерно 10–15 % в эффективность сжатия любого современного кодека. Цена – вычислительная: arithmetic coding по природе последовательный (каждый символ зависит от текущего состояния), поэтому плохо параллелится и часто становится бутылочным горлышком декодеров с малой мощностью. Executive summary: arithmetic coding – причина, по которой то же видео при том же визуальном качестве заметно меньше в H.264 Main, чем в Baseline; разница вся в entropy-кодере.