LZSS (LZSS)

LZSS (Lempel-Ziv-Storer-Szymanski, Лемпель-Зив-Сторер-Шиманский^[1]) — алгоритм сжатия данных без потерь, производный от метода LZ77. Создан в 1982 году Джеймс Сторером и Томасом Шиманским. LZSS был описан в статье «Data compression via textual substitution» (сжатие данных через текстовые подстановки), опубликованной в журнале АСМ (1982, РР. 928—951).^[2]

LZSS является словарным методом сжатия. Он пытается заменить повторно встреченные последовательности символов на ссылку в словарь.

Основная разница между исходным LZ77 и LZSS состоит в том, что в методе LZ77 запись ссылки на словарь может быть длиннее, чем строка, которую она замещает (то есть запись такой ссылки делает сжатый фрагмент длиннее, чем несжатый). В методе LZSS подобные ссылки опускаются, в случае, если длина строки меньше некоторой настройки («break even»). Более того, LZSS применяет однобитный флаг для обозначения того, является ли следующий фрагмент сжатого потока литералом (байтом) или ссылкой в словарь (парой значений длина и смещение).

Реализации

Многие популярные архиваторы 1990-х — 2000-х, такие как PKZip, ARJ, RAR, ZOO, LHarc используют метод LZSS вместо LZ77 в качестве основного алгоритма упаковки данных. Схемы кодирования литералов и пар длина-смещение часто различаются, однако более популярным является применение энтропийного кодирования при помощи кода Хаффмана. Многие реализации основаны на коде Haruhiko Okumura от 1989 года.^[3]^[4]

Пример сжатия

Входной текст, 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).

Примечания

↑ НОУ ИНТУИТ | Лекция | Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива (неопр.). Дата обращения: 17 октября 2018. Архивировано 17 октября 2018 года.
↑ Storer, James A. Data Compression via Textual Substitution (неопр.) // Journal of the ACM. — 1982. — October (т. 29, № 4). — С. 928—951. — doi:10.1145/322344.322346.
↑ 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.

Ссылки

Исходный код реализации алгоритма LZSS

Алгоритм LZSS - Андрей Хохлов. Язык Context (Как создать язык программирования и транслятор), 26.06.2000
Методы сжатия изображений. Лекция 2: Словарные методы сжатия данных - Дмитрий Ватолин, МГУ, 10.10.2007
Алгоритмы сжатия и компрессии. LZSS Архивная копия от 18 октября 2018 на Wayback Machine
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 (англ.)

[1] НОУ ИНТУИТ | Лекция | Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива (неопр.). Дата обращения: 17 октября 2018. Архивировано 17 октября 2018 года.

[2] Storer, James A. Data Compression via Textual Substitution (неопр.) // Journal of the ACM. — 1982. — October (т. 29, № 4). — С. 928—951. — doi:10.1145/322344.322346.

[3] Simtel.net mirror. Haruhiko Okumura implementation of 1989. Archived on February 3, 1999.

[4] Haruhiko Okumura. History of Data Compression in Japan. Archived on January 10, 2016.

[1]

[2]

[3]

[4]