Компрессионная функция

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

Основные характеристики

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

• Коэффициент сжатия — отношение размера исходных данных к размеру сжатых данных. Выражается в разах или процентах.
• Скорость сжатия — время, необходимое для обработки единицы данных.
• Качество восстановления — для сжатия с потерями мера искажения между исходными и восстановленными данными (например, PSNR для изображений).
• Вычислительная сложность — количество операций, требуемых для выполнения функции.

Классификация

Компрессионные функции делятся на два основных типа в зависимости от возможности точного восстановления исходных данных.

Сжатие без потерь

Функции этого типа гарантируют, что после сжатия и последующего восстановления (декомпрессии) исходные данные будут воспроизведены без каких-либо изменений. Они основаны на устранении избыточности в данных. Примеры:

• Кодирование Хаффмана — построение оптимального префиксного кода на основе частот символов.
• Арифметическое кодирование — представление последовательности символов как числа в интервале [0, 1).
• Словарные методы — LZ77, LZ78, LZW (используются в форматах ZIP, GIF, PNG).
• Алгоритм Барроуза — Уилера (BWT) — преобразование, группирующее одинаковые символы, применяется в bzip2.

Сжатие с потерями

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

• Дискретное косинусное преобразование (DCT) — основа JPEG, MPEG, MP3.
• Вейвлет-преобразование — используется в JPEG 2000, аудиокодеках.
• Векторное квантование — разбиение пространства данных на кластеры и замена векторов на их центры.
• Модели восприятия — например, психоакустическая модель в MP3, удаляющая звуки, не слышимые человеком.

Применение

Архивация данных

Компрессионные функции без потерь используются в программах-архиваторах (ZIP, RAR, 7z, Gzip) для уменьшения размера файлов. В операционных системах семейства Windows и Linux встроенные утилиты сжатия (например, NTFS-сжатие, Btrfs) применяют компрессионные функции на уровне файловой системы.

Мультимедиа

В цифровой фотографии, видео и аудио компрессионные функции с потерями являются стандартом. Форматы JPEG, MPEG-4, H.264, H.265, AV1, MP3, AAC, Opus используют сложные компрессионные функции, адаптированные под особенности восприятия человека. Например, в H.264 применяется внутрикадровое и межкадровое сжатие, включающее DCT, квантование и энтропийное кодирование.

Сетевая передача

Компрессионные функции используются в протоколах передачи данных (например, HTTP-сжатие с помощью Gzip или Brotli), в системах видеоконференцсвязи (Zoom, Skype) и в потоковом вещании (YouTube, Twitch). В спутниковой связи и мобильных сетях (4G, 5G) применяются специализированные компрессионные функции для уменьшения объёма трафика.

Криптография

В криптографии компрессионные функции являются ключевым элементом хеш-функций. Например, в семействе SHA-2 (SHA-256, SHA-512) используется компрессионная функция, которая преобразует блок данных фиксированного размера в выходное значение меньшего размера. Такие функции должны быть однонаправленными и устойчивыми к коллизиям. В алгоритмах шифрования с открытым ключом (например, RSA) компрессионные функции применяются для уменьшения размера подписей.

Научные вычисления

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

Интересные факты

• Первая широко известная компрессионная функция для текстов — код Морзе (1838 год), где часто встречающимся буквам (например, «E») присваивались короткие коды.
• Алгоритм LZW, разработанный в 1984 году, был запатентован компанией Unisys, что привело к юридическим спорам и ограничениям на использование в свободном программном обеспечении. Впоследствии патент истёк.
• В формате FLAC (Free Lossless Audio Codec) используется компрессионная функция на основе линейного предсказания, что позволяет сжимать аудио без потерь в 2–3 раза.
• Современные видеокодеки, такие как AV1 и H.266/VVC, используют компрессионные функции с машинным обучением для оптимизации выбора параметров квантования и предсказания.
• В криптовалютах (например, Bitcoin) хеш-функция SHA-256, основанная на компрессионной функции, используется для майнинга и обеспечения целостности блокчейна.

Критика и ограничения

Компрессионные функции с потерями могут приводить к необратимой потере информации, что неприемлемо в некоторых областях (например, в медицине при хранении рентгеновских снимков или в юридических документах). Алгоритмы сжатия без потерь, хотя и сохраняют данные, имеют ограниченный коэффициент сжатия (обычно 2–4 раза для текстов и 1.5–2 раза для изображений). Кроме того, использование запатентованных компрессионных функций (например, в формате GIF до 2004 года) создавало проблемы для свободного распространения программного обеспечения. В последние годы наблюдается тенденция к разработке открытых и свободных от патентов компрессионных функций (Brotli, AV1, Opus).

Источники

• Сэломон Д. «Сжатие данных, изображений и звука». — М.: Техносфера, 2004.
• Ватолин Д., Ратушняк А., Смирнов М., Юкин В. «Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео». — М.: ДИАЛОГ-МИФИ, 2002.
• Sayood K. «Introduction to Data Compression». — 5th ed. — Morgan Kaufmann, 2017.
• RFC 1951 — DEFLATE Compressed Data Format Specification.
• ISO/IEC 10918-1:1994 — JPEG Standard.
• ITU-T H.264 — Advanced Video Coding for Generic Audiovisual Services.