LZSS

LZSS (Lempel-Ziv-Storer-Szymanski) — это алгоритм сжатия данных без потерь, основанный на словарном подходе, являющийся модификацией алгоритма LZ77. Разработан Джеймсом Сторером и Томасом Шимански в 1982 году. LZSS устраняет основной недостаток LZ77 — избыточность, возникающую при кодировании коротких совпадений, которые не дают выигрыша в размере.

История

Алгоритм LZSS был предложен в 1982 году в статье «Data Compression via Textual Substitution» (Сжатие данных с помощью текстовой замены) Джеймсом Сторером и Томасом Шимански. Он стал развитием идей LZ77, опубликованных Абрахамом Лемпелем и Якобом Зивом в 1977 году. Основная цель авторов заключалась в повышении эффективности сжатия за счёт введения механизма, который предотвращает кодирование совпадений, не приводящих к уменьшению объёма данных.

LZSS получил широкое распространение в 1980-1990-х годах благодаря своей простоте и эффективности. Он использовался в архиваторах (например, PKZIP, ARJ, ZOO), в файловых системах (например, сжатие в MS-DOS с помощью DoubleSpace/DriveSpace), в протоколах модемной связи (V.42bis) и во встроенных системах.

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

Как и LZ77, LZSS использует скользящее окно, которое делится на две части:

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

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

Ключевое отличие от LZ77

Основное нововведение LZSS заключается в том, что он не кодирует совпадения, длина которых меньше минимального порога. Обычно этот порог равен 2 или 3 символам. Если длина совпадения меньше порога, алгоритм выводит символ как есть (литерал). Если длина совпадения равна или превышает порог, выводится ссылка на совпадение.

Для различения литералов и ссылок используется флаг-бит (или несколько битов), который добавляется к каждому элементу выходного потока. Например, флаг «0» может означать литерал, а «1» — ссылку. Это позволяет декодеру однозначно интерпретировать данные.

Формат кодирования

Выходной поток LZSS состоит из последовательности элементов двух типов:

• Литерал — один байт исходных данных. Кодируется флагом литерала и самим байтом.
• Ссылка — пара (смещение, длина). Кодируется флагом ссылки, смещением (обычно 12-15 бит) и длиной (обычно 4-7 бит).

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

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

• Простота реализации — алгоритм не требует сложных математических операций и больших объёмов памяти.
• Высокая скорость — как сжатия, так и распаковки, особенно при небольших размерах окна.
• Низкие требования к памяти — для работы достаточно скользящего окна размером 2-32 КБ.
• Отсутствие потерь — данные восстанавливаются без искажений.

Недостатки

• Ограниченная степень сжатия — по сравнению с более современными алгоритмами (LZMA, Deflate, BWT) LZSS даёт меньший коэффициент сжатия, особенно на больших объёмах данных.
• Чувствительность к размеру окна — слишком маленькое окно снижает эффективность, слишком большое — увеличивает время поиска и потребление памяти.
• Неэффективность на случайных данных — как и любой словарный метод, LZSS не сжимает случайные последовательности, а может даже увеличивать их размер.

Применение

LZSS нашёл применение в различных областях, где требуется быстрое сжатие с низким потреблением ресурсов:

• Архиваторы — PKZIP (версия 1.0, 1989), ARJ (1989), ZOO (1985) и другие использовали LZSS или его модификации.
• Файловые системы — MS-DOS 6.0 (1993) включала утилиту DoubleSpace (позже DriveSpace), которая использовала LZSS для сжатия дисков.
• Протоколы связи — ITU-T V.42bis (1990) — стандарт сжатия для модемов, основанный на LZSS.
• Встраиваемые системы — благодаря низким требованиям к памяти, LZSS часто применяется в прошивках микроконтроллеров, игровых консолях (например, Game Boy Advance, Nintendo DS) и в системах хранения данных.
• Форматы изображений — некоторые форматы растровой графики (например, PCX, TIFF) поддерживают сжатие по алгоритму LZSS.

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

Существует несколько модификаций LZSS, адаптированных под конкретные задачи:

• LZSS с адаптивным окном — размер окна может меняться в процессе сжатия в зависимости от характера данных.
• LZSS с предсказанием — используется для сжатия аудиоданных (например, в формате ADPCM).
• LZSS с кодированием Хаффмана — комбинация LZSS и статистического кодирования (например, в алгоритме Deflate, используемом в форматах PNG, ZIP, gzip). Deflate сначала применяет LZSS, а затем кодирует полученные литералы и ссылки с помощью кодов Хаффмана.
• LZSS с битовыми флагами — для уменьшения накладных расходов флаги группируются в блоки (например, по 8 элементов), что снижает долю служебной информации.

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

LZSS занимает промежуточное положение между LZ77 и более сложными алгоритмами. Он значительно эффективнее LZ77 за счёт отбрасывания коротких совпадений, но уступает LZMA и Deflate по степени сжатия.

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

• LZSS используется в протоколе V.42bis, который был стандартом для модемов со скоростью до 57,6 кбит/с.
• Алгоритм применяется в игровых консолях Nintendo Game Boy Advance и Nintendo DS для сжатия графики и звука.
• В 1990-х годах LZSS был основой многих коммерческих архиваторов, которые конкурировали между собой по скорости и степени сжатия.
• Современные реализации LZSS часто используют хеш-таблицы или деревья поиска для ускорения поиска совпадений в словаре.

Источники

• Storer J., Szymanski T. «Data Compression via Textual Substitution» // Journal of the ACM, 1982.
• Salomon D. «Data Compression: The Complete Reference» — 4th edition, Springer, 2007.
• Nelson M., Gailly J.-L. «The Data Compression Book» — 2nd edition, M&T Books, 1995.
• ITU-T Recommendation V.42bis (1990) — Data compression procedures for data circuit terminating equipment (DCE) using error correction procedures.
• PKWARE Inc. «APPNOTE.TXT — .ZIP File Format Specification» — версия 6.3.10, 2022.