LZO

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
LZO
Тип алгоритм сжатия[d]
Автор Маркус Оберхеймер (Markus Oberhumer)
Разработчик Markus F.X.J. Oberhumer[d]
Операционная система многоплатформенная
Языки интерфейса англ.
Первый выпуск 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
  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
  5. Compression — btrfs Wiki
  6. 1 2 Архивированная копия (недоступная ссылка). Дата обращения: 31 октября 2016. Архивировано 6 марта 2016 года.
  7. https://www.kernel.org/doc/Documentation/blockdev/zram.txt
  8. In-kernel memory compression, LWN.net
  9. 1 2 Raising Lazarus — The 20 Year Old Bug that Went to Mars / 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, Linux Kernel Documentation, (англ.)
  11. Longstanding Security Vulnerability Found in LZO Compression Algorithm | SecurityWeek.Com
  12. Twenty-year-old vulnerability in LZO finally patched / CSO Online

Ссылки[править | править код]