Lempel – Ziv – Storer – Szymanski ( LZSS ) - это алгоритм сжатия данных без потерь , производный от LZ77 , который был создан в 1982 году Джеймсом А. Сторером и Томасом Шимански . LZSS был описан в статье «Сжатие данных посредством текстовой замены», опубликованной в Journal of the ACM (1982, стр. 928–951). [1]
LZSS - это метод словарного кодирования . Он пытается заменить строку символов ссылкой на местоположение той же строки в словаре.
Основное различие между LZ77 и LZSS состоит в том, что в LZ77 словарная ссылка на самом деле может быть длиннее, чем строка, которую она заменяет. В LZSS такие ссылки опускаются, если длина меньше точки «безубыточности». Кроме того, LZSS использует однобитовые флаги, чтобы указать, является ли следующий фрагмент данных литералом (байтом) или ссылкой на пару смещение / длина.
Пример
Вот начало книги доктора Сьюза « Зеленые яйца и ветчина» с номерами знаков в начале строк для удобства. Green Eggs and Ham - оптимальный пример для иллюстрации сжатия LZSS, потому что сама книга содержит только 50 уникальных слов, несмотря на то, что количество слов составляет 170. [2] Таким образом, слова повторяются, но не последовательно.
0: Я Сэм 9: 10: Сэм, я 19: 20: Этот Сэм-я! 35: Этот Сэм-я-есть! 50: Мне не нравится 64: этот Сэм-я-есть! 79: 80: Вам нравятся зеленые яйца и ветчина?112:113: Мне они не нравятся, Сэм-я-есть.143: Не люблю зеленые яйца и ветчину.
Этот текст занимает 177 байт в несжатом виде. Предполагая, что точка безубыточности составляет 2 байта (и, следовательно, 2 пары байтов указатель / смещение) и один байт новой строки, этот текст, сжатый с помощью LZSS, становится длиной 94 байта:
0: Я Сэм 9:10: (5,3) (0,4)16:17: Это (4,4) -I-am! (19,16) Мне не нравится45: т (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 года Харухико Окумуры . [3] [4] Версия 4 библиотеки Allegro может кодировать и декодировать формат LZSS, [5] но эта функция была вырезана из версии 5. Game Boy Advance BIOS может декодировать слегка измененный формат LZSS. [6] Mac OS X от Apple использует LZSS как один из методов сжатия кода ядра. [7]
Смотрите также
- LZ77
- Лемпель – Зив – Велч (LZW)
Рекомендации
- ^ Сторер, Джеймс А .; Шиманский, Томас Г. (октябрь 1982 г.). «Сжатие данных с помощью текстовой замены». Журнал ACM . 29 (4): 928–951. DOI : 10.1145 / 322344.322346 .
- ^ «10 историй за рассказами доктора Сьюза» . CNN . 23 января 2009 . Проверено 26 января 2009 .
- ^ Зеркало Simtel.net. Реализация Харухико Окумуры 1989 года. Архивировано 3 февраля 1999 года.
- ^ Харухико Okumura. История сжатия данных в Японии. Архивировано 10 января 2016 года.
- ^ Харгривз, Шон , и др. Allegro исходный код: lzss.c . Доступ 13 июля 2016 г.
- ^ Корт, Мартин. «GBATEK: Функции декомпрессии GBA BIOS» . Архивировано из оригинала на 2013-03-23 . Проверено 2 января 2014 .. Доступ 3 августа 2008 г.
- ^ "kext_tools / сжатие.c" . GitHub . Открытый исходный код Apple . Проверено 28 декабря 2019 .