LZ4 (алгоритм сжатия)

LZ4

Автор (ы)
Разработчик ( s)	Янн Коллет
Первоначальный выпуск	24 апреля 2011 г. (2011-04-24)
Стабильный выпуск	1.9.2 / 20 августа 2019 г.; 14 месяцев назад (20.08.2019)
Репозиторий	github.com / lz4 / lz4
Написано на	C
Операционная система	Кросс-платформенная
Платформа	Portable
Тип	Сжатие данных
Лицензия	Упрощенная лицензия BSD
Веб-сайт	lz4.github.io / lz4 /

LZ4- алгоритм сжатия данных без потерь , ориентированный на скорость сжатия и распаковки. Он принадлежит к семейству схем побайтно-ориентированного сжатия LZ77.

• 1 Особенности
• 2 Дизайн
• 3 Реализация
• 4 Ссылки
• 5 Внешние ссылки

Алгоритм дает немного худшую степень сжатия, чем Алгоритм LZO - который, в свою очередь, хуже алгоритмов типа DEFLATE. Однако скорости сжатия аналогичны LZO и в несколько раз быстрее, чем DEFLATE, тогда как скорости распаковки могут быть значительно выше, чем LZO.

LZ4 использует только этап сопоставления словаря (LZ77), и в отличие от других распространенных алгоритмов сжатия не объединяет его с этапом энтропийного кодирования (например, кодирование Хаффмана в DEFLATE).

Алгоритм LZ4 представляет данные в виде последовательности последовательностей. Каждая последовательность начинается с однобайтового токена, разбитого на два 4-битных поля. Первое поле представляет количество литеральных байтов, которые должны быть скопированы в вывод. Второе поле представляет количество байтов для копирования из уже декодированного выходного буфера (0 представляет минимальную длину совпадения в 4 байта). Значение 15 в любом из битовых полей указывает, что длина больше, и есть дополнительный байт данных, который должен быть добавлен к длине. Значение 255 в этих дополнительных байтах указывает, что нужно добавить еще один байт. Следовательно, произвольная длина представлена ​​серией дополнительных байтов, содержащих значение 255. Строка литералов идет после токена и любых дополнительных байтов, необходимых для указания длины строки. За этим следует смещение, указывающее, как далеко в выходном буфере следует начать копирование. Дополнительные байты (если есть) длины совпадения прибывают в конец последовательности.

Сжатие может выполняться в потоке или блоками. Более высокая степень сжатия может быть достигнута, если приложить больше усилий для поиска наилучшего соответствия. Это приводит как к меньшему результату, так и к более быстрой декомпрессии.

Эталонная реализация на языке C Янна Колле лицензирована по лицензии BSD. Существуют порты и привязки на различных языках, таких как Java, C #, Python и т. Д. Базы данных, такие как Hadoop, используют этот алгоритм для быстрого сжатия. LZ4 также изначально был реализован в ядре Linux 3.11. Реализации файловой системы ZFS в FreeBSD, Illumos, ZFS в Linux и ZFS-OSX поддерживают алгоритм LZ4 для сжатия на лету. Linux поддерживает LZ4 для SquashFS начиная с версии 3.19-rc1. LZ4 также реализован Янном Колле в новом архиваторе Zstd.

• Официальный сайт