LZ4 (kompresní algoritmus) - LZ4 (compression algorithm)

LZ4
Původní autořiYann Collet
VývojářiYann Collet
První vydání24.dubna 2011 (2011-04-24)
Stabilní uvolnění
1.9.2 / 20. srpna 2019; Před 15 měsíci (2019-08-20)[1]
Úložiště
Upravte to na Wikidata
NapsánoC
Operační systémCross-platform
PlošinaPřenosný
TypKomprese dat
LicenceZjednodušená licence BSD
webová stránkalz4.github.io/ lz4/ Upravte to na Wikidata
Formát rámu LZ4
Magické číslo04 22 4d 18[2]
Typ formátuKomprese dat
webová stránkahttps://github.com/lz4/lz4/blob/master/doc/lz4_Frame_format.md

LZ4 je bezztrátová komprese dat algoritmus který je zaměřen na rychlost komprese a dekomprese. Patří k LZ77 rodina bytově orientovaných kompresních schémat.

Funkce

Algoritmus poskytuje o něco horší kompresní poměr než LZO algoritmus - který je zase horší než algoritmy jako DEFLATE. Rychlosti komprese jsou však podobné LZO a několikrát rychlejší než DEFLATE, zatímco rychlosti dekomprese mohou být výrazně vyšší než LZO.[3]

Design

LZ4 používá pouze fázi porovnávání slovníků (LZ77) a na rozdíl od jiných běžných kompresních algoritmů ji nekombinuje s entropické kódování fáze (např. Huffmanovo kódování v DEFLATE).[4][5]

Algoritmus LZ4 představuje data jako sérii sekvencí. Každá sekvence začíná jednobajtovým tokenem, který je rozdělen na dvě 4bitová pole. První pole představuje počet doslovných bajtů, které se mají zkopírovat na výstup. Druhé pole představuje počet bajtů, které se mají zkopírovat z již dekódované výstupní vyrovnávací paměti (přičemž 0 představuje minimální délku shody 4 bajty). Hodnota 15 v kterémkoli z bitových polí označuje, že délka je větší a k délce je přidán další bajt dat. Hodnota 255 v těchto extra bajtech označuje, že je třeba přidat ještě další bajt. Proto jsou libovolné délky reprezentovány řadou dalších bytů obsahujících hodnotu 255. Řetězec literálů přichází za tokenem a případnými dalšími bajty potřebnými k označení délky řetězce. Následuje posun, který označuje, jak daleko zpět ve výstupní vyrovnávací paměti se má začít kopírovat. Další bajty (pokud existují) délky shody přicházejí na konec sekvence.[6][7]

Komprese může být provedena v proudu nebo v blocích. Vyšších kompresních poměrů lze dosáhnout investováním většího úsilí do hledání nejlepších shod. Výsledkem je menší výstup a rychlejší dekomprese.

Implementace

Referenční implementace v jazyce C od Yanna Colleta je licencována na základě licence BSD. K dispozici jsou porty a vazby v různých jazycích, jako je Java, C #, Python atd.[8] Databáze jako Hadoop použijte tento algoritmus pro rychlou kompresi. LZ4 byl také nativně implementován v Linuxové jádro 3.11.[9] FreeBSD, Illumos, ZFS v systému Linux a implementace souborového systému ZFS ZFS-OSX podporují algoritmus LZ4 pro okamžitou kompresi.[10][11][12][13] Linux podporuje LZ4 pro SquashFS od 3.19-rc1.[14] LZ4 je implementován také v novějších verzích Zstd archivátor Yann Collet.

Reference

  1. ^ „LZ4 v1.9.2“. Github. 30. srpna 2019. Citováno 30. srpna 2019.
  2. ^ Collet, Yann. "Popis formátu rámečku LZ4". Citováno 7. října 2020.
  3. ^ Michael Larabel (2013-01-28). „Podpora komprese jádra Linuxu pomocí LZ4“. Phoronix. Citováno 2015-08-28.
  4. ^ Collet, Yann (2019-03-30). "Popis formátu bloku LZ4". GitHub. Citováno 2020-07-09. Neexistuje žádný back-end kodéru entropie ani rámovací vrstva.
  5. ^ DEFLATE Specifikace formátu komprimovaných dat verze 1.3. IETF. doi:10.17487 / RFC1951. RFC 1951. Citováno 2020-07-09.
  6. ^ Yann Collet (2011-05-26). „Komprese dat v reálném čase“. Citováno 2015-08-28.
  7. ^ ticki (2016-10-25). "Jak funguje LZ4". Citováno 2017-06-29.
  8. ^ Algoritmus extrémně rychlé komprese http://www.lz4.org na GitHub
  9. ^ Jonathan Corbet (19. 7. 2013). "Vývoj jádra". LWN.net. Citováno 2015-08-28.
  10. ^ „Poznámky k verzi FreeBSD 9.2-RELEASE“. FreeBSD. 2013-11-13. Citováno 2015-08-28.
  11. ^ "LZ4 Compression". ilumos. Citováno 2015-08-28.
  12. ^ Podpora komprese Illumos # 3035 LZ4 v ZFS a GRUB na GitHub
  13. ^ "Vlastnosti: komprese lz4". OpenZFS. Citováno 2015-08-28.
  14. ^ Phillip Lougher (2014-11-27). "Squashfs: Přidat možnost konfigurace komprese LZ4". Citováno 2015-08-28.

externí odkazy