liblzg

liblzg
Стабильная версия	1.0.10 / 29 ноября 2018 г .; 5 лет назад
Репозиторий	github .с /mbitsnbites /libzg ;
Написано в	C , Паскаль , Lua , язык Ассемблера , JavaScript
Операционная система	Кросс-платформенный
Тип	Сжатие данных
Лицензия	лицензия zlib
Веб-сайт	liblzg .bitsnbites .Евросоюз

liblzg — библиотека сжатия для сжатия данных без потерь . Он реализует алгоритм, который является разновидностью алгоритма LZ77 , называемого алгоритмом LZG, основной целью которого является обеспечение очень простого и быстрого метода декодирования. Одной из ключевых особенностей алгоритма является то, что он не требует памяти во время распаковки. Библиотека программного обеспечения является свободным программным обеспечением , распространяемым по лицензии zlib .

Алгоритм

Если в потоке несжатых данных обнаруживается повторяющаяся серия байтов (повторяющаяся строка), то обратная ссылка вставляется , ссылающаяся на предыдущее местоположение этой идентичной строки. Закодированное совпадение с более ранней строкой состоит из длины (3–128 байт) и расстояния (1–526 341 байт). Уровень сжатия можно контролировать, указав максимальное расстояние, на котором будет осуществляться поиск повторяющихся строк (это размер скользящего окна ).

Формат данных

Формат данных состоит из заголовка, за которым следуют сжатые данные. Заголовок содержит идентификатор и служебную информацию, такую как размеры сжатых и распакованных данных, а также 32-битную контрольную сумму (вариант контрольной суммы Флетчера ).

Сжатые данные начинаются с четырех байтов, идентифицирующих четыре уникальных 8-битных символа маркера ( m1 , m2 , m3 и m4 ). Они используются для отделения буквальных байтов данных от различных форм парного кодирования длины-расстояния .

Любой символ, который не является байтом маркера, считается литеральным байтом и будет скопирован в распакованный буфер данных как есть. Однако если декодер встретит любой из четырех байтов маркера, он декодирует пару длина-расстояние , которая используется в качестве обратной ссылки в ранее распакованные данные.

Байты маркера интерпретируются следующим образом (% обозначает двоичное число):

Общий экземпляр (м1)

m1 представляет собой наиболее общую форму операции копирования и занимает четыре байта в потоке сжатых данных:

м1	%оооолллл	%мммммммм	%nnnnnnnn

...где длина= DECODELENGTH(%lllll+2) и смещение= %ооомммммммммнннннн + 2056 .

Средний экземпляр (м2)

m2 — это более короткая форма операции копирования, занимающая три байта в потоке сжатых данных:

м2	%оооолллл	%мммммммм

...где длина= DECODELENGTH(%lllll+2) и смещение= %оооммммммммм + 8 .

Короткий экземпляр (м3)

m3 требует всего два байта и используется для коротких длин, близких к маркеру:

m3	%lloooooo

...где длина= %ll+3 и смещение= %ооооо + 8 .

Близкая копия (м4)

m4 требует всего два байта и используется для соседних копий (включая RLE , когда смещение равно 1):

м4	%оооолллл

...где длина= DECODELENGTH(%lllll+2) и смещение= %ооо + 1 .

Буквальная копия

В особом случае, если за любым из символов маркера следует нулевой байт (0), сам символ маркера записывается в распакованный буфер.

Нелинейное кодирование длины

The Функция DECODELENGTH реализует нелинейное сопоставление числа в диапазоне 3–33 с числом в диапазоне 3–128 согласно следующей таблице:

Параметр длины, L (3-33)	Декодированная длина (3–128)
33	128
32	72
31	48
30	35
<30	л

В худшем случае рост данных

В качестве символов-маркеров выбираются четыре наименее общих символа в потоке несжатых данных (с вероятностью не более ${\tfrac {1}{256}}$ каждый), а для кодирования одного появления символа-маркера требуется два байта, сжатые данные могут увеличиться не более чем на ${\tfrac {4}{256}}$ < 1,6% по сравнению с распакованными данными (худший случай).

Библиотека liblzg компенсирует это, используя простой режим копирования 1:1, если кодировщик определяет, что сжатые данные будут больше, чем исходные несжатые данные. Следовательно, на практике максимальный рост данных составляет 0% (плюс размер заголовка данных, который составляет 16 байт).

Реализации

Алгоритмы сжатия и распаковки реализованы в библиотеке с открытым исходным кодом, написанной на языке программирования C. Также доступно несколько альтернативных реализаций алгоритма распаковки (например, на JavaScript и 8-битном языке ассемблера ).

См. также

Внешние ссылки

домашняя страница liblzg