Алгоритмы Лемпеля-Зива

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

История

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

Первоначально алгоритмы не получили широкого распространения из-за высокой вычислительной сложности. Однако в 1980-х годах, с ростом производительности процессоров и потребности в эффективном хранении данных, началась их активная реализация. В 1984 году Терри Уэлч, работая в Sperry Research Center (США), модифицировал LZ78, создав алгоритм LZW (Lempel-Ziv-Welch). LZW стал основой для таких форматов, как GIF и ранних версий TIFF.

В 1990-х годах алгоритмы LZ были интегрированы в стандарты сжатия: Deflate (комбинация LZ77 и кодирования Хаффмана) используется в ZIP, gzip и PNG; LZMA (Lempel-Ziv-Markov chain algorithm) применяется в 7z; LZSS (Lempel-Ziv-Storer-Szymanski) — в архиваторах PKZip и ARJ. К началу XXI века алгоритмы семейства Лемпеля-Зива стали доминирующим методом сжатия данных без потерь.

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

Общая идея алгоритмов Лемпеля-Зива заключается в замене повторяющихся последовательностей символов ссылками на их предыдущие вхождения. Это позволяет сократить объём данных без потери информации, так как декомпрессор может восстановить исходную последовательность, используя те же самые ссылки.

Скользящее окно (LZ77)

В LZ77 сжатие выполняется с использованием буфера, называемого скользящим окном. Окно делится на две части:

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

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

Динамический словарь (LZ78)

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

Например, для строки «ABABABA» процесс выглядит так:

• Первый символ «A» — нет совпадения, выводится (0, «A»), словарь: 1 = «A».
• Следующий символ «B» — нет совпадения, выводится (0, «B»), словарь: 2 = «B».
• Далее «AB» — совпадение с фразой «A» (индекс 1), следующий символ «A» — выводится (1, «A»), словарь: 3 = «AB».
• Затем «BA» — совпадение с фразой «B» (индекс 2), следующий символ «A» — выводится (2, «A»), словарь: 4 = «BA».
• Оставшийся символ «A» — совпадение с фразой «A» (индекс 1), следующий символ отсутствует — выводится (1, EOF).

Декомпрессор восстанавливает словарь, используя те же правила.

Классификация

Алгоритмы Лемпеля-Зива делятся на две основные ветви, а также их многочисленные модификации.

LZ77 и его производные

• LZ77 — базовый алгоритм со скользящим окном.
• LZSS (Lempel-Ziv-Storer-Szymanski) — модификация, которая кодирует совпадения только в том случае, если длина совпадения превышает некоторый порог (обычно 2-3 символа), иначе выводится исходный символ. Это повышает эффективность.
• LZH (Lempel-Ziv-Huffman) — комбинация LZ77 и кодирования Хаффмана для сжатия кодов смещений и длин.
• Deflate — алгоритм, используемый в форматах ZIP, gzip, PNG. Состоит из двух этапов: сначала LZ77 (с ограничением на длину совпадения и смещения), затем кодирование Хаффмана для полученных кодов.
• LZMA (Lempel-Ziv-Markov chain algorithm) — используется в архиваторе 7z. Основан на LZ77, но с более сложной моделью марковских цепей для предсказания символов.

LZ78 и его производные

• LZ78 — базовый алгоритм с динамическим словарём.
• LZW (Lempel-Ziv-Welch) — модификация, в которой словарь инициализируется всеми возможными односимвольными фразами (например, для 8-битных данных — 256 символов). Это упрощает реализацию и улучшает сжатие на начальных этапах. LZW широко применялся в форматах GIF и TIFF.
• LZC (Lempel-Ziv-Compress) — вариант LZW, используемый в программе compress (UNIX).
• LZMA2 — улучшенная версия LZMA, поддерживающая многопоточность и большие словари.

Применение

Алгоритмы Лемпеля-Зива нашли применение в самых разных областях:

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

• ZIP (алгоритм Deflate) — один из самых распространённых форматов архивов.
• gzip — используется для сжатия отдельных файлов в UNIX-подобных системах.
• 7z (алгоритм LZMA) — обеспечивает высокую степень сжатия, особенно для больших файлов.
• RAR (собственный алгоритм, основанный на LZSS) — популярный архиватор.

Графические форматы

• GIF (LZW) — формат для хранения растровых изображений с палитрой до 256 цветов.
• PNG (Deflate) — формат для сжатия изображений без потерь, заменивший GIF в вебе.
• TIFF — поддерживает несколько алгоритмов сжатия, включая LZW.

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

• HTTP — сжатие содержимого с помощью gzip или deflate для ускорения передачи данных.
• SSH — сжатие трафика с использованием zlib (реализация Deflate).

Файловые системы

• NTFS (Windows) — поддерживает сжатие файлов на уровне файловой системы с использованием LZNT1 (вариант LZ77).
• Btrfs (Linux) — поддерживает сжатие с помощью zlib, LZO, ZSTD (последний основан на LZ77).

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

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

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

Недостатки

• Чувствительность к размеру словаря/окна — слишком маленький словарь снижает степень сжатия, слишком большой — увеличивает потребление памяти и времени.
• Неоптимальность для коротких данных — на очень коротких строках (менее 10-20 символов) сжатие может не давать выигрыша или даже увеличивать размер.
• Патенты — алгоритм LZW был защищён патентами в США до 2003 года, что ограничивало его свободное использование.

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

• Алгоритм LZW стал причиной патентных споров в 1990-х годах. Компания Unisys, владевшая патентом на LZW, требовала лицензионных отчислений за использование формата GIF, что привело к разработке свободного формата PNG.
• В 2017 году, спустя 40 лет после публикации, Абрахам Лемпель и Якоб Зив получили премию Шеннона за основополагающий вклад в теорию сжатия данных.
• Алгоритмы Лемпеля-Зива лежат в основе большинства современных архиваторов и форматов сжатия, включая ZIP, RAR, 7z, gzip, PNG, PDF (в части сжатия потоков).

Источники

• Лемпель А., Зив Я. «A Universal Algorithm for Sequential Data Compression» (1977).
• Зив Я., Лемпель А. «Compression of Individual Sequences via Variable-Rate Coding» (1978).
• Уэлч Т. «A Technique for High-Performance Data Compression» (1984).
• Саломон Д. «Data Compression: The Complete Reference» (4-е издание, 2007).
• Нельсон М., Гейл Ж.-Л. «The Data Compression Book» (2-е издание, 1995).