WikiDer > Лемпель – Зив – Сторер – Шиманский

Lempel–Ziv–Storer–Szymanski

Лемпель – Зив – Сторер – Шиманский (ЛЗСС) это сжатие данных без потерь алгоритм, производная от LZ77, который был создан в 1982 году Джеймс А. Сторер и Томас Шимански. LZSS описан в статье «Сжатие данных посредством текстовой подстановки», опубликованной в Журнал 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 байта:

Пример с цветовой кодировкой, помогающий проиллюстрировать повторное использование повторяющейся информации для минимизации хранения.
Цветной пример сжатия 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, ЗООПАРК, LHarc используйте LZSS вместо LZ77 в качестве алгоритма первичного сжатия; кодирование буквальных символов и пар длина-расстояние варьируется, наиболее распространенным вариантом является Кодирование Хаффмана. Большинство реализаций происходит от всеобщее достояние Код 1989 года Харухико Окумура.[3][4] Версия 4 Библиотека Аллегро может кодировать и декодировать формат LZSS,[5] но функция была вырезана из версии 5. Game Boy Advance BIOS может декодировать слегка измененный формат LZSS.[6] Apple Mac OS X использует LZSS как один из методов сжатия кода ядра.[7]

Смотрите также

использованная литература

  1. ^ Сторер, Джеймс А .; Шимански, Томас Г. (октябрь 1982 г.). «Сжатие данных с помощью текстовой замены». Журнал ACM. 29 (4): 928–951. Дои:10.1145/322344.322346.
  2. ^ "10 историй, стоящих за рассказами доктора Сьюза". CNN. 23 января 2009 г.. Получено 2009-01-26.
  3. ^ Simtel.net зеркало. Реализация Харухико Окумуры 1989 года. Архивировано 3 февраля 1999 года.
  4. ^ Харухико Окумура. История сжатия данных в Японии. Архивировано 10 января 2016 года.
  5. ^ Харгривз, Шон [pl], и другие. Исходный код Allegro: lzss.c. Доступ 13 июля 2016 г.
  6. ^ Корт, Мартин. "GBATEK: Функции декомпрессии GBA BIOS". Архивировано из оригинал на 2013-03-23. Получено 2014-01-02.. Доступ 3 августа 2008 г.
  7. ^ "kext_tools / сжатие.c". GitHub. Открытый исходный код Apple. Получено 28 декабря 2019.