Run-length coding

Run-length coding – простая техника сжатия, заменяющая серию одинаковых подряд идущих символов одной парой (символ, количество). «AAAAA» становится «(A, 5)». Это самая древняя и наименее сложная техника семейства entropy coding, восходящая к телеграфным протоколам 1960-х, но она выживает внутри современных видеокодеков, потому что идеально работает на одном конкретном паттерне: длинных сериях нулей.

Почему это важно: после этапов DCT-преобразования и квантизации большинство коэффициентов в типичном блоке округляется в ноль. Типичный блок 8×8 квантованных коэффициентов может иметь 2–3 значимых значения в верхнем левом углу и 60+ нулей в оставшейся части. Хранить каждый ноль отдельно – огромная трата места. Хранить их как «62 нуля» занимает несколько бит. В сочетании с zig-zag-сканированием (которое раскладывает блок 8×8 в 1D-последовательность, ставя вероятно-ненулевые значения первыми, а длинный нулевой хвост в конце) run-length coding упаковывает типичный блок в поразительно маленькое число бит.

Для продуктовой команды run-length coding – невидимая сантехника, нет ручки для настройки – но он объясняет структурный факт о видеосжатии: более сильная квантизация (более агрессивное сжатие) даёт более длинные серии нулей, которые сжимаются почти до ничего. Поэтому уменьшение bitrate видео вдвое обычно не делит размер файла ровно пополам везде; сжатие не линейно, потому что run-length-этап драматически эффективнее по мере того как квантизация становится грубее. Современные кодеки (AV1, HEVC, VVC) обобщают идею через arithmetic coding, которое работает с произвольными распределениями ещё компактнее, но базовая интуиция – «длинные серии нулей, сжимающиеся практически бесплатно» – та же.