Сжатие данных

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

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

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

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

Классификация методов сжатия

Все методы сжатия данных делятся на два основных класса: сжатие без потерь и сжатие с потерями.

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

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

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

• Кодирование Хаффмана (Huffman coding) — один из первых и наиболее известных алгоритмов. Присваивает более короткие коды символам, которые встречаются чаще, и более длинные — редким символам. Используется во многих форматах (ZIP, JPEG — на этапе энтропийного кодирования).
• Арифметическое кодирование (Arithmetic coding) — более эффективный, но и более сложный метод. Кодирует всю последовательность символов в одно число с плавающей точкой в интервале [0, 1). Обеспечивает сжатие, близкое к теоретическому пределу (энтропии).
• LZ77 и LZ78 (Lempel-Ziv) — словарные методы, основанные на поиске повторяющихся последовательностей (фраз) в данных. Вместо повторной записи фразы сохраняется ссылка на её предыдущее вхождение. Алгоритмы LZ являются основой форматов ZIP, gzip, PNG и многих других.
• LZW (Lempel-Ziv-Welch) — модификация LZ78, широко использовавшаяся в форматах GIF и TIFF.
• BWT (Burrows-Wheeler Transform) — преобразование, которое переставляет символы в строке так, чтобы одинаковые символы оказывались рядом. Само по себе не сжимает, но подготавливает данные для эффективного кодирования (например, с помощью move-to-front и Хаффмана). Лежит в основе архиватора bzip2.

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

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

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

• JPEG (Joint Photographic Experts Group) — стандарт сжатия фотографических изображений. Использует дискретное косинусное преобразование (DCT) для перевода изображения в частотную область, после чего высокочастотные детали, малозаметные для глаза, отбрасываются или квантуются с большим шагом.
• MPEG (Moving Picture Experts Group) — семейство стандартов для сжатия видео (MPEG-1, MPEG-2, MPEG-4, H.264/AVC, H.265/HEVC). Используют межкадровое предсказание (кодирование только изменений между кадрами), DCT и другие методы.
• MP3 (MPEG-1 Audio Layer 3) — популярный формат сжатия аудио. Основан на психоакустической модели: удаляются звуки, которые маскируются более громкими или находятся за пределами чувствительности человеческого уха.
• AAC (Advanced Audio Coding) — более совершенный аудиокодек, чем MP3, обеспечивающий лучшее качество при той же битрейте.
• Wavelet-сжатие — используется в формате JPEG 2000 и некоторых других. Преобразование вейвлетами позволяет лучше сохранять детали при сильном сжатии, чем DCT.

Применение

Сжатие данных повсеместно используется в современных технологиях.

Хранение данных

• Архиваторы: ZIP, RAR, 7z, gzip, bzip2 — позволяют упаковывать файлы и папки для экономии места на диске.
• Файловые системы: некоторые файловые системы (NTFS, ZFS) поддерживают прозрачное сжатие на уровне диска.
• Форматы файлов: PNG (изображения без потерь), JPEG (изображения с потерями), GIF (анимация, до 256 цветов), MP3, AAC (аудио), MP4, AVI (видео), PDF (документы, часто со сжатием).

Передача данных

• Интернет: протокол HTTP использует сжатие (gzip, deflate) для ускорения загрузки веб-страниц. Протоколы потокового видео (YouTube, Netflix) используют адаптивное сжатие (H.264, H.265) в зависимости от скорости соединения.
• Сотовая связь: голосовые кодеки (AMR, EVRC) сжимают речь для передачи по каналам с ограниченной пропускной способностью.
• Спутниковая и космическая связь: сжатие изображений и телеметрии необходимо из-за низкой скорости передачи данных на большие расстояния. Например, марсоходы используют специальные алгоритмы сжатия для передачи снимков на Землю.

Обработка сигналов

• Медицина: сжатие медицинских изображений (МРТ, КТ, рентген) должно быть без потерь или с минимальными потерями, чтобы не исказить диагностическую информацию. Используются специализированные форматы (DICOM).
• Научные данные: сжатие данных с экспериментов (например, с Большого адронного коллайдера) необходимо для их хранения и анализа.

Критерии оценки эффективности

Эффективность алгоритма сжатия оценивается по нескольким параметрам:

• Коэффициент сжатия (Compression ratio) — отношение размера исходных данных к размеру сжатых. Чем выше, тем лучше.
• Скорость сжатия и распаковки — важна для приложений реального времени (видеоконференции, стриминг).
• Качество восстановления (для сжатия с потерями) — измеряется объективными метриками (PSNR — пиковое отношение сигнала к шуму, SSIM — индекс структурного сходства) и субъективными оценками (тесты на восприятие).
• Потребление памяти — некоторые алгоритмы требуют значительных объёмов оперативной памяти для работы (например, LZMA в 7z).

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

• Первый практический алгоритм сжатия без потерь (кодирование Хаффмана) был разработан Дэвидом Хаффманом в 1952 году.
• Формат GIF (Graphics Interchange Format) долгое время был предметом патентных споров из-за использования алгоритма LZW, запатентованного компанией Unisys.
• Алгоритм BWT (Burrows-Wheeler Transform) был изобретён Майклом Барроузом и Дэвидом Уилером в 1994 году и лёг в основу архиватора bzip2.
• Современные кодеки (H.265/HEVC, AV1) используют сложные методы, такие как внутрикадровое предсказание, компенсация движения и контурная фильтрация, для достижения высоких коэффициентов сжатия видео.
• В России разработан ряд алгоритмов сжатия, например, алгоритм сжатия изображений, используемый в системе космической связи «Орбита», и специализированные кодеки для передачи данных в системах управления.

Источники

• Шеннон К. Работы по теории информации и кибернетике. — М.: Издательство иностранной литературы, 1963.
• Хаффман Д. А. Метод построения кодов с минимальной избыточностью. — Труды IRE, 1952.
• Саломон Д. Сжатие данных, изображений и звука. — М.: Техносфера, 2004.
• Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М.: ДИАЛОГ-МИФИ, 2003.
• ISO/IEC 10918-1 (JPEG), ISO/IEC 14496-10 (H.264/AVC), ISO/IEC 23008-2 (H.265/HEVC).