Лемпель–Зив–Сторер–Шимански
Lempel-Ziv-Storer-Szymanski ( LZSS ) — сжатия данных без потерь алгоритм , производный от LZ77 , который был создан в 1982 году Джеймсом А. Сторером и Томасом Шимански . LZSS был описан в статье «Сжатие данных посредством текстовой замены», опубликованной в журнале ACM (1982, стр. 928–951). [1]
LZSS — это метод словарного кодирования . Он пытается заменить строку символов ссылкой на местоположение той же строки в словаре.
Основное различие между LZ77 и LZSS заключается в том, что в LZ77 ссылка на словарь может быть длиннее, чем строка, которую она заменяет. В LZSS такие ссылки опускаются, если длина меньше точки «безубыточности». Кроме того, LZSS использует однобитовые флаги, чтобы указать, является ли следующий фрагмент данных литералом (байтом) или ссылкой на пару смещение/длина.
Пример
[ редактировать ]Вот начало книги доктора Сьюза « Зеленые яйца и ветчина» с номерами символов в начале строк для удобства. «Зеленые яйца и ветчина» — хороший пример, иллюстрирующий сжатие LZSS, поскольку сама книга содержит всего 50 уникальных слов, несмотря на то, что количество слов в ней составляет 170. [2] Таким образом, слова повторяются, но не подряд.
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.
Этот текст занимает 177 байт в несжатом виде. Предполагая, что точка безубыточности равна 2 байтам (и, следовательно, 2-байтовым парам указатель/смещение) и однобайтовым символам новой строки, этот текст, сжатый с помощью LZSS, становится длиной 95 байт:
0: I am Sam 9:10: (5,3) (0,4)16:17: That(4,4)-I-am!(19,15)32: I do not like46: t(21,14)50: Do you(58,5) green eggs and ham?79: (49,14) them,(24,9).(112,15)(92,18).
Примечание. Сюда не входят 11 байтов флагов, указывающих, является ли следующий фрагмент текста указателем или литералом. После его добавления длина текста становится 106 байт, что все равно короче исходных 177 байт.
Реализации
[ редактировать ]Многие популярные архиваторы, такие как ARJ , RAR , ZOO , LHarc, используют LZSS, а не LZ77 в качестве основного алгоритма сжатия; Кодирование литеральных символов и пар длина-расстояние различается, наиболее распространенным вариантом является кодирование Хаффмана . Большинство реализаций основано на общедоступном коде 1989 года Харухико Окумура . [3] [4] Версия 4 библиотеки Allegro может кодировать и декодировать формат LZSS. [5] но эта функция была вырезана из версии 5. BIOS Game Boy Advance может декодировать слегка измененный формат LZSS. [6] от Apple MacOS использует LZSS в качестве одного из методов сжатия кода ядра. [7]
См. также
[ редактировать ]- Лемпель – Зив – Велч (LZW)
Ссылки
[ редактировать ]- ^ Сторер, Джеймс А.; Шимански, Томас Г. (октябрь 1982 г.). «Сжатие данных посредством текстовой замены» . Журнал АКМ . 29 (4): 928–951. дои : 10.1145/322344.322346 .
- ^ «10 историй, лежащих в основе историй доктора Сьюза» . CNN . 23 января 2009 года . Проверено 26 января 2009 г.
- ^ Зеркало Simtel.net. Реализация Харухико Окумура, 1989 год . Архивировано 3 февраля 1999 года.
- ^ Харухико Окумура. История сжатия данных в Японии. Архивировано 10 января 2016 г.
- ^ Харгривз, Шон и др. Исходный код Аллегро: lzss.c. Доступ 13 июля 2016 г.
- ^ Корт, Мартин. «Функции декомпрессии GBATEK LZ» . www.problemkaputt.de . Проверено 7 июня 2022 г.
- ^ «kext_tools/compression.c» . Гитхаб . Apple с открытым исходным кодом . Проверено 28 декабря 2019 г.
сжатия данных Методы | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| без потерь |
| ||||||||
| с потерями |
| ||||||||
| Аудио |
| ||||||||
| Изображение |
| ||||||||
| Видео |
| ||||||||
| Теория | |||||||||
| Сообщество | |||||||||
| Люди | |||||||||
