Урок #2. Алгоритмы сжатия информации

Введение

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

Представьте себе средний смартфон. Если бы мы хранили фотографии в формате несжатого BMP, видео в чистом RAW-формате, а музыку как WAV-файлы без кодирования, встроенной памяти в 256 гигабайт хватило бы ровно на один поход за продуктами с включённой камерой. Стриминговые сервисы вроде «Кинопоиска» или музыки во «ВКонтакте» были бы невозможны из-за колоссальной нагрузки на сети передачи данных. Сжатие — это невидимый фундамент интернета, мобильной связи и хранения больших данных.

Часть 1. Почему данные можно сжать? Энтропия и избыточность

Любой файл на вашем компьютере — будь то текст этой лекции, фотография кота или песня любимого исполнителя — представляет собой последовательность нулей и единиц, битов. Казалось бы, эта последовательность случайна, но это не так. Реальные данные почти всегда содержат избыточность. Именно её удаление и есть суть сжатия.

Существует три основных вида избыточности:

1. Пространственная (статическая). Повторение одних и тех же элементарных фрагментов внутри данных. Классический пример — текст. В любом языке одни буквы встречаются чаще других. В русском языке буква «о» встречается гораздо чаще, чем «ф». Сочетание «_пробел_и» невероятно популярно. Зачем тратить одинаковое количество бит на хранение редкой «ф» и частой «о», если можно закодировать их по-разному?
2. Спектральная (частотная). Характерна для аудио и изображений. Человеческое ухо плохо слышит очень высокие частоты или звуки, которые маскируются более громкими соседними частотами. Глаз человека слабо различает оттенки цвета при слабом освещении, зато отлично видит перепады яркости. Эти несовершенства наших органов чувств позволяют выбрасывать часть информации незаметно для восприятия.
3. Временная (психоизуальная). Типична для видео. В потоке из 30 кадров в секунду два соседних кадра обычно почти идентичны. Нет никакого смысла хранить полную информацию о пикселях каждого кадра, если 95 % картинки осталось неизменным.

С точки зрения математики теорию сжатия описывает понятие энтропии Шеннона, введённое Клодом Шенноном в 1948 году. Энтропия — это мера неопределённости или непредсказуемости сообщения. Чем выше хаос в данных, тем больше их энтропия и тем сложнее их сжать. Идеально случайные данные (например, зашифрованный поток) имеют максимальную энтропию, и сжать их невозможно. Напротив, предсказуемые данные (длинная строка из миллиона нулей) имеют низкую энтропию и сжимаются практически до нуля. Любой алгоритм сжатия стремится приблизить среднюю длину кода к теоретическому пределу — энтропии источника.

Часть 2. Две большие ветви: Lossless и Lossy

Все алгоритмы делятся на две принципиально разные категории.

1. Сжатие без потерь (Lossless Compression)

После распаковки файл байт-в-байт совпадает с оригиналом. Этот метод обязателен там, где любая ошибка критична: исполняемые программы (.exe, .apk), таблицы Excel, программный код, текстовые документы, медицинские снимки МРТ или рентгена. Архиваторы ZIP, RAR, 7z работают именно так.

Как это работает? Главный принцип здесь — замена длинных часто встречающихся последовательностей короткими кодами.

• Алгоритм Хаффмана (1952 год). Строится бинарное дерево. Самым частым символам присваиваются самые короткие пути (коды). Например, пробелу — 01, букве «е» — 11, а редкому твёрдому знаку — длинная последовательность вроде 1011001. Файл становится короче, потому что средняя длина кода уменьшается.
• Алгоритм LZW (Лемпеля-Зива-Велча, 1984 год). Он лежит в основе формата GIF и старого стандарта TIFF. Алгоритм не знает заранее статистики текста. Вместо этого он читает поток символов и динамически строит таблицу словаря. Как только он встречает уже известную ему последовательность, он заменяет её коротким индексом в таблице.
• Кодирование длин серий (RLE). Самый простой метод. Последовательность WWWWWWBBBBBBBBLLLLLLL превращается в запись 7W6B6L. Прекрасно работает на простых изображениях (скриншоты интерфейсов, иконки), но бесполезен на фотографиях природы, где каждый следующий пиксель отличается от предыдущего.

2. Сжатие с потерями (Lossy Compression)

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

Как это работает? Здесь правит бал психофизиология. Алгоритм анализирует данные и удаляет то, что человек скорее всего не заметит.

• Дискретное косинусное преобразование (DCT). Сердце форматов JPEG (изображения) и MP3 (звук). Изображение разбивается на блоки 8×8 пикселей. Каждый блок переводится из цветового пространства в пространство частот. Алгоритм квантования делит эти коэффициенты на определённые числа и округляет их. Высокочастотные шумы превращаются в нули и выбрасываются.
• Психоакустическая модель. Используется в MP3, AAC, Ogg Vorbis. Алгоритм постоянно анализирует звуковую волну. Если звучит громкий звук, человеческое ухо на несколько миллисекунд перестаёт слышать тихие звуки в близком диапазоне частот. Алгоритм находит такие «временно оглохшие» зоны спектра и просто вырезает оттуда все данные.
• Ключевые кадры (I-frames) и дельта-кадры (P-frames) в видеокодеках H.264 (AVC), H.265 (HEVC) и AV1. Раз в секунду сохраняется полный ключевой кадр. Все последующие кадры хранят только разницу между собой и предыдущим состоянием. Если фон неподвижен, передаётся буквально пара килобайт инструкций типа «сместить этот прямоугольник с лицом на 2 пикселя вправо».

Часть 3. Современные стандарты и практическое применение

Теория мертва без практики. Давайте посмотрим, какие алгоритмы окружают нас сегодня:

• Текст и веб-трафик: Gzip (на базе Deflate) и Brotli. Когда ваш браузер запрашивает главную страницу Яндекса или новостного сайта, сервер не отправляет чистый HTML-код весом в сотни килобайт. Веб-сервер налету сжимает его через Gzip или более современный Brotli, экономя до 70–80 % трафика и ускоряя загрузку страницы.
• Изображения нового поколения: WebP, AVIF. Формат JPEG безнадёжно устарел. WebP даёт файлы на 25–35 % легче при том же визуальном качестве. Новый формат AVIF (основанный на технологии обработки видео AV1) превосходит даже его, обеспечивая кинематографическое качество HDR-изображений при минимальном весе.
• Видео: HEVC (H.265), AV1, VVC (H.266). Переход с HD (720p) на Full HD увеличил объём данных вдвое. Переход на 4K — ещё в четыре раза. Без современных кодеков стриминг 4K-видео был бы невозможен для домашнего интернета. Кодек AV1 бесплатен от патентных отчислений, поддерживается всеми крупными браузерами и YouTube.
• Аудио: Opus. Золотой стандарт современной интернет-связи. Этот алгоритм используется в Telegram, Discord, Zoom и Google Meet. Уникальность Opus в адаптивности: он объединяет технологию речи (SILK) и технологию музыки (CELT). При плохом интернете он мгновенно переключается в режим чистой передачи голоса, отсекая лишние шумы, а при хорошем канале выдаёт прозрачный широкополосный стереозвук.
• Архивация общего назначения: Zstandard (Zstd). Сегодня это де-факто стандарт индустрии. Он сочетает скорость старых лёгких алгоритмов со степенью сжатия тяжёлых архиваторов. Базы данных PostgreSQL резервируют копии через Zstd, ядра Linux распространяются в нём, игровые платформы используют его для упаковки ассетов.

Заключение

Мы прошли путь от простого подсчёта повторяющихся букв до нейросетей, генерирующих изображения. Важно понимать ключевое различие: алгоритмы без потерь борются со статистической структурой данных, они ищут идеальный код. Алгоритмы с потерями борются с особенностями нашего восприятия, они ищут иллюзию идеального качества.

Развитие алгоритмов сжатия напрямую связано с развитием вычислительной техники. Раньше сложные преобразования требовали мощных процессоров. Сегодня аппаратное декодирование AV1 или VVC встроено в бюджетные смартфоны и телевизоры. Более того, на горизонте маячит новая эпоха — использование искусственного интеллекта. Нейросетевые кодеки (кодеки нового поколения, NNC) начинают применяться для сверхэффективного сжатия видео и улучшения масштабирования старых фильмов.