LZSS (, Лемпель-Зив-Сторер-Шиманский) — алгоритм сжатия данных без потерь, производный от метода 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 года.Simtel.net mirror. Haruhiko Okumura implementation of 1989. Archived on February 3, 1999.Haruhiko Okumura. History of Data Compression in Japan. Archived on January 10, 2016.
Пример сжатия Входной текст, 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).
Примечания
Ссылки Алгоритм LZSS, ИТМО, 2014 Ливак Е.Н., Обзор алгоритмов сжатия без потерь. Алгоритм LZSS, Исходный код реализации алгоритма LZSS Алгоритм LZSS - Андрей Хохлов. Язык Context (Как создать язык программирования и транслятор), 26.06.2000 Методы сжатия изображений. Лекция 2: Словарные методы сжатия данных - Дмитрий Ватолин, МГУ, 10.10.2007 Алгоритмы сжатия и компрессии. LZSS ftp://ftp.kemsu.ru/incoming/M-134/%D1%EB%E0%E9%E4%FB%20%CC%D1%C8%20%E1%E5%E7%20%EF%EE%F2%E5%F0%FC.pdf#page=80 LZSS and LZRW1-A, Wikibooks Data Compression/Dictionary compression
Категория:Алгоритмы сжатия без потерь