Войти
Lempel – Ziv – Storer – Szymanski (LZSS ) - без потерь алгоритм сжатия данных , производный от LZ77, который был создан в 1982 году и. LZSS был описан в статье «Сжатие данных с помощью текстовой замены», опубликованной в Journal of the ACM (1982, стр. 928–951).
LZSS - это метод словарного кодирования. Он пытается заменить строку символов ссылкой на местоположение той же строки в словаре.
Основное различие между LZ77 и LZSS заключается в том, что в LZ77 ссылка на словарь может быть длиннее, чем строка, которую она заменяет. В LZSS такие ссылки опускаются, если длина меньше точки «безубыточности». Кроме того, LZSS использует однобитовые флаги, чтобы указать, является ли следующий фрагмент данных литералом (байтом) или ссылкой на пару смещение / длина.
Вот начало книги доктора Сьюза Green Eggs and Ham, с номерами знаков в начале строк для удобства. Green Eggs and Ham - оптимальный пример для иллюстрации сжатия LZSS, поскольку сама книга содержит только 50 уникальных слов, несмотря на то, что количество слов составляет 170. Таким образом, слова повторяются, но не последовательно.
0: Я Сэм 9: 10: Сэм Я 19: 20: Этот Сэм-я! 35: Этот Сэм-я-есть! 50: Мне не нравится 64: этот Сэм-я! 79: 80: Тебе нравятся зеленые яйца и ветчина? 112: 113: Я не люблю их, Сам-я. 143: Не люблю зеленые яйца и ветчину.
Этот текст занимает 177 байт в несжатом виде. Если предположить, что точка безубыточности составляет 2 байта (и, следовательно, 2 байта пары указатель / смещение), и один байт новой строки, этот текст, сжатый с помощью LZSS, становится длиной 94 байта:
Цветовой пример сжатия LZSS в действии. 0: Я Сэм 9: 10: (5,3) (0,4) 16: 17: Это (4,4) -Я-есть! (19,16) Мне не нравится 45: t (21,14) 49: Вы (58,5) зеленые яйца и ветчину? 78: (49,14) их, (24,9). (112,15) (92,18).
Примечание: сюда не входят 12 байтов флагов, указывающих, является ли следующий фрагмент текста указателем или литералом. При его добавлении длина текста становится 106 байт, что по-прежнему меньше исходных 177 байт.
Многие популярные архиваторы, такие как PKZip, ARJ, RAR, ZOO, LHarc использовать LZSS, а не LZ77 в качестве основного алгоритма сжатия; кодирование буквальных символов и пар длина-расстояние варьируется, наиболее распространенным вариантом является кодирование Хаффмана. Большинство реализаций основано на коде общественного достояния 1989 года, созданном Харухико Окумура. Версия 4 библиотеки Allegro может кодировать и декодировать формат LZSS, но эта функция была вырезана из версии 5. BIOS Game Boy Advance может декодировать слегка измененный формат LZSS. Apple Mac OS X использует LZSS как один из методов сжатия кода ядра.
