LZO

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].