Komprese
Z MiS
(Rozdíly mezi verzemi)
(→Statické × dynamciké metody: Doplněny popisy metod.) |
(Přidán Model dat a příklad.) |
||
| Řádka 1: | Řádka 1: | ||
[[Category:VSE]][[Category:Sítě]][[Category:Informatika]][[Category:Bezpečnost]][[Category:CRI]][[Category:Komprese]] | [[Category:VSE]][[Category:Sítě]][[Category:Informatika]][[Category:Bezpečnost]][[Category:CRI]][[Category:Komprese]] | ||
| − | == Definice == | + | == Principy == |
| + | |||
| + | === Definice === | ||
* Kompresní metody: Postupy, vedoucí ke snížení objemu dat při zachování podstatné informace. | * 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. | ||
| + | |||
| + | <div class="Priklad"> | ||
| + | ; 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. | ||
| + | </div> | ||
Verze z 27. 3. 2017, 06:55
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.
