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).


Примечания
  1. НОУ ИНТУИТ | Лекция | Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива
  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.

Ссылки

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.