Компрессия данных

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

История

Первые теоретические основы компрессии были заложены в 1940-х годах. В 1948 году Клод Шеннон опубликовал работу «Математическая теория связи», где ввёл понятие энтропии как меры информационной неопределённости и определил теоретический предел сжатия без потерь. В 1952 году Дэвид Хаффман разработал алгоритм оптимального префиксного кодирования, который до сих пор широко используется.

Практическое развитие сжатия началось с ростом компьютерной техники. В 1970-х годах появились алгоритмы Лемпеля — Зива (LZ77, LZ78), ставшие основой для форматов ZIP, GIF и PNG. В 1980-х годах началось активное развитие сжатия с потерями для аудио и видео: стандарт JPEG (1992) для изображений, MPEG (1993) и MP3 (1993) для видео и звука. В 1990-е годы алгоритмы сжатия стали неотъемлемой частью операционных систем и интернета.

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

По критерию обратимости компрессия делится на два основных класса:

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

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

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

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

Основные алгоритмы и методы

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

Методы, основанные на статистических свойствах данных. Чем чаще встречается символ, тем более коротким кодом он кодируется.

• Код Хаффмана — строит оптимальное префиксное дерево на основе частот символов.
• Арифметическое кодирование — кодирует целое сообщение в одно число из интервала [0,1), что даёт более высокую эффективность, чем код Хаффмана, особенно для неравномерных распределений.
• Кодирование длин серий (RLE) — заменяет последовательности одинаковых символов на пару «символ — количество повторений». Эффективно для изображений с большими однотонными областями.

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

Основаны на поиске повторяющихся фрагментов в данных и замене их ссылками на предыдущие вхождения.

• LZ77 — использует скользящее окно, в котором ищутся совпадения с текущей позицией. На его основе построены форматы ZIP, gzip, PNG.
• LZ78 — строит словарь из встречающихся фраз. На его основе построен формат GIF.
• LZW (Lempel-Ziv-Welch) — модификация LZ78, использовавшаяся в ранних версиях GIF и в формате TIFF.

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

Для изображений

• JPEG — основан на дискретном косинусном преобразовании (DCT). Изображение разбивается на блоки 8×8 пикселей, преобразуется в частотную область, затем высокочастотные составляющие квантуются (грубо округляются) и кодируются энтропийно. Коэффициент сжатия регулируется параметром качества.
• JPEG 2000 — использует вейвлет-преобразование, обеспечивает лучшее качество при низких битрейтах и поддержку прогрессивной загрузки.
• WebP — разработан компанией Google, использует как DCT, так и вейвлет-подобное предсказание, обеспечивает на 25–35% меньший размер файла по сравнению с JPEG при том же качестве.

Для аудио

• MP3 — использует психоакустическую модель, отбрасывающую звуки, неразличимые для человеческого уха, и применяет модифицированное дискретное косинусное преобразование (MDCT).
• AAC (Advanced Audio Coding) — более совершенный стандарт, обеспечивающий лучшее качество при меньшем битрейте, чем MP3.
• FLAC — сжатие без потерь для аудио, использует линейное предсказание и кодирование остатков.

Для видео

• H.264/AVC — наиболее распространённый стандарт (MPEG-4 Part 10), использует внутрикадровое и межкадровое предсказание, DCT, энтропийное кодирование (CABAC или CAVLC).
• H.265/HEVC — преемник H.264, обеспечивает вдвое лучшее сжатие при том же качестве за счёт более сложных алгоритмов (блоки до 64×64, более точное предсказание).
• AV1 — открытый кодек, разработанный Alliance for Open Media, обеспечивает на 20–30% лучшее сжатие, чем H.265, при сопоставимой вычислительной сложности.

Применение

Компрессия данных используется повсеместно:

• Архивация файлов: форматы ZIP, RAR, 7z, tar.gz — для хранения и передачи наборов файлов.
• Изображения: JPEG, PNG, GIF, WebP — для веб-страниц, цифровой фотографии, графики.
• Аудио: MP3, AAC, FLAC, Ogg Vorbis — для музыки, подкастов, аудиокниг.
• Видео: H.264, H.265, AV1, VP9 — для потокового видео (YouTube, Netflix), видеозвонков, хранения фильмов.
• Сжатие данных в реальном времени: в видеоконференциях (Zoom, Skype), в системах видеонаблюдения, в телемедицине.
• Сжатие баз данных: методы сжатия строк, столбцов, индексов в СУБД (Oracle, SQL Server, PostgreSQL).
• Сжатие в сетях: протоколы HTTP сжатия (gzip, Brotli), сжатие заголовков в HTTP/2, сжатие в VPN и SSH.

Характеристики и показатели

Основные параметры, описывающие алгоритм сжатия:

• Коэффициент сжатия — отношение размера исходных данных к размеру сжатых (например, 5:1 означает уменьшение в 5 раз). Для сжатия с потерями часто используется битрейт (бит на пиксель, бит на секунду).
• Скорость сжатия и декомпрессии — количество обрабатываемых данных в единицу времени (МБ/с). Важна для приложений реального времени.
• Память — объём оперативной памяти, необходимый для работы алгоритма. Для мобильных устройств критична.
• Качество (для сжатия с потерями) — субъективная или объективная оценка искажений. Измеряется PSNR (пиковое отношение сигнала к шуму), SSIM (структурное сходство) или MOS (средняя экспертная оценка).

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

• Теоретический предел сжатия без потерь для данного источника определяется энтропией Шеннона. Алгоритмы, достигающие этого предела, называются энтропийно-оптимальными.
• Формат GIF (Graphics Interchange Format) использует сжатие LZW. В 1990-х годах компания Unisys пыталась взимать лицензионные отчисления за использование LZW, что привело к разработке формата PNG (Portable Network Graphics) как свободной альтернативы.
• Алгоритм сжатия без потерь PAQ (и его последователи) долгое время удерживал рекорды по степени сжатия на стандартных тестовых наборах, но требует очень большого времени и памяти.
• В 2020-х годах активно развиваются методы сжатия на основе нейронных сетей (нейрокомпрессия), которые могут превосходить традиционные кодеки по качеству при низких битрейтах, особенно для изображений и видео.

Источники

• Шеннон К. «Математическая теория связи» (1948)
• Хаффман Д. «A Method for the Construction of Minimum-Redundancy Codes» (1952)
• Зив Я., Лемпель А. «A Universal Algorithm for Sequential Data Compression» (1977)
• ISO/IEC 10918-1 (JPEG)
• ISO/IEC 14496-10 (H.264/AVC)
• ITU-T H.265 (HEVC)
• Саломон Д. «Сжатие данных, изображений и звука» (2004)
• Witten I.H., Moffat A., Bell T.C. «Managing Gigabytes: Compressing and Indexing Documents and Images» (1999)