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

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

Принцип работы

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

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

История

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

В 1977 году Абрахам Лемпель и Якоб Зив опубликовали алгоритм LZ77, который лёг в основу многих современных архиваторов, включая DEFLATE (используется в ZIP, gzip, PNG). В 1978 году они предложили улучшенную версию LZ78. Эти алгоритмы стали прорывом, так как они не требовали априорного знания статистики данных и могли адаптироваться к их структуре.

В 1980-х и 1990-х годах появились алгоритмы, основанные на контекстном моделировании и арифметическом кодировании, такие как PPM (Prediction by Partial Matching) и PAQ. Они достигали рекордных степеней сжатия, но требовали значительных вычислительных ресурсов. В 2000-х годах развитие получили алгоритмы на основе преобразования Барроуза — Уилера (BWT), используемые в bzip2.

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

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

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

Эти методы заменяют символы или последовательности символов кодами переменной длины, причём более частые символы получают более короткие коды.

• Код Хаффмана — строит оптимальное префиксное дерево на основе частот символов. Широко применяется в архиваторах (ZIP, gzip) и форматах изображений (PNG).
• Арифметическое кодирование — кодирует весь поток данных в одно число из интервала [0, 1). Обеспечивает лучшую степень сжатия, чем код Хаффмана, особенно для данных с неравномерным распределением вероятностей. Используется в JPEG 2000, H.264, формате CABAC.
• Код Шеннона — Фано — один из первых методов, но уступает коду Хаффмана по оптимальности.

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

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

• LZ77 — использует скользящее окно, в котором ищутся совпадения. На выходе выдаются пары (смещение, длина). Лёг в основу DEFLATE.
• LZ78 — строит словарь фраз по мере обработки данных. Каждая фраза кодируется ссылкой на предыдущую фразу плюс новый символ. Используется в формате GIF.
• LZW (Lempel-Ziv-Welch) — модификация LZ78, разработанная Терри Велчем. Широко применялся в ранних архиваторах (compress) и формате TIFF.

Методы на основе контекстного моделирования

Эти алгоритмы предсказывают вероятность следующего символа на основе уже обработанного контекста. Чем больше контекст, тем точнее предсказание, но выше требования к памяти.

• PPM (Prediction by Partial Matching) — использует конечные контексты разной длины. Достигает высокой степени сжатия на текстовых данных.
• PAQ — семейство алгоритмов, использующих нейросетевые и статистические модели для предсказания. Являются одними из лучших по степени сжатия, но очень медленны.

Преобразования

Эти методы не сжимают данные напрямую, а переупорядочивают их так, чтобы они стали более удобными для последующего энтропийного кодирования.

• Преобразование Барроуза — Уилера (BWT) — переставляет символы так, чтобы одинаковые символы оказывались рядом. После этого данные легко сжимаются простыми методами (например, RLE). Используется в bzip2.
• Преобразование MTF (Move-To-Front) — заменяет каждый символ его индексом в списке, который постоянно переупорядочивается. Часто применяется после BWT.
• RLE (Run-Length Encoding) — заменяет последовательности одинаковых символов на пару (символ, количество повторений). Эффективен для данных с длинными повторами (например, чёрно-белые изображения, штрих-коды).

Применение

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

Архивация и хранение

• ZIP (алгоритм DEFLATE) — стандартный формат для сжатия файлов в Windows, macOS и Linux.
• gzip — популярный архиватор в Unix-подобных системах (использует DEFLATE).
• 7z (LZMA, LZMA2) — обеспечивает более высокую степень сжатия, чем ZIP, за счёт использования словарных методов с большими окнами.
• RAR (RARLAB) — проприетарный формат, использующий собственные алгоритмы (PPMd, LZSS).

Форматы изображений

• PNG (Portable Network Graphics) — использует фильтрацию строк и DEFLATE. Поддерживает прозрачность и палитры.
• GIF (Graphics Interchange Format) — использует LZW. Ограничен 256 цветами, но поддерживает анимацию.
• BMP — может быть сжат с помощью RLE (необязательно).
• TIFF — поддерживает множество алгоритмов, включая LZW, DEFLATE, PackBits.

Форматы аудио

• FLAC (Free Lossless Audio Codec) — открытый формат, использующий линейное предсказание и кодирование остатков.
• ALAC (Apple Lossless Audio Codec) — проприетарный, но открытый формат от Apple.
• WavPack — поддерживает как сжатие без потерь, так и гибридные режимы.
• APE (Monkey's Audio) — обеспечивает высокую степень сжатия, но требует больше ресурсов.

Форматы видео

• FFV1 — свободный кодек без потерь, разработанный для архивирования видео.
• H.264 Lossless — режим без потерь в стандарте H.264/AVC.
• Apple ProRes 4444 — поддерживает альфа-канал и сжатие без потерь.
• VP9 Lossless — режим без потерь в кодеках Google.

Другие области

• Сжатие текстов — программы-архиваторы (ZIP, RAR), а также специализированные форматы (например, для электронных книг).
• Сжатие баз данных — методы сжатия строк и чисел (например, в SQLite, Oracle).
• Сжатие исполняемых файлов — упаковщики (UPX, ASPack) уменьшают размер программ без потери функциональности.
• Сжатие медицинских изображений — DICOM поддерживает сжатие без потерь (JPEG-LS, JPEG 2000 lossless).
• Сжатие научных данных — HDF5, NetCDF, FITS используют алгоритмы без потерь для хранения результатов экспериментов.

Сравнение с методами с потерями

Основное различие между сжатием с потерями и без потерь заключается в допустимости искажений. Сжатие с потерями (например, JPEG, MP3, H.264) достигает гораздо более высокой степени сжатия за счёт отбрасывания несущественной, с точки зрения восприятия, информации. Однако восстановить исходные данные в точности невозможно.

Сжатие без потерь, напротив, гарантирует полную идентичность, но обычно даёт меньший коэффициент сжатия. Для текстовых файлов типичный коэффициент составляет 2–5 раз, для изображений — 1.5–3 раза, для аудио — 1.5–2.5 раза. Для уже сжатых данных (например, JPEG-файлов) сжатие без потерь практически неэффективно.

Критерии оценки

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

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

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

• Алгоритм Хаффмана, несмотря на свою простоту, до сих пор используется в большинстве современных архиваторов и форматов (PNG, JPEG, MP3).
• Преобразование Барроуза — Уилера было открыто в 1994 году, но его идея была независимо предложена ещё в 1980-х годах.
• Формат FLAC был разработан в 2000 году Джошем Коулсоном и до сих пор остаётся стандартом для сжатия аудио без потерь.
• Алгоритмы семейства PAQ (например, PAQ8) выигрывали многие конкурсы по сжатию данных, но их практическое применение ограничено из-за высокой вычислительной сложности.
• В 2020-х годах активно развиваются методы сжатия на основе нейронных сетей, которые могут превзойти традиционные алгоритмы по степени сжатия, но пока остаются медленными.

Источники

• Клод Шеннон. «Математическая теория связи» (1948)
• Дэвид Хаффман. «A Method for the Construction of Minimum-Redundancy Codes» (1952)
• Абрахам Лемпель, Якоб Зив. «A Universal Algorithm for Sequential Data Compression» (1977)
• Терри Велч. «A Technique for High-Performance Data Compression» (1984)
• М. Барроуз, Д. Уилер. «A Block-sorting Lossless Data Compression Algorithm» (1994)
• Спецификации форматов PNG, FLAC, ZIP, gzip, bzip2
• Стандарты ISO/IEC 10918 (JPEG), 14495 (JPEG-LS), 15444 (JPEG 2000)