LZ77

LZ77 — это алгоритм сжатия данных без потерь, основанный на словарном подходе, в котором повторяющиеся последовательности символов заменяются ссылками на их предыдущие вхождения. Разработан в 1977 году израильскими учёными Авраамом Лемпелем и Якобом Зивом. Относится к классу алгоритмов LZ (Lempel-Ziv), ставших основой для многих современных форматов сжатия, включая DEFLATE, LZMA, LZSS и LZW.

История

Алгоритм LZ77 был впервые описан в статье «A Universal Algorithm for Sequential Data Compression» (IEEE Transactions on Information Theory, 1977). Лемпель и Зив предложили метод, который не требует предварительного построения статистической модели данных, как в алгоритмах Хаффмана или арифметическом кодировании, а работает на лету, анализируя уже обработанный поток.

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

В 1978 году Лемпель и Зив опубликовали модификацию — LZ78, которая использует не скользящее окно, а динамически растущий словарь из всех встреченных фраз. LZ77 остаётся более распространённым в практических реализациях из-за простоты и эффективности.

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

Скользящее окно

Алгоритм поддерживает два буфера фиксированного размера:

• Словарь (search buffer) — уже закодированные данные, которые служат источником для поиска повторений.
• Буфер предварительного просмотра (look-ahead buffer) — ещё не закодированные данные, которые обрабатываются в текущий момент.

Размеры этих буферов задаются параметрами алгоритма (например, 4 КБ словарь и 256 байт буфер просмотра). Окно «скользит» по мере обработки: после кодирования фрагмента данные из буфера просмотра перемещаются в словарь, а старые данные «выталкиваются» за пределы окна.

Кодирование

На каждом шаге алгоритм ищет в словаре самую длинную последовательность, совпадающую с началом буфера просмотра. Если совпадение найдено, оно кодируется тройкой чисел:

• смещение (offset) — расстояние от текущей позиции до начала совпадения в словаре (в символах назад);
• длина (length) — длина совпадающей последовательности;
• следующий символ (next character) — первый символ после совпадения, который не удалось найти в словаре.

Если совпадение не найдено (или его длина меньше минимальной), кодируется одиночный символ: смещение и длина равны нулю, а следующий символ — сам этот символ.

Декодирование

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

Пример

Пусть словарь содержит «abcab», а буфер просмотра — «abcde». Алгоритм найдёт совпадение «abc» длиной 3 на смещении 2 (от конца словаря). Он закодирует это как (2, 3, 'd'), где 'd' — первый несовпавший символ. После кодирования окно сдвинется: словарь станет «bcab abc», а буфер — «de...».

Параметры и оптимизации

Размер окна

Чем больше словарь, тем выше вероятность найти длинное совпадение, но тем больше памяти требуется для хранения и поиска. Размер буфера просмотра ограничивает максимальную длину совпадения. Типичные значения: словарь 4–32 КБ, буфер 16–256 байт.

Минимальная длина совпадения

Короткие совпадения (например, 1–2 символа) могут не давать выигрыша, так как тройка занимает больше места, чем исходные символы. Поэтому часто вводят порог (например, 3 символа), ниже которого кодируется одиночный символ.

Поиск совпадений

Наивный поиск (полный перебор словаря) имеет сложность O(n²), что неприемлемо для больших данных. Для ускорения применяются хеш-таблицы, бинарные деревья или алгоритм Ziv-Lempel с хешированием цепочек (LZSS).

Применение

Форматы сжатия

• Deflate (используется в ZIP, gzip, PNG) — комбинация LZ77 и кодирования Хаффмана.
• LZMA (7-Zip, XZ) — улучшенная версия LZ77 с большим словарём и контекстным моделированием.
• LZSS (Lempel-Ziv-Storer-Szymanski) — модификация, где вместо тройки используется пара (смещение, длина) для совпадений, а одиночные символы кодируются отдельно.
• Zstandard (zstd) — современный алгоритм, использующий LZ77 с конечными автоматами.

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

• HTTP — сжатие содержимого с помощью gzip (Deflate).
• VPN — сжатие трафика в протоколах LZS (Lempel-Ziv-Stac).
• Файловые системы — сжатие на диске (NTFS, Btrfs, ZFS) использует LZ77 в составе алгоритмов.

Архиваторы

• PKZIP, WinRAR, 7-Zip — все поддерживают LZ77 в различных реализациях.

Преимущества и недостатки

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

• Сжатие без потерь — полное восстановление исходных данных.
• Скорость — декодирование очень быстрое, так как не требует сложных вычислений.
• Универсальность — работает с любыми данными, не требует предварительной статистики.
• Простота реализации — базовая версия алгоритма легко программируется.

Недостатки

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

Варианты и модификации

LZSS (1982)

Джеймс Сторер и Томас Шимански предложили модификацию, где:

• одиночные символы кодируются без дополнительных битов (флаг «0» + символ);
• совпадения кодируются парой (смещение, длина) с флагом «1»;
• минимальная длина совпадения — 3 символа (двухсимвольные совпадения невыгодны).

Этот вариант используется в форматах LHA, ARJ, а также в некоторых реализациях Deflate.

LZ77 с хешированием

Для ускорения поиска совпадений применяется хеш-таблица, где ключом является хеш первых нескольких символов буфера просмотра. Это позволяет находить потенциальные совпадения за O(1) в среднем. Используется в LZMA, zstd, Deflate.

LZ77 с контекстным моделированием

В алгоритмах LZMA и LZMA2 (7-Zip) после поиска совпадений применяется арифметическое кодирование с учётом контекста (например, предыдущих символов, длины совпадения, смещения). Это повышает степень сжатия на 10–30% по сравнению с базовым LZ77.

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

• Алгоритм LZ77 лёг в основу стандарта сжатия V.42bis (модемы, 1989), который использовался для сжатия данных в телефонных линиях.
• В 2014 году алгоритм LZ4 (вариация LZ77) стал стандартом для сжатия в реальном времени в ядре Linux (сжатие страниц памяти, сетевых пакетов).
• LZ77 является одним из немногих алгоритмов, защищённых патентом (US 4464650, 1984), но срок действия патента истёк в 2004 году, после чего алгоритм стал полностью свободным.
• В 2023 году алгоритм Zstandard (zstd), использующий LZ77, был принят как стандарт сжатия для формата PDF 2.0.

Источники

1. Lempel A., Ziv J. «A Universal Algorithm for Sequential Data Compression». IEEE Transactions on Information Theory, 1977.
2. Storer J., Szymanski T. «Data Compression via Textual Substitution». Journal of the ACM, 1982.
3. Salomon D. «Data Compression: The Complete Reference». 4th ed., Springer, 2007.
4. Sayood K. «Introduction to Data Compression». 5th ed., Morgan Kaufmann, 2017.
5. RFC 1951 — DEFLATE Compressed Data Format Specification, 1996.
6. 7-Zip LZMA SDK Documentation, 2022.