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

21. 11. 2024
Doba čtení: 5 minut

Sdílet

 Autor: Root.cz s využitím DALL-E
Komprese dat je postup, který má za cíl zmenšit objem nebo datový tok dat. Tento článek se věnuje výhradně bezeztrátové kompresi, kde lze původní data zrekonstruovat bez zkreslení. Jaké metody můžeme použít?

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

Soubor Popis Typ dat Velikost
dickens Collected works of Charles Dickens text 9,72 MiB
mr Medical magnetic resonanse image picture 9,51 MiB
ooffice A dll from Open Office.org 1.01 exe 5,87 MiB
osdb Sample database in MySQL format database 9,62 MiB
reymont Text of the book CHŁOPI by W. Reymont pdf 6,32 MiB
sao The SAO star catalog bin data 6,92 MiB
xml Collected XML files html 5,10 MiB
x-ray X-ray medical picture image 8,08 MiB

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

dickens mr ooffice osdb reymont sao xml x-ray
lzop 2.2803 2.4523 1.8408 2.3925 3.0753 1.2517 6.7689 1.2433
lz4 2.3244 2.3784 1.7391 2.5489 3.2072 1.2787 7.0204 1.1802
gzip 2.6461 2.7138 1.9907 2.7138 3.6396 1.3613 8.0709 1.4035
zopfli 2.7783 2.9060 2.0565 2.7966 3.9169 1.3847 8.5281 1.4756
rar 3.2698 3.5758 2.6634 3.0469 4.2394 1.3068 10.7838 2.0164
lzma 3.6006 3.6237 2.5351 3.5462 5.0383 1.6388 12.2943 1.8871
xz 3.6000 3.6231 2.5346 3.5456 5.0374 1.6386 12.2910 1.8868
zstd 3.5770 3.2103 2.3672 3.2550 4.9177 1.4502 11.7940 1.6436
brotli 3.6044 3.5317 2.4818 3.5812 4.9747 1.5812 12.4145 1.8096
bzip2 3.6407 4.0841 2.1492 3.5984 5.3178 1.4678 12.1157 2.0918
bzip3 4.5625 4.7031 2.4346 4.4589 6.7591 1.5517 13.1697 2.3172
zpaq 4.8656 4.5708 3.4825 4.5745 6.9285 1.8598 16.3486 2.3092

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

dickens mr ooffice osdb reymont sao xml x-ray
lzop 264.8 357.4 252.8 421.8 311.3 352.8 490.1 291.7
lz4 665.7 699.1 592.6 745.6 658.3 606.6 717.9 585.6
gzip 148.4 148.3 123.5 153.6 170.3 127.6 229.6 108.1
rar 158.3 134.6 109.6 152.9 169.4 124.6 193.8 130.9
lzma 70.3 53.6 37.6 55.7 92.1 24.5 170.4 26.7
xz 71.1 53.0 37.6 55.5 89.6 24.6 163.3 25.9
zstd 439.8 424.4 362.1 500.9 501.6 409.2 670.7 338.1
brotli 263.4 206.2 152.3 231.2 329.1 129.0 439.4 121.8
bzip2 27.1 35.8 21.2 28.1 32.7 18.5 44.2 24.1
bzip3 6.8 6.8 7.0 6.6 7.2 5.7 16.2 7.1
zpaq 3.3 4.0 3.1 3.0 3.0 2.3 4.0 2.9

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.

dickens mr ooffice osdb reymont sao xml x-ray
lzop 231.4 306.7 255.0 331.6 274.7 256.1 509.7 808.1
lz4 441.8 559.3 366.6 565.7 351.1 406.8 509.7 621.6
gzip 64.8 77.3 48.8 66.3 71.8 38.4 110.8 39.8
rar 30.0 31.3 36.4 37.7 38.0 34.5 49.9 28.9
lzma 3.3 2.4 4.1 4.0 3.1 4.3 3.3 4.9
xz 20.6 14.8 19.7 27.9 16.8 21.8 13.3 29.3
zstd 237.0 352.1 308.7 356.2 210.6 314.3 424.8 1010.2
brotli 226.0 288.1 217.3 331.6 287.2 197.5 463.4 197.1
bzip2 13.8 19.5 12.1 14.2 15.2 12.0 12.9 14.2
bzip3 6.8 6.4 6.0 6.0 5.6 4.7 10.9 5.2
zpaq 0.3 0.4 0.3 0.3 0.3 0.2 0.4 0.3

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.

bitcoin školení listopad 24

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.

ikonka

Zajímá vás toto téma? Chcete se o něm dozvědět víc?

Objednejte si upozornění na nově vydané články do vašeho mailu. Žádný článek vám tak neuteče.

Autor článku

Autor vystudoval Fakultu informačních technologií VUT v Brně, kde nyní pracuje jako vědecký pracovník. Zajímá se o multimédia a na svých strojích používá výhradně Gentoo Linux.