LZO

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
LZO
Тип алгоритм сжатия[вд]
Автор Маркус Оберхеймер (Markus Oberhumer)
Операционная система многоплатформенная
Языки интерфейса англ.
Первый выпуск 1997
Последняя версия 2.10 (1 марта 2017)
Лицензия GPLv2
Сайт oberhumer.com/opensource…

LZO (аббр. от Lempel-Ziv-Oberhumer — Лемпель-Зив-Оберхеймер) — алгоритм сжатия данных, разработанный для достижения максимальной скорости распаковки в середине 1990-х годов. Алгоритм сжимает данные без потерь и его базовая реализация поддерживает многопоточное исполнение.

Свободной программой, реализующей LZO, является lzop. Исходная библиотека была написана на ANSI C и доступна под лицензией GPL. Также существуют реализации LZO на языках Ассемблер (x86), Perl, Python, Java и .NET. Код написан Маркусом Оберхеймером (Markus F. X. J. Oberhumer).

Библиотека LZO реализует несколько алгоритмов со следующими особенностями.

  • Распаковка простая и очень быстрая.
  • Для декомпрессии не требуется дополнительной памяти, помимо буферов для сжатых и распаковываемых данных.
  • Сжатие также очень быстрое.
  • При сжатии требуется 64 КБ памяти.
  • Можно достичь дополнительного сжатия, потратив несколько больше времени при сжатии. При этом скорость декомпрессии не уменьшается.
  • Существует несколько уровней сжатия (с разными требования по скорости).
  • В частности, реализован вариант алгоритма, которому требуется всего 8 КБ памяти для сжатия.
  • Алгоритм безопасно применять в многопоточной среде.
  • Алгоритм сжимает и распаковывает данные без потерь.

Высокая скорость алгоритма позволяет встраивать его в различные высокопроизводительные системы, например, в СУБД[1], системы обработки данных[2][3], файловые системы[4][5], для распаковки ядер ОС при загрузке[6] (в том числе Android-устройствах Samsung), системы сжатой памяти[7][8]. Применялся на нескольких планетах[9].

Алгоритм является одним из самых быстрых по скорости распаковки наряду с созданным на его основе методом LZ4 (LZ4 HC), а также рядом других алгоритмов сжатия: Snappy, FastLZ, LZF[6].

Среди недостатков отмечают отсутствие единой спецификации на формат сжатого потока[10]. В оригинальном коде распаковки до 2014 года существовала ошибка целочисленного переполнения. Широкое использование алгоритма привело к потенциальной уязвимости множества проектов[9][11][12].

Примечания

[править | править код]
  1. LZO Encoding — Amazon Redshift. Дата обращения: 31 октября 2016. Архивировано 24 ноября 2016 года.
  2. Parallel LZO: Splittable Compression for Apache Hadoop — Cloudera Engineering Blog. Дата обращения: 31 октября 2016. Архивировано из оригинала 1 ноября 2016 года.
  3. A guide to using LZO compression in Hadoop
  4. Btrfs LZO Compression Performance — Phoronix. Дата обращения: 31 октября 2016. Архивировано 14 апреля 2016 года.
  5. Compression — btrfs Wiki. Дата обращения: 31 октября 2016. Архивировано 12 июня 2017 года.
  6. 1 2 Архивированная копия. Дата обращения: 31 октября 2016. Архивировано из оригинала 6 марта 2016 года.
  7. Архивированная копия. Дата обращения: 31 октября 2016. Архивировано 22 марта 2016 года.
  8. In-kernel memory compression Архивная копия от 9 октября 2021 на Wayback Machine, LWN.net
  9. 1 2 Raising Lazarus — The 20 Year Old Bug that Went to Mars Архивная копия от 22 октября 2016 на Wayback Machine / The Lab Mouse Security research blog. «LZO algorithm has gone to the planet Mars on NASA devices multiple times»
  10. LZO stream format as understood by Linux’s LZO decompressor Архивная копия от 9 июня 2016 на Wayback Machine, Linux Kernel Documentation, (англ.)
  11. Longstanding Security Vulnerability Found in LZO Compression Algorithm | SecurityWeek.Com. Дата обращения: 31 октября 2016. Архивировано 1 ноября 2016 года.
  12. Twenty-year-old vulnerability in LZO finally patched Архивная копия от 1 ноября 2016 на Wayback Machine / CSO Online