Сжатие с использованием словарей

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

История

Идея использования словарей для сжатия данных восходит к 1950-м годам, когда появились первые алгоритмы, основанные на поиске повторяющихся строк. Однако практическое развитие этого направления началось в 1970-х годах.

Ранние разработки

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

Развитие и стандартизация

В 1980-х годах на основе LZ77 и LZ78 были созданы практические реализации:

• LZW (Lempel-Ziv-Welch) — модификация LZ78, предложенная Терри Уэлчем в 1984 году. Алгоритм лёг в основу форматов GIF (CompuServe, 1987) и TIFF.
• Deflate — гибридный алгоритм, разработанный Филом Кацем в 1993 году для архиватора PKZIP. Он комбинирует LZ77 с кодированием Хаффмана. Deflate стал стандартом для форматов ZIP, gzip, PNG и HTTP-сжатия.
• LZMA (Lempel-Ziv-Markov chain algorithm) — алгоритм, созданный Игорем Павловым в 1998 году для архиватора 7-Zip. Он использует усовершенствованный LZ77 с марковскими цепями и большим словарём.

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

Словарное сжатие основано на поиске и кодировании повторяющихся фрагментов. Процесс включает два этапа: построение словаря и кодирование.

Построение словаря

Словарь может быть:

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

Кодирование

Алгоритм последовательно читает входные данные и ищет в словаре самую длинную строку, совпадающую с текущей позицией. Если совпадение найдено, она заменяется ссылкой (парой «смещение, длина» в LZ77 или индексом фразы в LZ78). Если совпадения нет, символ кодируется как литерал (непосредственное значение). На выходе получается поток токенов, который затем может быть дополнительно сжат статистическим кодером.

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

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

Алгоритмы семейства LZ77

Используют скользящее окно. Примеры:

• LZ77 — базовый алгоритм. Словарь — буфер последних N байт. Код: (смещение, длина, следующий символ).
• Deflate — комбинация LZ77 и кодирования Хаффмана. Использует окно размером 32 КБ.
• LZMA — расширенная версия LZ77 с марковскими цепями для прогнозирования вероятностей. Окно может достигать 4 ГБ.
• LZSS (Lempel-Ziv-Storer-Szymanski) — оптимизация LZ77, где литералы и ссылки кодируются разными битовыми флагами.

Алгоритмы семейства LZ78

Строят словарь из фраз. Примеры:

• LZ78 — базовый алгоритм. Словарь — таблица, пополняемая новыми фразами.
• LZW — модификация LZ78, где словарь инициализируется всеми возможными одиночными символами. Широко применялся в GIF и TIFF.
• LZMW — вариант LZW с улучшенным управлением словарём.

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

• LZ4 — быстрый алгоритм, ориентированный на скорость сжатия и распаковки. Используется в базах данных и сетевых протоколах.
• Brotli — алгоритм, разработанный Google в 2013 году. Комбинирует LZ77 с контекстным моделированием и статическим словарём из 13 000 фраз для веб-контента.
• Zstandard (Zstd) — алгоритм, созданный Яном Колле в 2015 году. Использует LZ77 с конечными автоматами и адаптивным кодированием.

Применение

Словарное сжатие широко применяется в различных областях информационных технологий благодаря высокой эффективности и скорости.

Архивация данных

• ZIP — использует Deflate. Стандарт для архивации в Windows и macOS.
• 7z — использует LZMA и LZMA2. Обеспечивает высокую степень сжатия.
• gzip — использует Deflate. Применяется в Unix-подобных системах и HTTP-сжатии.
• RAR — проприетарный алгоритм, основанный на LZSS и PPM.

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

• GIF — использует LZW. Поддерживает до 256 цветов.
• PNG — использует Deflate после фильтрации строк. Формат сжатия без потерь.
• TIFF — может использовать LZW или Deflate.

Сетевые протоколы

• HTTP — сжатие контента с помощью gzip, Deflate, Brotli.
• SSH — сжатие трафика с помощью Zlib (Deflate).
• WebSocket — сжатие с помощью permessage-deflate.

Базы данных и файловые системы

• ZFS — использует LZ4, Zstd, gzip для сжатия данных на диске.
• Btrfs — поддерживает сжатие с помощью Zstd, LZO, Zlib.
• SQLite — использует Deflate для сжатия страниц.

Сравнение с другими методами

Словарное сжатие имеет ряд преимуществ и недостатков по сравнению со статистическими и контекстными методами.

Преимущества

• Высокая скорость — особенно для алгоритмов LZ4 и LZSS, которые могут обрабатывать данные со скоростью до нескольких гигабайт в секунду.
• Эффективность на структурированных данных — тексты, код, таблицы сжимаются в 2–5 раз.
• Простота реализации — базовые алгоритмы LZ77 и LZ78 легко программируются.
• Отсутствие необходимости в предварительном анализе — динамический словарь адаптируется к данным.

Недостатки

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

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

• Алгоритм LZW был запатентован компанией Unisys в 1985 году, что привело к юридическим спорам при использовании GIF. Патент истёк в 2003 году.
• Алгоритм Deflate не был запатентован, что способствовало его широкому распространению в открытых форматах (PNG, ZIP).
• В 2010-х годах Google разработал Brotli специально для сжатия веб-страниц, что позволило сократить время загрузки на 20–30% по сравнению с gzip.
• Алгоритм Zstandard от Facebook (организация Meta признана экстремистской и запрещена в РФ) используется в системах хранения данных и распределённых базах данных, таких как Apache Hadoop и RocksDB.

Источники

• Зив Я., Лемпель А. «A Universal Algorithm for Sequential Data Compression» (1977).
• Уэлч Т. «A Technique for High-Performance Data Compression» (1984).
• Дойч П. «DEFLATE Compressed Data Format Specification» (RFC 1951, 1996).
• Павлов И. «7z Format Description» (1999).
• Колле Я. «Zstandard — Real-time data compression algorithm» (2015).
• Google. «Brotli Compressed Data Format» (RFC 7932, 2016).