Téměř každý uživatel se někdy setkal s kompresí. Zabalené soubory se stahují každodenně z internetu, aniž by si to kdo uvědomoval. Například i na serveru www.stahuj.cz můžete najít instalační soubory zabalené do archivů. Komprese pomocí archivů se dříve používala zejména pro zmenšení velikosti souborů. V dnešní době se využívá spíše pro vytvoření jednoho jediného souboru z více souborů či složek, popřípadě pro vytvoření několika souborů stejné velikost (možnost rozdělit archiv rar na díly - party - stejné velikosti). Snadněji se pak daný soubor nahrává na web anebo posílá přátelům.

Jak soubor zabalit a rozbalit, to ví téměř každý uživatel. Ale jak vlastně komprese funguje? Jak to, že posloupnost jedniček a nul se dá zredukovat na kratší posloupnost a poté opět rozvinout do původní? To už ví daleko méně lidí. Princip přitom není nikterak složitý. Jednotlivé postupy se však zdokonalují, komplikují a stávají se složitými.

Samotná komprese se dělí na dva typy. Prvním je bezeztrátová komprese, které se budeme ihned věnovat. Na konci se pak zmíníme i o druhém typu - ztrátové kompresi.

 <p> </p>

Ilustrační obrázek dvou archivů v prostředí Windows.

Bezeztrátová komprese

Jedná se o proces, při kterém nedochází ke ztrátě informací. Proces je vratný. Využívá se například u typů rar, zip, tar, gz a dalších. Pokud tedy zabalíme nějaký soubor, po rozbalení bude zcela shodný s tím původním.

Postup

Pro vysvětlení komprese použijeme příklad. Nejblíže většině uživatelů bude jistě použití obyčejných slov. Mějme tedy například větu:

Petr požádal Petru o ruku. Petra však Petra odmítla a Petr nevěděl, jestli ji má požádat později znova.

Pokud se podíváme na jednotlivá slova, všimneme si, že se některá z nich opakují. Tato slova označujeme jako redundantní (neboli nadbytečná, opakující se). Pokud bychom chtěli zkrátit danou větu, měli bychom se snažit zkrátit ji právě pomocí těchto slov.

LZ slovník

Jako první případ si ukážeme jednoduché použití Lempel and Ziv adaptive dictionary-based algorithm (ve volném překladu: Lempelův a Zivův přizpůsobivý slovníkový postup).

Nejprve si sepíšeme tabulku s výskytem redundancí a s novým označením slova (kódovým slovem), čímž vytvoříme slovník:

Slovo Výskyt Kódové slovo
Petr 2x 1
Petra 2x 2

 

Nyní můžeme větu přepsat za použití našeho slovníku, který jsme si sestavili:

1 požádal Petru o ruku. 2 však 2 odmítla a 1 nevěděl, jestli ji má požádat později znova.

Původní věta měla 103 znaků (včetně mezer a interpunkčních znamének). Nová věta má pouhých 89, ale nesmíme zapomenout na slovník, který jsme si vytvořili a který musíme k datům přiložit. Ten má (vždy číslo + slovo) dohromady 11 znaků. To je spolu s novou větou 100 znaků. Naše komprese tedy nebyla moc úspěšná a rozhodně jsme neušetřili příliš místa.

Při chytřejším použití slovníkového postupu nebudeme brát celá slova, ale samotná písmena. Když si projdeme větu, najdeme nejčastější posloupnost písmen, kterou je "Petr". Jako druhou můžeme ještě vzít například "_požáda", kde "_" značí mezeru. Nový slovník tedy bude vypadat následovně:

Posloupnost Výskyt Kódové slovo
Petr 5x 1
_požáda 2x 2

 

Nová věta bude vypadat takto:

12l 1u o ruku. 1a však 1a odmítla a 1 nevěděl, jestli ji má2t později znova.

Tato věta má 76 znaků, slovník má 13 znaků. Dohromady tedy máme 89 znaků. To je určitě lepší než v prvním případě.

<p> </p>

Ukázka binárního stromu. Vlevo lze vidět posloupnosti a1-a4 a jejich pravděpodobnosti výskytu (červeně). Žlutě podbarvená jsou pak kódová slova.

Huffmanovo kódování

Jako druhý postup si ukážeme Huffmanovo kódování. Při něm dochází k prohledávání textu a hledání nejčastěji se vyskytujících posloupností znaků určité délky. Nejčastější posloupnosti jsou pak nahrazeny nejkratšími kódovými slovy (například 011 binárně), nejméně časté posloupnosti jsou nahrazeny nejdelšími kódovými slovy (například 100110101). Pro přidělování kódových slov se sestavuje binární strom podle pravděpodobností výskytu jednotlivých posloupností. Při sestupu po jeho hranách pak dochází k získání kódových slov v prefixovém tvaru, což zaručí, že se při dekódování nemohou poplést dvě posloupnosti (pro náš případ to znamená, že delší slovo nemůže být například 01101, což by znamenalo, že začíná znaky 011, přičemž by došlo k přeložení na nejkratší posloupnost a hledala by se pak posloupnost pro znaky 01).

Typy dat

Můžeme se zamyslet nad různými typy souborů a uvědomíme si, jak moc je můžeme zmenšit. V dlouhých textových souborech se dá často najít spousta podobných slov a tím pádem je i dostatečně zmenšit. U různých zdrojových textů programovacích jazyků to bývá mnohdy ještě daleko lepší, protože jazyky se skládají z několika častých příkazů a výrazů, které se používají neustále dokola. Na druhou stranu například hudební nebo video soubory neobsahují příliš redundantních informací a tudíž ani komprese nebude příliš úspěšná.

 <p> </p>

Jendoduchý zdrojový kód v jazyku Java. Lze si všimnout vysoké redundance.

Ztrátová komprese

Při tomto procesu dochází ke ztrátě informací, které se již nedají získat zpátky. Obyčejný uživatel se s ní nejčastěji setkává například u obrázkových formátů (JPG, JPEG), a to pravděpodobně najvíce u fotek, které se v těchto formátech často uchovávají, jelikož u nich ztrátová komprese nezpůsobí na první pohled rozeznatelné škody.

Obrázky

Vezměme si například fotku, na které jste vy před rozlehlou zelenou krajinou a modravou oblohou. Na první pohled se obloha jeví celá modrá a tráva celá stejně zelená. Tím pádem by se měl dát soubor jednoduše zmenšit. Když se však podíváte podrobněji, všimnete si, že barva jednotlivých pixelů oblohy se jemně liší. Některá modrá je trošku tmavější či světlejší než jiná. Při procesu ztrátové komprese pak dochází k výpočtu jedné barvy, kterou se dá nahradit více barevně podobných pixelů. Části oblohy a louky jsou pak nahrazeny novými barvami, které jsou již redundantní.

 <p> </p> <p> </p>

Vlevo je obrázek před kompresí. Vpravo obrázek se 7% zachováním kvality formátu JPG.

Programy na bezeztrátovou kompresi

Programů pro kompresi je velká spousta a většina těch známějších dosahuje stejné kvality. Některé zkomprimují soubor na menší velikost, ale zase jim proces trvá více času. Jiné dokážou data zabalit rychleji, ale samozřejmě na úkor velikosti.

Mezi ty nejznámější jistě patří WinRAR, 7-zip, WinZip, ALZip, IZArc, ale i spousta a spousta dalších. Různé programy pracují s různými formáty, což znamená použití trochu jiných postupů. Některé jsou zdarma, jiné placené. Záleží pak jen na uživateli, který z nich si zvolí za svůj oblíbený.