LZSS (Lempel-Ziv-Storer-Szymanski, Лемпель-Зив-Сторер-Шиманский) — алгоритм сжатия данных без потерь, производный от метода LZ77. Создан в 1982 году Джеймс Сторером и Томасом Шиманским. LZSS был описан в статье «Data compression via textual substitution» (сжатие данных через текстовые подстановки), опубликованной в журнале АСМ (1982, РР. 928—951).
LZSS является словарным методом сжатия. Он пытается заменить повторно встреченные последовательности символов на ссылку в словарь.
Основная разница между исходным LZ77 и LZSS состоит в том, что в методе LZ77 запись ссылки на словарь может быть длиннее, чем строка, которую она замещает (то есть запись такой ссылки делает сжатый фрагмент длиннее, чем несжатый). В методе LZSS подобные ссылки опускаются, в случае, если длина строки меньше некоторой настройки («break even»). Более того, LZSS применяет однобитный флаг для обозначения того, является ли следующий фрагмент сжатого потока литералом (байтом) или ссылкой в словарь (парой значений длина и смещение).
Реализации
Многие популярные архиваторы 1990-х — 2000-х, такие как PKZip, ARJ, RAR, ZOO, LHarc используют метод LZSS вместо LZ77 в качестве основного алгоритма упаковки данных. Схемы кодирования литералов и пар длина-смещение часто различаются, однако более популярным является применение энтропийного кодирования при помощи кода Хаффмана. Многие реализации основаны на коде Haruhiko Okumura от 1989 года.
Пример сжатия
Входной текст, 177 байтов:
0: I am Sam 9: 10: Sam I am 19: 20: That Sam-I-am! 35: That Sam-I-am! 50: I do not like 64: that Sam-I-am! 79: 80: Do you like green eggs and ham? 112: 113: I do not like them, Sam-I-am. 143: I do not like green eggs and ham.При минимальном совпадении в два байта получаем 94 байта (без учета 12 байтов флагов типа фрагмента). В скобках указаны пары (смещение, длина):
0: I am Sam 9: 10: (5,3) (0,4) 16: 17: That(4,4)-I-am!(19,16)I do not like 45: t(21,14) 49: Do you(58,5) green eggs and ham? 78: (49,14) them,(24,9).(112,15)(92,18).