Hlavní navigace

Kompresní algoritmy v souborech ZIP: Store a Shrink

13. 4. 2021
Doba čtení: 5 minut

Sdílet

 Autor: Depositphotos
Kompresní formát ZIP je přes třicet let starý, přesto by mohl být i v současnosti pro někoho zajímavý. Podporuje několik kompresních algoritmů a ty si zde postupně rozebereme. V tomto díle se budeme věnovat hlavně Shrink/LZW.

ZIP je a hlavně byl velmi rozšířený a populární program pro archivaci a kompresi dat. První program PKZIP vznikl již v roce 1989. V současnosti v Linuxu a jiných Unixech použijete patrně open source Info-ZIP (zip a unzip ) a ve Windows například WinZip, 7-Zip nebo třeba PeaZip. Poslední dva najdete i v Linuxu (nedávno se objevila oficiální linuxová verze 7-Zip).

Formát souboru ZIP umožňuje několik kompresních algoritmů: Store (bez komprese), Shrink (LZW), Reduce, Implode, Deflate a další. V současnosti se používá hlavně algoritmus Deflate, protože má nejlepší kompresi. Byl však přidán až do PKZIP 2 v roce 1993. Deflate se také používá v knihovně zlib, v programu gzip a také kupříkladu v souborech PNG, EPUB, ODT a DOCX.

Zajímavá je také vlastní struktura souboru ZIP, kdy až na konci najdeme Central Directory. Zde je seznam souborů, odkaz na jejich polohu v ZIP souboru, jejich kontrolní součet CRC-32, datum vytvoření souboru, velikost komprimovaná a nekomprimovaná a další informace. Patrně se vám již někdy stalo, že jste stáhli ZIP soubor necelý a on se odmítl rozbalit. To právě je způsobené chybějícím Central Directory na konci souboru. Tato vlastnost také umožňuje pěknou hříčku, jak vytvořit soubor, který se chová zároveň jako PNG i jako ZIP.


Autor: Wikipedia

Struktura souboru ZIP

Nedávno se v pěkném článku kompresním algoritmům v souborech ZIP věnoval Hans Wennborg a my si tu s jeho svolením jeho článek přeložíme. Pokud někoho zajímá, jakým algoritmem jsou komprimovány soubory v nějakém souboru ZIP, tak k tomu slouží nástroj zipinfo z již zmíněného Info-ZIP. U jednotlivých souborů můžeme vidět  například stor, re, shrk, defS, defF, defN a defX (Deflate superfast, fast, normal a maximum). Info-ZIP umí použít při kompresi jen Store ( -0) a Deflate ( -1  – -2 defF, -2  – -7 defN, -8  – -9 defX), výchozí je volba -6. Dekomprimovat umí samozřejmě všechny algoritmy. Pokud chcete experimentovat s ostatními metodami komprese, můžete použít například hwzip právě od Hanse Wennborga. Také doporučuji se podívat do jeho zdrojových kódů.

Store

Při použití Store jsou data pouze uložena, není provedena žádná komprese. Touto metodou jsou ukládány například prázdné soubory a adresáře. Jinak tento algoritmus není příliš zajímavý.

Shrink, Unshrink

Shrink je variantou kompresního algoritmu LZW (Lempel-Ziv-Welch), který se objevil v roce 1984 ve známém článku. Algoritmus LZW se používá ve starém známém unixovém nástroji Compress, který vytváří soubory .Z. Dále se LZW používá v grafických souborech GIF. LZW však bylo patentované. To pomohlo rozvoji formátu PNG a nástroje gzip, které oba používají svobodný Deflate. Mimochodem LZW patenty vypršely v roce 2004.

Algoritmus LZW

Algoritmus LZW je založen na slovníku. Vstup je rozložen na řetězce, které se nacházejí ve slovníku a výstup jsou kódy, které odkazují na řetězce ve slovníku. Slovník se postupně vytváří a rozšiřuje při kompresi. Přitom se slovník nemusí ukládat do archivu, ale je při dekompresi znovu rekonstruován.

Na začátku jsou ve slovníku všechny povolené jednobajtové znaky. Pokud se ve vstupu objeví řetězec, který již ve slovníku je, automaticky přidáváme řetězec s přidaným dalším znakem ze vstupu.

Příklad

Zkusíme zkomprimovat řetězec s 28 znaky „tri sta tricet tri strikacek“. Jako počáteční slovník použijeme jen písmena. V původním LZW algoritmu jsou ve slovníku všechny osmibitové znaky 0–255. Kódy 256–4095 jsou rezervovány pro další kombinace znaků, které se ve zdroji postupně vyskytnou.

Počáteční slovník
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
_ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Ze vstupu vezmeme znaky, které jsou ve slovníku a jejich kód pošleme na výstup. Tyto znaky rozšíříme o následující znak a automaticky přidáme do slovníku s dalším volným kódem. Tak postupně rozšiřujeme slovník a podobně postupujeme po zbytek vstupního řetězce.

Postup komprese LZW
Vstup Výstup Rozšířený slovník
T 20
R 18 TR=27
I 9 RI=28
_ 0 I_=29
S 19 _S=30
T 20 ST=32
A 1 TA=33
_ 0 A_=34
TR 27 _TR=35
I 9 TRI=36
C 3 IC=37
E 5 CE=38
T 20 ET=39
_TR 35 T_TR=40
I 9 _TRI=41
_S 30 I_S=42
TRI 36 _STRI=43
K 11 TRIK=44
A 1 KA=45
CE 38 ACE=46
K 11 CEK=47

Vstupní řetězec o délce 28 je zkomprimován do kódu o délce 21. Dlouhý anglický text se pomocí LZW zkomprimuje v poměru asi 2:1. Podobně postupujeme při dekompresi, kde také postupně rekonstruujeme rozšířený slovník.

Postup dekomprese LZW
Vstup Výstup Rozšířený slovník
20 T
18 R TR=27
9 I RI=28
0 _ I_=29
19 S _S=30
20 T ST=32
1 A TA=33
0 _ A_=34
27 TR _TR=35
9 I TRI=36
3 C IC=37
5 E CE=38
20 T ET=39
35 _TR T_TR=40
9 I _TRI=41
30 _S I_S=42
36 TRI _STRI=43
11 K TRIK=44
1 A KA=45
38 CE ACE=46
11 K CEK=47

Slovník

Implementace LZW v PKZIP tedy Shrink ukládá slovník jako prefixový strom tzv. trie. To jednak šetří paměť a také zrychluje vyhledávání.


Autor: Wikipedie

Příklad trie

Další otázkou je, jak dlouhý slovník a tedy jak dlouhé kódy použít. Pro 8bitové bajty musíme použít nejméně 9bitové kódy. Větší kódy umožňují větší slovník a tedy lepší kompresi, ale pro vstupy bez opakování může pak být naopak výstup delší.

Jak jsme již řekli, tak původní LZW algoritmus používal pro 8bitový vstup 12bitové kódy. Většina implementací však používá variabilní délku kódů. Například program Compress začíná na 9 bitech a může dosáhnout až 16 bitů. GIF začíná s 3–9 bity podle barevné hloubky obrázku a může růst až na 12 bitů. U Compress i GIF se kód zvětšuje automaticky.

PKZIP Shrink používá kódy dlouhé 9 – 13 bitů a používá specifický kód (256), jak dekodéru oznámit, že kódy byly zvětšeny.

Plný slovník

Dalším problémem může být plný slovník, jak se řetězce neustále přidávají do slovníku, který je shora omezen maximální dálkou kódu. Například původní Compress v takovém případě nedělá nic, pokračuje zpracovávat vstup, jen již nepřidává nic do slovníku. Problémem je, že slovník už není aktuální a kompresní poměr se postupně zhoršuje.

Druhou možností je smazání slovníku, když se zaplní, a ten se začne vytvářet znova. Takto postupuje například GIF. Smazání slovníku je řízeno speciálním kódem, který kompresor může použít kdykoli, nejen při plném slovníku.

Compress od verze 3.0 po zaplnění slovníku testuje kompresní poměr a když klesne, tak resetuje slovník. Toto se nazývá adaptivní reset.

Shrink jde ještě dále a umožňuje částečný reset, kdy jsou odebrány řetězce, které pod sebou ve stromě již nemají další řetězce a tedy se ve vstupu zatím objevily jen jednou.

skoleni

Tímto končí povídání o Shrink. Příště se můžete těšit na Reduce.

Hlavní odkazy

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.

Autor článku

První linux nainstaloval kolem roku 1994 a u něj zůstal. Později vystudoval fyziku a získal doktorát.

  • Kompresní algoritmy v souborech ZIP: Store a Shrink