Алгоритмы сжатия данных

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

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

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

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

Классификация алгоритмов

По типу сжатия

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

Сжатие с потерями (lossy) — процесс, при котором восстановленные данные отличаются от исходных, но в пределах допустимой погрешности. Применяется для мультимедийных данных (аудио, видео, изображения), где незначительная потеря качества незаметна для человеческого восприятия. Примеры: JPEG, MP3, MPEG-4.

По способу обработки данных

Потоковые (адаптивные) алгоритмы — обрабатывают данные последовательно, строя модель по мере поступления. Не требуют предварительного анализа всего файла. Пример: LZ77.

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

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

Алгоритмы без потерь

Алгоритм Хаффмана (Huffman coding) — один из первых и наиболее известных методов. Строит оптимальное префиксное дерево на основе частот символов, присваивая более короткие коды часто встречающимся символам. Разработан Дэвидом Хаффманом в 1952 году. Используется в форматах ZIP, JPEG (часть цепочки), MP3.

Арифметическое кодирование (Arithmetic coding) — более эффективный, чем Хаффман, метод, который кодирует всё сообщение в одно число в интервале [0, 1). Позволяет приблизиться к теоретическому пределу энтропии. Используется в стандартах JPEG 2000, H.264, CABAC.

Алгоритмы LZ (Lempel-Ziv) — семейство словарных методов, разработанных Абрахамом Лемпелем и Якобом Зивом в 1977–1978 годах. Основные варианты:

• LZ77 — использует скользящее окно и словарь из уже обработанных данных. Заменяет повторяющиеся последовательности ссылками на предыдущие вхождения. Лёг в основу форматов ZIP, GZIP, PNG.
• LZ78 — строит глобальный словарь фраз, который может расти. Основа для формата GIF (LZW).

Алгоритм Барроуза — Уилера (BWT, Burrows-Wheeler Transform) — преобразование, которое переставляет символы так, чтобы одинаковые символы оказывались рядом, что повышает эффективность последующего сжатия. Используется в формате bzip2.

Дельта-кодирование (Delta encoding) — записывает разности между последовательными значениями. Эффективно для данных с плавными изменениями (аудио, временные ряды).

Кодирование длин серий (RLE, Run-Length Encoding) — заменяет последовательности одинаковых символов на пару (символ, количество повторов). Прост и эффективен для изображений с большими однотонными областями (BMP, PCX).

Алгоритмы с потерями

JPEG (Joint Photographic Experts Group) — стандарт сжатия изображений. Основан на дискретном косинусном преобразовании (DCT), которое переводит блоки пикселей в частотную область, после чего высокочастотные компоненты квантуются (отбрасываются) с меньшей точностью.

MPEG (Moving Picture Experts Group) — семейство стандартов сжатия видео. Использует межкадровое предсказание (I-, P-, B-кадры) и DCT-преобразование. Наиболее известны MPEG-2 (DVD) и MPEG-4 AVC/H.264 (современное видео).

MP3 (MPEG-1 Audio Layer 3) — формат сжатия аудио с потерями. Основан на психоакустической модели, которая удаляет звуки, неразличимые для человеческого уха.

Вейвлет-сжатие (Wavelet compression) — использует вейвлет-преобразование, которое даёт лучшее качество при низких битрейтах по сравнению с DCT. Применяется в формате JPEG 2000 и в аудиокодеке FLAC (без потерь).

Применение

Алгоритмы сжатия данных широко используются в различных областях:

• Архивация файлов: форматы ZIP, RAR, 7z, GZIP, bzip2.
• Цифровое изображение и видео: JPEG, PNG, GIF, MPEG, H.264, HEVC.
• Цифровое аудио: MP3, AAC, FLAC, Ogg Vorbis.
• Сетевые протоколы: HTTP (сжатие gzip/deflate), SSH, VPN.
• Базы данных: сжатие строк и столбцов для уменьшения объёма хранимых данных.
• Научные вычисления: сжатие результатов моделирования, телеметрии, медицинских изображений (DICOM).

Критерии выбора алгоритма

Выбор конкретного алгоритма зависит от нескольких факторов:

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

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

• Первый алгоритм сжатия данных (код Морзе) был разработан в 1830-х годах для телеграфии.
• Алгоритм Хаффмана был создан Дэвидом Хаффманом в рамках курсовой работы в Массачусетском технологическом институте.
• Формат ZIP был создан Филом Кацем в 1989 году и стал одним из самых распространённых форматов архивации.
• Современные алгоритмы сжатия видео (H.265/HEVC, AV1) могут достигать коэффициента сжатия более 1000:1 без заметной потери качества.
• Алгоритм LZMA (Lempel-Ziv-Markov chain) используется в архиваторе 7z и обеспечивает один из самых высоких коэффициентов сжатия среди алгоритмов без потерь.

Источники

• Шеннон К. Работы по теории информации и кибернетике. — М.: Иностранная литература, 1963.
• Huffman D. A. A Method for the Construction of Minimum-Redundancy Codes // Proceedings of the IRE. — 1952. — Vol. 40, No. 9. — P. 1098–1101.
• Ziv J., Lempel A. A Universal Algorithm for Sequential Data Compression // IEEE Transactions on Information Theory. — 1977. — Vol. 23, No. 3. — P. 337–343.
• Burrows M., Wheeler D. J. A Block-sorting Lossless Data Compression Algorithm // Technical Report 124. — Digital Equipment Corporation, 1994.
• Wallace G. K. The JPEG Still Picture Compression Standard // Communications of the ACM. — 1991. — Vol. 34, No. 4. — P. 30–44.
• ISO/IEC 11172-3:1993 — Coding of moving pictures and associated audio for digital storage media at up to about 1,5 Mbit/s — Part 3: Audio.