Сжатие данных и файлов¶

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

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

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

Ключевой характеристикой любого алгоритма является коэффициент сжатия — отношение размера исходных данных к размеру сжатых. Этот показатель зависит от типа данных и выбранного метода. Например, текстовые документы сжимаются в 3–10 раз, фотографии — в 2–5 раз, а уже сжатые форматы (JPEG, MP3) практически не поддаются дальнейшему уменьшению.

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

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

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

• Алгоритм Хаффмана — метод, основанный на присвоении символам кодов переменной длины: часто встречающимся символам — короткие коды, редким — длинные.
• LZ77 и LZ78 — словарные методы, заменяющие повторяющиеся последовательности ссылками на предыдущие вхождения. На их основе построены форматы ZIP, GZIP и PNG.
• LZW — модификация LZ78, используемая в форматах GIF и TIFF.
• Арифметическое кодирование — метод, кодирующий весь поток данных одним дробным числом, обеспечивая более высокую степень сжатия, чем Хаффман.
• BWT (преобразование Барроуза — Уилера) — блочная сортировка символов, применяемая в архиваторе bzip2.

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

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

• JPEG — сжатие изображений на основе дискретного косинусного преобразования.
• MP3 и AAC — сжатие аудио с учётом психоакустической модели слуха человека.
• MPEG и H.264 — семейства стандартов сжатия видео, использующие межкадровую и внутрикадровую компрессию.
• WebP и AVIF — современные форматы изображений, сочетающие методы без потерь и с потерями.

¶Архиваторы и форматы архивов

Архивация — объединение нескольких файлов в один с последующим сжатием. Наиболее распространённые форматы:

• ZIP — самый универсальный формат, поддерживаемый всеми операционными системами. Использует алгоритмы Deflate (комбинация LZ77 и Хаффмана) и BZIP2.
• RAR — проприетарный формат, разработанный российским программистом Евгением Рошалем. Обеспечивает высокую степень сжатия и поддерживает восстановление повреждённых архивов.
• 7z — формат архиватора 7-Zip, использующий алгоритм LZMA (вариант LZ77 с арифметическим кодированием). Обеспечивает один из лучших коэффициентов сжатия.
• TAR — формат объединения файлов без сжатия, обычно применяется вместе с GZIP или XZ в Unix-подобных системах.

¶История развития

Первые алгоритмы сжатия появились в 1950-х годах вместе с развитием вычислительной техники. В 1952 году Дэвид Хаффман опубликовал свой алгоритм кодирования. В 1977–1978 годах Авраам Лемпель и Яаков Зив разработали словарные методы LZ77 и LZ78, ставшие основой большинства современных алгоритмов.

В 1980-х годах Терри Вэлч создал алгоритм LZW, использованный в формате GIF. В 1993 году вышел стандарт JPEG, а в 1994 году — MPEG-1, определившие развитие мультимедийных технологий. В 1993 году Евгений Рошаль выпустил первый архиватор RAR. В 1999 году появился формат 7z, а в 2010-х годах — современные алгоритмы Brotli и Zstandard, ориентированные на высокую скорость работы.

¶Области применения

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

• Операционные системы — встроенные средства сжатия NTFS (Windows) и ZFS (Unix-подобные системы) уменьшают занимаемое место на дисках.
• Сети и интернет — протоколы HTTP используют сжатие gzip и Brotli для ускорения загрузки веб-страниц.
• Мультимедиа — все цифровые фотоаппараты, видеокамеры и музыкальные сервисы применяют сжатие с потерями.
• Базы данных — сжатие строк и страниц в СУБД сокращает объём хранилища и ускоряет чтение.
• Резервное копирование — архивация данных перед хранением на лентах и облачных сервисах.

¶Критерии выбора метода

Выбор алгоритма сжатия определяется несколькими факторами: требуемый коэффициент сжатия, скорость работы, объём потребляемой памяти и допустимость потерь. Для текстовых документов предпочтительны методы без потерь, для фотографий — JPEG или WebP, для видео — H.264 или H.265. В системах реального времени, например в видеоконференциях, критична скорость, поэтому используются упрощённые алгоритмы с меньшим коэффициентом сжатия.

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

• Алгоритм Хаффмана был создан Дэвидом Хаффманом как курсовая работа в Массачусетском технологическом институте.
• Формат GIF долгое время был предметом патентных споров из-за алгоритма LZW, что привело к разработке свободного формата PNG.
• Современный формат JPEG XL поддерживает как сжатие без потерь, так и с потерями, обеспечивая обратную совместимость с JPEG.