LZO: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правка
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
мНет описания правки
 
(не показано 25 промежуточных версий 14 участников)
Строка 1: Строка 1:
{{Карточка программы
⚫
'''LZO''' это [[алгоритм]] [[сжатие данных|сжатия данных]], разработанный для достижения максимальной скорости распаковки. LZO — это аббревиатура от фамилий разработчиков: Lempel-Ziv-Oberhumer (Лемпель-Зив-Оберхеймер). Это [[сжатие без потерь|алгоритм сжатия без потерь]] и его базовая реализация может работать в многопоточной среде.
| название =
| автор = Маркус Оберхеймер (Markus Oberhumer)
| языки интерфейса = англ.
| операционные системы = многоплатформенная
| написана на =
| первый выпуск = 1997
| последняя версия = 2.10
| дата последней версии = 1 марта 2017
| состояние =
| лицензия = GPLv2
| сайт = www.oberhumer.com/opensource/lzo/
}}
⚫
'''LZO''' (аббр. от ''Lempel-Ziv-Oberhumer'' — Лемпель-Зив-Оберхеймер) — [[алгоритм]] [[сжатие данных|сжатия данных]], разработанный для достижения максимальной скорости распаковки в середине 1990-х годов. Алгоритм [[сжатие без потерь|сжимает данные без потерь]] и его базовая реализация поддерживает многопоточное исполнение.


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


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


Высокая скорость алгоритма позволяет встраивать его в различные высокопроизводительные системы, например, в СУБД<ref>{{Cite web |url=http://docs.aws.amazon.com/redshift/latest/dg/lzo-encoding.html |title=LZO Encoding — Amazon Redshift<!-- Заголовок добавлен ботом --> |access-date=2016-10-31 |archive-date=2016-11-24 |archive-url=https://web.archive.org/web/20161124005015/http://docs.aws.amazon.com/redshift/latest/dg/lzo-encoding.html |deadlink=no }}</ref>, системы обработки данных<ref>{{Cite web |url=https://blog.cloudera.com/blog/2009/06/parallel-lzo-splittable-compression-for-hadoop/ |title=Parallel LZO: Splittable Compression for Apache Hadoop — Cloudera Engineering Blog<!-- Заголовок добавлен ботом --> |accessdate=2016-10-31 |archiveurl=https://web.archive.org/web/20161101102511/https://blog.cloudera.com/blog/2009/06/parallel-lzo-splittable-compression-for-hadoop/ |archivedate=2016-11-01 |deadlink=yes }}</ref><ref>[http://dl.acm.org/citation.cfm?id=2371485&dl=ACM&coll=DL A guide to using LZO compression in Hadoop<!-- Заголовок добавлен ботом -->]</ref>, файловые системы<ref>{{Cite web |url=http://www.phoronix.com/scan.php?page=article&item=btrfs_lzo_2638&num=1 |title=Btrfs LZO Compression Performance — Phoronix<!-- Заголовок добавлен ботом --> |access-date=2016-10-31 |archive-date=2016-04-14 |archive-url=https://web.archive.org/web/20160414212759/http://www.phoronix.com/scan.php?page=article&item=btrfs_lzo_2638&num=1 |deadlink=no }}</ref><ref>{{Cite web |url=https://btrfs.wiki.kernel.org/index.php/Compression |title=Compression — btrfs Wiki<!-- Заголовок добавлен ботом --> |access-date=2016-10-31 |archive-date=2017-06-12 |archive-url=https://web.archive.org/web/20170612231906/https://btrfs.wiki.kernel.org/index.php/Compression |deadlink=no }}</ref>, для распаковки ядер ОС при загрузке<ref name=autogenerated1>{{Cite web |url=http://events.linuxfoundation.org/sites/events/files/lcjpcojp13_klee.pdf |title=Архивированная копия |accessdate=2016-10-31 |archiveurl=https://web.archive.org/web/20160306095636/http://events.linuxfoundation.org/sites/events/files/lcjpcojp13_klee.pdf |archivedate=2016-03-06 |deadlink=yes }}</ref> (в том числе Android-устройствах Samsung), системы [[zRam|сжатой памяти]]<ref>{{Cite web |url=https://www.kernel.org/doc/Documentation/blockdev/zram.txt |title=Архивированная копия |access-date=2016-10-31 |archive-date=2016-03-22 |archive-url=https://web.archive.org/web/20160322045542/https://www.kernel.org/doc/Documentation/blockdev/zram.txt |deadlink=no }}</ref><ref>[https://lwn.net/Articles/545244/ In-kernel memory compression] {{Wayback|url=https://lwn.net/Articles/545244/ |date=20211009005751 }}, LWN.net</ref>. Применялся на нескольких планетах<ref name="автоссылка1">[http://blog.securitymouse.com/2014/06/raising-lazarus-20-year-old-bug-that.html Raising Lazarus — The 20 Year Old Bug that Went to Mars] {{Wayback|url=http://blog.securitymouse.com/2014/06/raising-lazarus-20-year-old-bug-that.html |date=20161022162456 }} / The Lab Mouse Security research blog. «LZO algorithm has gone to the planet Mars on NASA devices multiple times»</ref>.
LZO supports overlapping compression and in-place decompression.


Алгоритм является одним из самых быстрых по скорости распаковки наряду с созданным на его основе методом [[LZ4]] (LZ4 HC), а также рядом других алгоритмов сжатия: [[Snappy (библиотека)|Snappy]], [[FastLZ]], LZF<ref name=autogenerated1 />.
LZO is a block compression algorithm - it compresses and decompresses
a block of data. Block size must be the same for compression
and decompression.


Среди недостатков отмечают отсутствие единой спецификации на формат сжатого потока<ref>[https://www.kernel.org/doc/Documentation/lzo.txt LZO stream format as understood by Linux’s LZO decompressor] {{Wayback|url=https://www.kernel.org/doc/Documentation/lzo.txt |date=20160609231314 }}, Linux Kernel Documentation,{{ref-en}}</ref>. В оригинальном коде распаковки до 2014 года существовала ошибка целочисленного переполнения. Широкое использование алгоритма привело к потенциальной уязвимости множества проектов<ref name="автоссылка1" /><ref>{{Cite web |url=http://www.securityweek.com/longstanding-security-vulnerability-found-lzo-compression-algorithm |title=Longstanding Security Vulnerability Found in LZO Compression Algorithm {{!}} SecurityWeek.Com<!-- Заголовок добавлен ботом --> |access-date=2016-10-31 |archive-date=2016-11-01 |archive-url=https://web.archive.org/web/20161101105706/http://www.securityweek.com/longstanding-security-vulnerability-found-lzo-compression-algorithm |deadlink=no }}</ref><ref>[http://www.csoonline.com/article/2375206/data-protection/twenty-year-old-vulnerability-in-lzo-finally-patched.html Twenty-year-old vulnerability in LZO finally patched] {{Wayback|url=http://www.csoonline.com/article/2375206/data-protection/twenty-year-old-vulnerability-in-lzo-finally-patched.html |date=20161101104234 }} / CSO Online</ref>.
LZO compresses a block of data into matches (a sliding dictionary)
and runs of non-matching literals. LZO takes care about long matches
and long literal runs so that it produces good results on highly
redundant data and deals acceptably with non-compressible data.

When dealing with uncompressible data, LZO expands the input
block by a maximum of 1/64th when measured over at least 1k.

LZO is also reported to work under [[Win32]], [[AIX]], ConvexOS, [[IRIX]], [[Mac OS]], [[Palm OS]],
PS1 ([[Sony PlayStation]]), [[Solaris Operating Environment|Solaris]], [[SunOS]], TOS (Atari ST) and VxWorks.

-->


== См. также ==
== См. также ==
Строка 38: Строка 37:
* [[LZW]]
* [[LZW]]
* [[LZMA]]
* [[LZMA]]
* [[UPX]]
* [[LZ4]]

== Примечания ==
{{примечания}}


== Ссылки ==
== Ссылки ==
* [http://www.oberhumer.com/opensource/lzo/ Официальная страница алгоритма]
* [https://web.archive.org/web/20120625020414/http://www.lzop.de/ Официальная страница алгоритма LZO]{{ref-en}}
* [https://www.lzop.org/ Сайт утилиты lzop], 2010{{ref-en}}
* [http://www.compression-links.info/LZO Список ресурсов по LZO]
** [https://www.lzop.org/lzop_man.php Документация lzop], 1996—2010{{ref-en}}
* [http://www.lzop.de/ LZO/LZOP бинарные коды]
⚫
{{Методы сжатия}}

⚫
{{методы сжатия}}


⚫
[[Категория:Алгоритмы сжатия с использованием словаря]]
[[Категория:Сжатие данных]]
[[Категория:Сжатие данных]]
⚫
[[Категория:Алгоритмы сжатия с использованием словаря]]

[[de:Lempel-Ziv-Oberhumer]]
[[en:Lempel–Ziv–Oberhumer]]
[[fr:Lempel-Ziv-Oberhumer]]
[[sl:LZO]]
[[zh:LZO]]

Текущая версия от 17:34, 13 февраля 2023

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

Ссылки

[править | править код]
Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=LZO&oldid=128495192