Komprese
Z MiS
Obsah |
Principy
Definice
- Kompresní metody: Postupy, vedoucí ke snížení objemu dat při zachování podstatné informace.
Model dat
- Kompresi můžeme využít pouze tehdy, pokud umíme odlišit „podstatnou“ informaci od zbytku.
- Musíme tedy vědět nějaké další informace o datech, které komprimujeme.
- Pojem „model dat“ označuje souhrn pravidel, o kterých víme, že jsou v datech dodržena.
- Příklad — Chceme komprimovat posloupnost nul a jedniček
- Pokud o datech nic nevíme, pak:
- nevíme, co z těchto dat můžeme „ztratit“, aniž bychom poškodili původní informaci.
- Můžeme si ale všimnout, že se často opakují některé posloupnosti nul a jedniček a nahradit je jinými, kratšími posloupnostmi (za cenu toho, že jiné, málo se opakující, nahradíme delšími posloupnostmi).
- Naším „modelem dat“ tedy bude pravděpodobnost výskytu jednotlivých posloupností.
- (Pokud by však pravděpodobnosti výskytu jednotlivých posloupností byly stejné, komprese nám nic nepřinese.)
- Pokud bychom ale věděli, že naše posloupnost nul a jedniček nese informace o barvách pixelů na fotce...
- pak víme, že tato data jsou již zatížena chybou při digitalizaci
- a že na fotce nejspíš sousední pixely budou mít „podobné“ barvy.
- Můžeme tak postavit mnohem přesnější model dat a vylepšit použitý kompresní algoritmus.
Pojmy
- Kompresní poměr
- Poměr velikosti původních dat a velikosti zkomprimovaných dat.
- Závisí na konkrétních datech, která komprimujeme.
Kompresní poměr
- Pro bezeztrátovou kompresi a obecná data je typický kompresní poměr 2:1.
- Pro ztrátovou kompresi (obvykle obrázky, video atd.) je typický kompresní poměr cca 10:1.
- Entropie
- Množství podstatné informace obsažené v datech.
- Velikost dat při použití ideálního kompresního algoritmu bezeztrátové komprese.
Rozdělení kompresních metod
Ztrátové × bezeztrátové
- Ztrátové typicky u videa, audia, obrázků a dalších dat, která jsou již sama zatížena chybou.
- Ztrátové mohou docílit výrazně vyššího kompresního poměru za cenu dílčího poškození (zhoršení kvality) komprimovaných dat.
Statistické × slovníkové metody
- Statistické metody
- Nahrazují jednotlivé hodnoty symbolů posloupností bitů.
- Můžeme si představit třeba tabulku: E => 01, A => 100, T => 101,...
- Vychází z toho, že pravděpodobnost výskytu znaků se dá spočítat a není stejná.
- Pro běžná počítačová data malý kompresní poměr, jsou spíše součástí jiných metod.
- Slovníkové metody
- Nahrazují celé posloupnosti symbolů (slova) za posloupnosti bitů.
- Převodní tabulka je větší, ale můžeme docílit lepšího kompresního poměru.
- Do této skupiny patří většina běžně používaných metod.
Statické × dynamické metody
- Statické metody
- Po celou dobu komprese datového souboru se převodní tabulka nemění.
- Většinou se převodní tabulka musí přiložit k souboru.
- Často je třeba nejprve předzpracovat statistiku výskytu znaků.
- Dynamické metody
- Upravují převodní tabulku v průběhu komprese.
Příklady metod
- LZ 77
- Používá kompresní program ZIP a odvozené.
- Bezeztrátová slovníková metoda
- Autoři Lempel a Ziv, Izrael, 1977.
- LZ 78
- Tvoří základ algoritmů programů RAR a GZIP
- Autoři Lempel a Ziv, Izrael, 1978.
Úkoly
- Srovnejte kompresní poměr programů ZIP (implementace ve vašem operačním systému) s programem RAR či 7zip. Jako stestovací použijte složku s několika textovými dokumenty a dokumenty ve Wordu či LibreOffice.
- Porovnejte s předchozím příkladem kompresní poměr v případě, že komprimujete složku s některým programem ve složce Program Files (či jiné pro váš operační systém).
- Porovnejte s předchozím příkladem kompresní poměr v případě, že komprimujete složku obrázky JPG či PNG.
- Vezměte si tři fotky ze svého mobilu. Chcete je předat kolegovi tak, aby byla délka zprávy (množství byte) co nejmenší. Kolega si obrázky chce prohlédnout na FullHD monitoru (1920×1080 px), žádné další operaci s nimi dělat nepotřebuje.
- Vezměte si tři screenshoty ze své obrazovky. Jedná se o výřezy jednoho okna, které zabírá třeba čtvrtinu plochy obrazovky. Chcete je předat kolegovi tak, aby je mohl vložit do webového návodu. Zároveň chcete, aby zabíraly co nejméně místa (co nejmenší počet byte).
