Kompresní algoritmy v souborech ZIP: Reduce a LZ77

V prvním díle jsme si řekli, že formát ZIP umožňuje několik algoritmů komprese a zabývali jsme se algoritmem Store a Shrink, což je v podstatě upravený LZW. V tomto díle budeme pokračovat algoritmem Reduce, který používá LZ77.

Reduce, Expand

Algoritmus Reduce (pro kompresi) a Expand (pro dekompresi) je patrně nejexotičtějším algoritmem ve formátu ZIP. I když byl podporován již v prvních verzích PKZipu s přepínačem -e (extra compression), byl po zavedení Implode (popíšeme později) nahrazen právě Implode nebo Shrink.

Reduce kombinuje slovníkovou kompresi LZ77 s jednoduchým statistickým zpracováním Follower sets.

Autor: H. Wennborg

Schéma Reduce

Lempel-Ziv LZ77

Abraham Lempel a Jacob Ziv jsou autory slovníkové komprese LZ77, kterou popsali ve svém článku z roku 1977. Hlavní myšlenkou algoritmu je reprezentovat řetězce, které se již ve vstupu dříve vyskytly, pomocí odkazu. Takže v našem vstupu „tri sta tricet tri strikacek“ bude druhý výskyt řetězce „tri“ reprezentován odkazem na (8,3), tedy 8 znaků zpět a zkopírovat 3 znaky. Na rozdíl od minule popisovaného algoritmu LZW z roku 1984, který si automaticky udržuje slovník, je v případě LZ77 celý již zpracovaný text vlastně slovníkem. Obecně má LZ77 lepší kompresi než LZW.

Původní autoři přišli se schématem tripletů, každá část vstupu je reprezentovaná tripletem ( vzdálenost, délka, následující_znak). Tedy naše druhé „tri“ by bylo (8, 3, c). Znak, který se ještě nevyskytl, například první „t“, bude zakódován jako (0, 0, t). Takto funguje originální LZ77. Ve skutečnosti se většinou následující znak nepoužívá, používají se dvojice ( vzdálenost, délka) a neopakovaný explicitní znak se prostě kopíruje na výstup. Tato varianta se jmenuje LZSS (Lempel–Ziv–Storer–Szymanski). 

Náš vstup „tri sta tricet tri strikacek“ bude v LZSS vypadat jako „tri sta (8,3)cet (7,3) (15,2)(5,2)ka(14,2)k“. Hledání shody v předchozím vstupu je limitováno vyhledávacím oknem (search window). Pokud je toto okno větší, máme větší naději, že najdeme shodu a zlepšuje se kompresní poměr. Zároveň ovšem roste velikost každého odkazu ( vzdálenost, délka) a také klesá rychlost komprese. V případě Reduce je okno omezeno na 512–4096 a délka na 273–385 podle zvoleného stupně komprese.

Reduce používá znak 144 k označení, že přijde zpětný odkaz. Tento znak je označován také jako DLE (distance-length encoding). Pokud za DLE následuje nulový bajt, nejde o DLE, ale o explicitní znak s kódem 144. Pokud následující bajt není nula, tak dva až tři bajty (podle zvoleného parametru komprese) obsahují vzdálenost a délku zpětného odkazu.

Vyhledávací okno

Nyní uděláme malou odbočku a podíváme se, jak velká vyhledávací okna mají různé kompresní algoritmy. K určení nám poslouží následující trik. Vygenerujeme náhodný soubor o určité délce. Náhodná data jsou prakticky nekomprimovatelná. Obsah uložíme dvakrát (případně třikrát či vícekrát) za sebou a komprimujeme. Jestli výsledek je poloviční, délka původního souboru je menší než vyhledávací okno algoritmu. Jestli je výsledek prakticky nezměněný, tak je délka původního souboru větší než vyhledávací okno algoritmu. Příklad jednoduchého skriptu:

#!/bin/sh
COUNT=31

rm out*
dd if=/dev/urandom bs=1k of=tmp count=$COUNT
cat tmp tmp > out
rm tmp
ls -l out*
zip -9 out.zip out
ls -l out*

Přitom lzo (Lempel–Ziv–Oberhumer) je z roku 1996, lz4 z roku 2011 je také založené na LZ77 a autorem je Yann Collet. Výkonný xz používá LZMA2 (Lempel–Ziv–Markov chain) a je z roku 1996 od autora 7-Zipu Igora Pavlova. Moderní zstd z roku 2016 má stejného autora jako lz4 a je do něj zapojen Facebook. Pokud použijete zstd --long=28 a vyšší, je potřeba totéž explicitně specifikovat i při rozbalování. Předposlední vydání zstd verze 1.4.9 vydané letos 3. března má navíc --long více než dvakrát rychlejší než dříve. Poslední verze 1.5.0 ze 14. května má pak i rychlejší dekompresi při použití velkých oken.

V roce 2006 Andrew Tridgell napsal rzip, který používá LZ77 s až 900MB oknem. Nevýhodou je nutnost několika průchodů původním souborem, proto jej nelze používat například s rourou. Vylepšenou verzí s LZMA je pak lrzip z roku 2008, jehož autorem je Con Kolivas.

Nevýhodou formátu ZIP je také to, že komprimuje všechny soubory odděleně. Tedy nemůže vyhledat duplicity, které se vyskytují mezi soubory. Výhodou je snad jen to, že poškození archivu jen v jednom místě znamená ztrátu jediného souboru.

Myšlenku využít duplicity mezi soubory využil tzv. solid archive, který se objevil poprvé v RARu. Ale například tar.gz také na rozdíl od ZIPu komprimuje mezi jednotlivými soubory. Pokud se podíváte do tabulky, Deflate má okno jen 32 kB, což omezuje možnosti komprese mezi jednotlivými soubory.

Pokud ale použijete xz nebo zstd --long, bude to už lepší. Také tar sám o sobě příliš nehledí na pořadí souborů v archivu. Existuje pár nástrojů, například tar-sorted a tarper, které mění pořadí souborů v archivu tar, aby se docílilo právě co nejlepší komprese.

Například zdrojové kódy hwzip 2.0 Hanse Wennborga mají v originálním ZIPu 180,6 kB (pokud použijeme Info-ZIP -9, bude o trochu větší 184,0 kB), v tar.gz 162,3 kB a s použitím tarper se dostaneme na 160,3 kB. Přitom pro kompresi gz použijeme paralelní ekvivalent  pigz -9.

Follower sets

Vraťme se nyní k Reduce. Follower sets je jednoduchá statistická metoda, jak efektivněji zakódovat explicitní znaky vstupu, které nejsou opakovány. Ke každému možnému bajtu 0–255 je možné na základě statistické analýzy vstupu přiřadit až 32 následujících bajtů, které se vyskytují nejčastěji. Například pro anglický text bude pravděpodobně následovat za T písmeno H a po něm E.

Přitom každý bajt nemusí mít následovníky, záleží na vstupu. Pokud je na vstupu Follower sets znak, co má následovníky, záleží na následujícím bitu. Při 0 se použije index v tabulce následovníků, při 1 se použije obyčejný kód znaku. Tímto způsobem lze ještě více zredukovat často opakované kombinace znaků.

Follower sets by měl nejprve přečíst celý vstup, najít nejčastější kombinace, uložit Follower sets do výstupu a začít zpracovávat vstup podruhé. To je ovšem časově náročné, proto se vyhodnocují kombinace ve vyrovnávací paměti a pak se obsah této paměti také komprimuje a pošle na výstup.

Odkazy

• Článek Hanse Wennborga
• První část článku Hanse Wennoborga s popisem LZ77
• Jeho hwzip 2.0
• LZ77 na Wikipedii anglicky
• LZSS na Wikipedii anglicky

Seriál vzniká jako překlad původního článku s laskavým svolením původního autora, kterým je Hans Wennborg.