Алгоритм LZ77

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

История

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

В 1978 году те же авторы представили модификацию — LZ78, которая отказалась от скользящего окна в пользу явного словаря, что повлияло на дальнейшее развитие методов сжатия (например, LZW). Однако LZ77 остался основой для многих современных алгоритмов, включая Deflate (используется в ZIP, PNG, gzip) и LZMA (7-Zip).

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

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

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

Размеры этих буферов фиксированы и задаются параметрами алгоритма. Алгоритм последовательно перемещает «окно» по данным, состоящее из этих двух буферов. Для каждого положения окна он ищет в буфере поиска самую длинную строку, совпадающую с началом буфера предварительного просмотра. Если такая строка найдена, она кодируется как тройка:

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

Если совпадение не найдено, символ кодируется как «литерал» — сам символ с нулевым смещением и длиной. После кодирования окно сдвигается вперёд на длину совпадения плюс один символ (или на один символ, если совпадения не было).

Пример кодирования

Рассмотрим строку «abracadabra». При размере окна, например, 10 символов, алгоритм будет обрабатывать её так:

• Сначала буфер поиска пуст, поэтому первые символы кодируются как литералы: a, b, r, a, c, a, d, a, b.
• Когда доходит до последнего «abra», буфер поиска содержит «abracadab». В нём находится совпадение «abra» (длина 4) на расстоянии 7 символов назад. Кодируется как (7, 4, ' '), где ' ' — конец строки.

Разновидности и модификации

LZ77 послужил основой для множества алгоритмов, различающихся способами кодирования, размерами окна и оптимизациями:

• LZSS (Lempel-Ziv-Storer-Szymanski) — модификация, предложенная в 1982 году. Вместо обязательной тройки (смещение, длина, следующий символ) использует флаг, указывающий, является ли следующий блок литералом или ссылкой. Это уменьшает избыточность.
• LZH — комбинация LZ77 и кодирования Хаффмана для сжатия ссылок и литералов.
• Deflate — алгоритм, используемый в форматах ZIP, gzip и PNG. Сочетает LZ77 (с фиксированным окном 32 КБ) и кодирование Хаффмана. Разработан Филом Кацем в 1993 году.
• LZMA (Lempel-Ziv-Markov chain algorithm) — алгоритм из архиватора 7-Zip, использующий LZ77 с большим окном (до 4 ГБ) и контекстное моделирование для предсказания вероятностей символов.
• LZ4 — алгоритм, ориентированный на высокую скорость сжатия и распаковки, использует LZ77 с минимальными накладными расходами.

Характеристики

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

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

Недостатки

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

Применение

LZ77 и его модификации широко применяются в системах хранения и передачи данных:

• Архиваторы — ZIP, gzip, 7-Zip (LZMA), RAR (частично).
• Графические форматы — PNG (Deflate), TIFF (LZW, но LZ77 также используется в некоторых реализациях).
• Сжатие сетевых протоколов — HTTP (gzip), SSH (zlib).
• Файловые системы — NTFS (сжатие на основе LZNT1, модификация LZ77).
• Встраиваемые системы — LZ4 используется для сжатия прошивок и логов.

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

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

• Алгоритм LZ77 был назван в честь года публикации (1977), а не по порядковому номеру версии.
• Изначально LZ77 использовал окно фиксированного размера (например, 4096 байт), что было обусловлено ограничениями памяти компьютеров того времени.
• В 1984 году Терри Уэлч опубликовал алгоритм LZW (Lempel-Ziv-Welch), который был модификацией LZ78 и стал широко известен благодаря формату GIF.
• LZ77 лежит в основе алгоритма Deflate, который используется в формате PNG — одном из самых популярных форматов для изображений в интернете.
• В 1990-х годах алгоритм LZ77 был запатентован в США (патент 4,464,650), но срок действия патента истёк, и сейчас он свободен для использования.

Критика и ограничения

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

Источники

• Ziv, J., Lempel, A. (1977). «A Universal Algorithm for Sequential Data Compression». IEEE Transactions on Information Theory.
• Storer, J. A., Szymanski, T. G. (1982). «Data compression via textual substitution». Journal of the ACM.
• Salomon, D. (2007). «Data Compression: The Complete Reference». Springer.
• Nelson, M., Gailly, J.-L. (1995). «The Data Compression Book». M&T Books.
• RFC 1951 (1996). «DEFLATE Compressed Data Format Specification».