Srovnání linuxových kompresorů dat: různé kompresní poměry a rychlost

Deflate

Asi nejznámější kompresní metoda je Deflate, který využívá například nástroj gzip v souborech .gz. Autorem metody Deflate byl geniální americký programátor Phil Katz, který ji uvedl v roce 1992 ve svém archivačním programu PKZIP. Interně se jedná o kombinaci slovníkové kompresní metody LZ77 a Huffmanova kódování.

Před kompresí jsou vstupní data rozdělena do bloků různé velikosti. Pro každý blok zvlášť jsou pak sestaveny Huffmanovy tabulky. Rozdělení do bloků při kompresi je složitá optimalizační úloha, kterou řeší nástroj Zopfli. Ten zvyšuje kompresní poměr za cenu extrémně pomalé rychlosti komprese.

bzip2 a bzip3

Nástroj bzip2 byl poprvé vydán v roce 1996 britským programátorem Julianem Sewardem. Je založen na Burrowsově–Wheelerově transformaci (BWT), move-to-front transformaci (MTF) a Huffmanově kódování. Bzip2 komprimuje většinu souborů efektivněji než Deflate ( .zip, .gz), ale je znatelně pomalejší.

Duchovním nástupcem bzip2 je bzip3, který poprvé vyšel v roce 2022. Dosahuje ještě vyšších kompresních poměrů než bzip2, ale cenou je další snížení rychlosti. Je založen na Burrowsově–Wheelerově transformaci, metodě LZ+P a aritmetickém kodéru.

LZMA (xz)

Dalšími široce používanými nástroji jsou xz a lzma z balíku XZ Utils. Nástroj xz komprimuje data metodou LZMA2. Naproti tomu nástroj lzma používá metodu LZMA. To je algoritmus vyvinutý programátorem Igorem Pavlovem pro jeho archivační program 7-Zip v roce 1999.

Skládá se z metody LZ77, Markovových řetězců a aritmetického kodéru (range coder). Co se týče kompresního poměru, rozdíl mezi metodami LZMA a LZMA2 je zanedbatelný.

LZ4, lzop

LZ4 se slovníková metoda z roku 2011 zaměřená na rychlost komprese a dekomprese. Implementuje LZ77 a na rozdíl od jiných algoritmů nepoužívá entropické kódování. Existuje odnož LZ4 HC, která dosahuje vyšších kompresních poměrů za cenu nižší rychlosti; bitstream je plně kompatibilní s LZ4.

LZ4 je srovnatelný s metodou LZO (Lempel–Ziv–Oberhumer), kterou implementuje nástroj lzop. Ta je zaměřena na rychlost dekomprese, ale nedosahuje takových rychlostí jako LZ4. lzop byl poprvé vydán v roce 1997 a nemá oficiální specifikaci.

Brotli, Zstandard

Nástroj Brotli byl vyvinut v roce 2013 společností Google. Používá kombinaci LZ77, Huffmanova kódování a kontextového modelování. Měl by poskytovat lepší kompresní poměr než Deflate. Nástroj je zaměřen na kompresi souborů HTML, CSS a JavaScript.

Podobně byl v roce 2015 společností Facebook uvolněn nástroj Zstandard (Zstd). Je to kombinace LZ77 a entropického kódování. Běžně dosahuje podobných kompresních poměrů jako Deflate, ale za to je rychlejší. Při maximální kompresi dosahuje Zstd kompresních poměru blízko LZMA. Oproti knihovnám implementující Deflate dosahuje vyšší kompresní i dekompresní rychlosti.

ZPAQ

Mezi méně známé nástroje pro kompresi dat patří zpaq, který je určen pro inkrementální zálohy. Jedná se o archivační program, který umí soubory do archivu pouze přidávat. Umí se ale vrátit to předchozího stavu a načíst starší verze souborů.

Jako předzpracování umožňuje zpaq použít metody LZ77, BWT a E8E9. Pro vlastní kompresi používá kontextové modelování. Dosažené kompresní poměry jsou velmi vysoké. Nicméně rychlost komprese i dekomprese je velmi nízká. Bohužel poslední vydání je z roku 2016 a aktivní vývoj již neprobíhá.

Srovnání různých metod

Srovnání probíhalo na datasetu Silesia, který sestával z následujících souborů.

Nyní se podívejme na srovnání maximálně dosaženého kompresního poměru (více je lépe).

Co z tabulky vyčteme? Nástroj bzip3 je velmi efektivní. Ve většině případů ho ale překonal zpaq. Dále vidíme, že bzip2, brotli, zstd, lzma a xz jsou také slušně účinné. Pak tu máme Deflate, u kterého vidíme značný skok. Takže gzip ani Zopfli již dnes nejsou příliš účinné.

Pak tu máme LZ4 a lzop, u nichž vidíte, že mají velmi malý kompresní poměr, ale to je účel. My chceme, aby LZ4 byla velmi rychlá při kompresi a dekompresi za cenu méně účinné komprese. Všimněte si, která data se nám dobře komprimují. Je to hlavně soubor ve formátu XML, tedy HTML soubory, na nichž lze dosáhnout vysokého kompresního poměru. Ostatní soubory se komprimují o poznání hůře, ale typicky dosažitelný kompresní poměr je třeba 4,5.

Nyní se podíváme na rychlost dekomprese. Rychlost v následující tabulce je udána v MiB/s (více je lépe).

Vidíte tady, že LZ4 je naprosto nepřekonatelný. Dekomprimuje ve stovkách megabajtů za sekundu. Dále zstd je taky slušně rychlý. Nakonec lzop a brotli jsou také celkem rychlé. Speciálně se ale podívejte na bzip3 a zpaq. Tyto dva nástroje byly naprosto nejúčinnější co se týče kompresního poměru, ale podívejte se, jak jsou pomalé.

Nakonec tu máme srovnání rychlosti komprese (MiB/s) se zaměřením na rychlost. Kompresní nástroje byly instruovány, aby komprese byla co nejrychlejší, i za cenu nízkého kompresního poměru. Opět platí, že více je lépe.

Tady můžeme vidět, že jasně vyhrává metoda LZ4 s několika stovkami megabajtů za sekundu. V jednom případě byla ale překonána metodou Zstd. Za zmínku stojí lzop, lz4, zstd a brotli, ale ostatní metody jsou pomalé. Suverénně nejpomalejší je bohužel nástroj zpaq.

Nejúčinnější je zpaq a bzip3

Závěrem můžeme říct, že zpaq a bzip3 jsou v současnosti nejúčinnější kompresory. Zopfli zlepší kompresní poměr proti gzipu o 3–8 %, přičemž používá stále stejnou kompresní metodu Deflate. Nástroje lzop, lz4 a gzip jsou relativně rychlé, ale s nízkým kompresním poměrem.

Metody LZMA, Zstd a Brotli dosahují relativně vysokých kompresních poměrů, nicméně bzip2, bzip3 a zpaq jsou ještě o něco účinnější. LZ4 má s náskokem nejrychlejší dekompresi (leč nízký kompresní poměr), Zstd je také poměrně rychlé. LZMA, bzip2, bzip3 a zpaq jsou při dekompresi hodně pomalé. Nástroje lze zaměřit na rychlost komprese (přinese snížený kompresní poměr) – tady vyhrává LZ4.

Zbývá dodat, že všechny zkomprimované soubory byly následně dekomprimovány a porovnány s originálem. Srovnání bylo měřeno na 32jádrovém procesoru AMD Ryzen Threadripper 2990WX. Byla použita jednovláknová komprese i dekomprese, i když některé nástroje umějí využít více vláken.