Сжатие информации¶

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

¶Основные принципы

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

Алгоритмы сжатия делятся на две большие категории:

• Сжатие без потерь — гарантирует побитовую точность восстановления исходных данных. Используется для текстов, исполняемых файлов, баз данных и медицинских изображений.
• Сжатие с потерями — допускает необратимые изменения, незначительно влияющие на восприятие (зрение, слух). Применяется для фотографий, видео и аудио, где допустима потеря части деталей ради высокой степени сжатия.

¶Методы сжатия без потерь

¶Энтропийное кодирование

Присваивает более короткие коды часто встречающимся символам. Основные методы:

• Код Хаффмана (1952) — построение префиксного дерева по частотам символов; оптимален для статических алфавитов.
• Арифметическое кодирование — кодирует весь поток в одно число с плавающей точкой, достигая эффективности, близкой к пределу энтропии.
• Код Шеннона — Фано — ранний метод, предшественник кода Хаффмана.

¶Словарные методы

Заменяют повторяющиеся последовательности ссылками на ранее встреченные фрагменты:

• LZ77 / LZ78 (1977–1978) — основа семейства LZ; используют скользящее окно и словарь.
• DEFLATE — комбинация LZ77 и кода Хаффмана; используется в форматах ZIP, gzip, PNG.
• LZW — модификация LZ78, применялась в GIF и TIFF.

¶Контекстное моделирование

Предсказывает вероятность следующего символа на основе контекста. Метод PPM (prediction by partial matching) и алгоритм BWT (Burrows-Wheeler transform, 1994), применяемый в bzip2, достигают высокой степени сжатия текстов.

¶Методы сжатия с потерями

Эти алгоритмы ориентированы на психофизиологические особенности восприятия человека.

¶Изображения

• JPEG (1992) — использует дискретное косинусное преобразование (ДКП) блоков 8×8, квантование и энтропийное кодирование. Степень сжатия регулируется параметром качества.
• JPEG 2000 (2000) — основан на вейвлет-преобразовании, обеспечивает лучшее качество при низких битрейтах и поддержку прогрессивной передачи.
• WebP (2010) — формат Google, сочетающий методы с потерями и без потерь.

¶Аудио

• MP3 (1993) — использует психоакустическую модель, отбрасывающую звуки, неразличимые для слуха.
• AAC (1997) — более совершенный стандарт, применяется в iTunes, YouTube и цифровом радио.
• Opus (2012) — современный кодек для речи и музыки, используемый в VoIP и веб-браузерах.

¶Видео

• H.264/AVC (2003) — стандарт, основанный на блочном кодировании с компенсацией движения; доминирует в интернет-вещании и Blu-ray.
• H.265/HEVC (2013) — обеспечивает вдвое лучшее сжатие при том же качестве, но требует более мощных процессоров.
• AV1 (2018) — открытый кодек, разработанный альянсом AOMedia для снижения зависимости от патентованных решений.

¶Применение

Сжатие информации повсеместно используется:

• Архивация — форматы ZIP, RAR, 7z для хранения и передачи файлов.
• Сети и интернет — протоколы HTTP/2 и HTTP/3 поддерживают сжатие заголовков (HPACK, QPACK); сжатие контента (gzip, Brotli) снижает трафик веб-сайтов.
• Мультимедиа — цифровое телевидение (DVB), видеоконференции (Zoom, Skype), стриминговые сервисы (Netflix, YouTube) невозможны без видеокодеков.
• Базы данных — сжатие строк и столбцов в СУБД (например, PostgreSQL, Oracle) уменьшает объём хранилища и ускоряет чтение.
• Научные данные — сжатие телеметрии, геномных последовательностей и результатов моделирования.

¶Оценка эффективности

Эффективность сжатия характеризуется коэффициентом сжатия — отношением размера исходных данных к размеру сжатых. Для текстов типичны коэффициенты 2–5, для фотографий — 10–20, для видео — 50–200. Важными метриками также являются скорость работы алгоритма и требуемый объём памяти. Для сжатия с потерями применяются объективные метрики искажения (PSNR, SSIM) и субъективные оценки качества.

¶Ограничения и перспективы

Теоретический предел сжатия без потерь определяется энтропией источника и не может быть преодолён. Для сжатия с потерями предел зависит от допустимого уровня искажений. Современные исследования сосредоточены на использовании нейронных сетей: алгоритмы на основе глубокого обучения (например, компрессионные автоэнкодеры) демонстрируют результаты, превосходящие традиционные кодеки, но требуют значительных вычислительных ресурсов.