Kompresní algoritmy v souborech ZIP: Deflate, Implode a srovnání

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. Ve druhém díle jsme probrali algoritmus Reduce, který používá LZ77. V posledním díle se budeme věnovat Implode a nejpoužívanějšímu algoritmu Deflate a na závěr si algoritmy porovnáme.

Deflate

Algoritmus Deflate byl přidán do PKZip 2.04c v roce 1993 a společnost PKWARE na něj držela patent. Ale podle RFC dokumentu z roku 1996 se obecně předpokládalo, že Deflate je možné implementovat bez porušení patentu. To umožnilo nasazení Deflate například v gzip, zlib a PNG (také kvůli patentu LZW v souborech GIF a Z (starý unixový nástroj compress)). Deflate se také používá v souborech EPUB, ODT, PDF, DOCX, JAR, APK a dalších. Mezitím patent již vypršel.

Deflate se podobá Reduce popsaném v předchozím díle. Data jsou nejprve komprimována LZ77, respektive variantou LZSS a poté je výsledek zpracován výhodnějším Huffmanovým kódováním místo Followers Set v případě Reduce. Huffmanovým kódováním projdou jak explicitní znaky (0–255) tak i zpětné reference (257–285). Kód 256 označuje konec Deflate bloku.

Autor: Hans Wennborg

Ilustrace algoritmů Deflate a Implode

Rozdělení do bloků (block splitting) se děje při kompresi a jde o poměrně složitou optimalizační úlohu. Maximálně může být v bloku 64 kB vstupních dat. Každý blok znamená určitou režii navíc, takže by se mohlo zdát, že je lépe mít míň bloků. Může se ale stát, že se vstupní data změní a je výhodnější začít nový blok s novou Huffmanovou tabulkou a dosáhnout větší komprese. Různé rozdělení zkouší například algoritmus Zopfli, ke kterému se dostaneme.

Huffmanovo kódování

Huffmanovo kódování konvertuje znaky ze vstupu do bitových kódů různé délky. Znaky, které se ve vstupním souboru vyskytují nejčastěji, jsou konvertovány do bitových řetězců s nejkratší délkou, kdežto znaky, které se vyskytují velmi zřídka, jsou konvertovány do delších řetězců, často delších než bajt.

Nejprve je potřeba zjistit statistický výskyt jednotlivých znaků a potom postupně vytvoříme binární strom, podobně jako slovník v LZW (viz první díl).

Autor: Andreas Roever, podle licence: CC BY-SA 3.0

Příklad vytvoření Huffmanova stromu

V příkladu Huffmanova stromu vezmeme dva znaky s nejmenší četností výskytu (D a E) a ty budou mít o jeden bit delší výstupní kód – přidáme před něj kolečko. Toto kolečko má nyní dohromady četnost 11. A pokračujeme dalším krokem, až máme celý strom. Ve stromě bude nejčastější znak (v našem případě A) zapsán pouhým jedním bitem. Ostatní znaky pak třemi bity.

V případě Deflate je možné použít pevné Huffmanovo kódování, kdy nás nezajímá četnost jednotlivých znaků ve vstupu, ale použije se prostě 8 bitů pro 0–143, 9 bitů pro 144–255, 7 bitů pro 256–279 a 8 bitů pro 280–287. Výhodou je, že se Huffmanova tabulka nemusí do výstupu ukládat.

Druhou častěji používanou možností je dynamické Huffmanovo kódování, kdy každý Deflate blok má svoji Huffmanovu tabulku a ta je zapsána na začátku každého bloku.  Pro lepší kompresi je samotná tabulka zapsána pomocí Huffmanova kódu.

Huffmanovo kódování se používá možná překvapivě také v souborech se ztrátovou kompresí například MP3, JPG. Pro JPG existuje výhodnější aritmetické kódování, které vytváří shodné ale menší soubory než Huffmanovo kódování, jak se můžete sami přesvědčit pomocí jpegtran -aritmetic. Typicky by se měl soubor zmenšit o asi 5 % oproti -optimize, který optimalizuje Huffmanovo kódování (také bezeztrátově). V souborech JPG jde ještě nezávisle na kódování použít progresivní sken pomocí -progressive, což typicky zmenší soubor o 2–3 %. Navíc je obrázek možné vidět rozmazaně již během načítání, což ale při dnešních rychlostech internetu již není relevantní. Bohužel aritmetické kódování v JPG není prakticky vůbec nikde podporované.

Výhodné aritmetické kódování využívá například komprese videa CABAC (Context-adaptive binary arithmetic coding) ve formátech H.264/MPEG-4 AVC a HEVC (High Efficiency Video Coding).

Implode

Implode je starším bratrem Deflate a objevil se v PKZip 1.01 v červenci 1989. Používá stejně jako Deflate LZ77 (LZSS) a poté Huffmanovo kódování. Jsou zde však některé rozdíly. Vyhledávací okno LZ77 je v případě Implode jen 8 kB, kdežto Deflate jej má 32 kB. Huffmanovy kódy jsou v případě Implode platné pro všechna vstupní data, kdežto Deflate dělí data do bloků a každý blok má své kódy. Díky tomu je kompresní poměr Deflate lepší než u Implode.

Deflate64

Deflate64 je maličko upravená verze Deflate, kde je slovník zvětšen z 32 kB na 64 kB (odtud název). Deflate64 byl zahrnut do PKZIP jako metoda 9 a umožňuje o trochu lepší kompresi než Deflate. V současnosti podporuje Deflate64 Info-ZIP (jen pro dekompresi) a 7-ZIP. Knihovna zlib naopak Deflate64 nepodporuje (a tedy ani PNG). Nástroj zipinfo z balíčku Info-ZIP ukazuje Deflate64 jako metodu d64N  místo defN nebo  defX.

Úsporu si předvedeme na Silesia Corpusu (nekomprimovaná velikost 206 990 kB) s pomocí 7-ZIP s největší kompresí (7-ZIP označuje -9 jako ultra). Použijeme7z -tzip -mm=Deflate -mx=9 anebo7z -tzip -mm=Deflate64 -mx=9 a výsledek je 63 210,2 kB a 61 355,2 kB, tedy s Deflate64 asi o 8 % menší.

Zopfli

Zopfli je vylepšený Deflate, ale s původním Deflate používaným ve zlib, gzip, PNG nebo ZIP je naprosto kompatibilní. Není kompatibilní s Deflate64. Autoři jsou z Google a vytvořen byl v roce 2013. Zopfli znamená ve švýcarské němčině vánočku. Výhodou je daleko lepší komprese (typicky o 3–8 %), nevýhodou je velmi velká časová náročnost (typicky 80× pomalejší). Původní implementace zopfli a zopflipng zvládne zmenšit soubory GZ a PNG. Ručně lze zvolit počet iterací ( -i, výchozí je 15, pro velké PNG pak 5), více iterací přinese o trochu lepší kompresi, ale o hodně delší běh programu. Algoritmus funguje jako hledání nejkratší dráhy (měřeno v bytech) mezi všemi možnými Deflate reprezentacemi vstupních dat.

Pokud chcete GZ vytvořit rychleji, je možné použít paralelní nástroj pigz používající všechna jádra procesoru. Umí Zopfli s předvolbou -11 a iterace nastavíte pomocí -I (výchozí je 15).

Třetí možností jak použít Zopfli je balík AdvanceCOMP (GitHub, v distribucích se balíček většinou jmenuje advancecomp) , kde můžete zmenšit již existující soubory GZ ( advdef), PNG ( advpng) i ZIP ( advzip). Oproti pigz však tyto nástroje pracují jen s jedním vláknem, což u Zopfli znamená, že si dost počkáte. Iterací je ve výchozím stavu jen 5 pro volbu –4 (insane). S volbou –3 (extra) se použije Deflate algoritmus 7-ZIPu.

Například již zmíněný Silesia Corpus má v originálním ZIP souboru velikost 66 584,7 kB, pokud jej vytvoříme znovu pomocí zip -9 a pigz -9 bude velikost 66 048,2 kB a 66 082,0 kB. Potom pomocí advzip -z -4 získáme 63 232,0 kB, advdef -z -4 63 258,9 kB a pigz -11   dá 63 016,9 kB. Zlepšení Zopfli je tedy asi o 4 %.

Pokud vezmeme soubor vytvořený pomocí 7-ZIP s Deflate 63 210,2 kB, Zopfli jej zmenší na 63 162,4 kB tedy o další asi 0,1 %.

EPUB

Soubory EPUB (electronic publication) jsou standardem pro e-knihy podle IDPF (International Digital Publishing Forum). Ve skutečnosti však jde o ZIP soubory se specifickou adresářovou a souborovou strukturou. Znamená to také, že je můžeme lehce bezeztrátově více komprimovat pomocí zmíněného  advzip.

Vezměme například hru R.U.R od Karla Čapka z Project Gutenberg. Původní EPUB má 101 840 B. Při použití advzip -z -4 je výsledek 90 278 B, tedy o 11 % menší. Stejným způsobem můžete jednoduše zmenšit svoji sbírku knih. Jestli jde stejně použít i Deflate64 nevím, bude záležet na čtečce.

Metodu advzip nejde použít na soubory ODT, protože chybí správné kontrolní součty CRC. Na soubory ODT, DOCX, APK, JAR a další je možné doporučit například nástroj Leanify.

DeflOpt

Ben Jos Walbeehm vytvořil mezi lety 2003–2007 program pro Windows DeflOpt.exe, který funguje v Linuxu dobře s Wine. DeflOpt umožňuje optimalizaci Deflate dat v souborech GZ, PNG a ZIP, případně i v jiných souborech obsahujících Deflate. Nefunguje na jiné algoritmy ani na Deflate64, ale nehavaruje na nich a pokračuje na dalším souboru. Pokud potřebujete optimalizovat více souborů, můžete použít wine DeflOpt.exe /a /r folder. Většinou však úspora není velká. Pokud nutně potřebujete uspořit každý bajt, doporučuje se nejprve 7-ZIP, pak Zopfli a nakonec DeflOpt. Na internetu seženete nejspíše poslední verzi 2.07 z roku 2007. Úspora DeflOpt na ZIP souboru Silesia Corpusu je mezi 2–5 kB, tedy pod 0,01 %.

Porovnání algoritmů

Nejprve si srovnáme algoritmy Shrink, Reduce, Implode a Deflate, jak jsou implementovány v hwzip 2.0 od Hanse Wennoborga. Použijeme opět Silesia Corpus. Pro srovnání rychlosti dekomprese použijeme unzip od Info-ZIP. Ten sice nepodporuje Reduce a v případě Shrink ukazuje chyby, ale je rychlejší než implementace v hwzip.

Nejlepší kompresi nabízí tedy Deflate a zároveň je nejpomalejší na kompresi. Na druhém místě je Implode.

Nyní srovnáme další implementace Deflate od Info-ZIP, 7-ZIP a Zopfli.

Je nutno poznamenat, že 7-ZIP používá více vláken při kompresi. Ale i při započtení všech vláken (8) je Zopfli stále více jak 3× pomalejší. Časy dekomprese jsou v podstatě stejné. Zde jsme Zopfli použili po 7z, aby se ukázalo, že dokáže výsledek ještě zlepšit.

Další algoritmy

Podle poslední specifikace z loňského roku ZIP podporuje daleko více kompresních metod. Přitom staré (legacy) metody 1–6 je doporučeno ke kompresi již nepoužívat.

4.4.5 compression method: (2 bytes)

0 - The file is stored (no compression)
1 - The file is Shrunk
2 - The file is Reduced with compression factor 1
3 - The file is Reduced with compression factor 2
4 - The file is Reduced with compression factor 3
5 - The file is Reduced with compression factor 4
6 - The file is Imploded
7 - Reserved for Tokenizing compression algorithm
8 - The file is Deflated
9 - Enhanced Deflating using Deflate64(tm)
10 - PKWARE Data Compression Library Imploding (old IBM TERSE)
11 - Reserved by PKWARE
12 - File is compressed using BZIP2 algorithm
13 - Reserved by PKWARE
14 - LZMA
15 - Reserved by PKWARE
16 - IBM z/OS CMPSC Compression
17 - Reserved by PKWARE
18 - File is compressed using IBM TERSE (new)
19 - IBM LZ77 z Architecture
20 - deprecated (use method 93 for zstd)
93 - Zstandard (zstd) Compression
94 - MP3 Compression
95 - XZ Compression
96 - JPEG variant
97 - WavPack compressed data
98 - PPMd version I, Rev 1
99 - AE-x encryption marker (see APPENDIX E)

Několik moderních algoritmů s lepší kompresí bylo dodatečně přidáno do souborů ZIP, jmenovitě LZMA a ZSTD, ale takové soubory nebudou kompatibilní se všemi ZIP programy, například s Info-ZIP. Nové algoritmy podporuje například 7-ZIP (Bzip2), libzip a minizip-ng. Domnívám se však, že je lépe tyto algoritmy v souborech ZIP nepoužívat kvůli kompatibilitě a zůstat u Deflate či Deflate64. Pokud potřebujete lepší kompresi, raději využijte soubory XZ, 7Z či ZST, na nichž je hned vidět, co bylo ke komprimaci použito. Pokud je potřeba použít kompatibilní ZIP a chcete dosáhnout co nejmenší velikosti, tak zkuste zmiňovaný program advzip, který zaručí kompatibilitu s Deflate, případně 7-ZIP s Deflate64.

Pro doplnění si ukážeme, jak si se Silesia Corpus poradí algoritmy ZSTD a LZMA2.

Zde všechny algoritmy používají všechna jádra (7z sám od sebe, ostatní pomocí -T0). Algoritmus ZSTD je možné nastavit na rychlou kompresi (výchozí nastavení), nebo pomalejší lepší kompresi ( -19), přitom rychlost dekomprese je velká. Algoritmy LZMA2 (xz a 7z) mají kompresi i dekompresi pomalou, dosahují však nejlepšího kompresního poměru.

Odkazy

• První část článku Hanse Wennoborga s popisem Deflate
• Druhá část článku se srovnáváním algoritmů
• Jeho hwzip 2.0
• Deflate na Wikipedii česky
• Deflate na Wikipedii anglicky
• LZSS na Wikipedii anglicky
• LZ77 na Wikipedii anglicky
• Huffmanovo kódování na Wikipedii česky
• Huffmanovo kódování na Wikipedii anglicky
• Zopfli 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.