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

Ссылки