Úvod
Použitie a prenos bežne používaných informácií, ako je zvuk, obraz a video v digitálnom tvare vyžaduje použitie rozsiahlych pamätí a veľkých šírok prenosového pásma. Toto má za následok zvyšovanie nákladov na prenos a uchovávanie informácií. Vďaka technológii kompresie môžeme tieto náklady výrazne zredukovať. Kompresia umožňuje efektívnu digitálnu reprezentáciu zdrojového signálu, ako je text, obraz alebo video, použitím redukovaného počtu prvkov digitálnej informácie (bitov), než má originál. Kompresia vo svojej podstate predstavuje druh kódovania, kde pod kódovaním rozumieme prechod od určitej reprezentácie dát k jej inej reprezentácii (pri kompresii, do reprezentácie s menším objemom dát). Obrátený postup, teda získanie pôvodných dát z dát komprimovaných sa nazýva dekompresia.
Základné dôvody hovoriace pre kompresiu dát:- rozsiahle nároky multimediálnych dát na pamäť a kapacitu záznamových médií
- relatívne pomalé pamäťové zariadenia, ktoré neumožňujú prehrávanie multimediálnych dát (hlavne videa) v reálnom čase
- šírka prenosového pásma v súčasných prenosových sieťach, ktorá neumožňuje prenos videa a často ani zvuku v reálnom čase
V zásade môžeme kompresiu rozdeliť na:
bezstratovú (lossless) - pôvodný signál zdroja informácií je možné obnoviť bez akejkoľvek straty kvality (pôvodný signál a signál po kompresii a následnej dekompresii sú totožné) . Bezstratovo sa komprimuje text, kód programov a iné informácie,u ktorých potrebujeme zachovať 100% pôvodný obsah. Bezstratovú kompresiu umožňujú napríklad: Huffmanove kódovanie, RLE, LZW, LZ77, aritmetické kódovanie a iné.
stratovú (lossy) - vychádzame obvykle z modelu vnímania informácie užívateľom a podľa požiadaviek na kvalitu, resp. rozsahu vnímania, redukujeme obsah prenášanej informácie (pôvodný signál a signál po kompresii a následnej dekompresii nieje totožný s pôvodným signálom, ale je mu do určitej miery podobný ). Stratová kompresia sa využíva hlavne pri kompresii obrazu, videa a zvuku napr. v štandardoch JPEG(statický obraz) a MPEG(audio a video). Stratové algoritmy dosahujú výrazne vyšších kompresných pomerov ako nestratové algoritmy.
Z hľadiska časovej náročnosti kompresie a dekompresie:symetrickú - kompresia a dekompresia trvajú zhruba rovnako dlho(napr. JPEG).
asymetrickú - jedna z operácií (kompresia alebo dekompresia) vyžaduje výrazne viac času. V praxi je to obyčajne operácia kompresie(napr. MPEG).
Na vyjadrenie efektívnosti kompresie môžeme použiť niekoľko ukazovateľov:
Pomer kompresie je definovaný nasledovne: Rozmer vstupného prúdu dát
Pomer kompresie = -----------------------------
Rozmer výstupného prúdu dát
Hodnota 0,7 bude znamenať, že údaje po kompresii zaberajú 70% pôvodného pamäťového priestoru. Hodnoty väčšie ako jedna znamenájú negatívnu, obyčajne nežiadúcu, expanziu spracovávaných dát.
Faktor kompresie je definovaný nasledovne: Rozmer výstupného prúdu dát
Faktor kompresie = -----------------------------
Rozmer vstupného prúdu dát
Faktor kompresie je vlastne prevrátená hodnota pomeru kompresie. V tomto prípade hodnoty väčšie ako 1 znamenajú kompresiu, menšie ako 1 expanziu.
Zopár pojmov z teórie informácií
V roku 1948 vo svojej práci "A Mathematical Theory of Communication" formuloval základy kompresie dát Claude E.Shannon. Zaviedol pojem entropia, ako základný limit pre bezstratovú kompresiu dát. Veľmi dobre spracovaná stránka o teórii kompresii je na http://www.data-compression.com/theory.html.
Pri kompresii sa využívajú poznatky z teórie informácií a tak si stručne uvedieme niektoré z nich. Predpokladáme, že máme abecedu zloženú z m prvkov či znakov, s ktorých sa vytvárajú slová s n prvkami, je možné zostaviť rôzne správy qo...qx...qQ s dĺžkou n; pre Q platí: Q=mn (variácie m prvkov triedy n s opakovaním).
Množstvo informácie Ix, získané prijatím určitej správy qx, ktorá sa vyskytuje s pravdepodobnosťou px, bude tím väčšie, čím bude táto správa nepravdepodobnejšia.
Ix=log2(1/px) [bit]
Entropia H je informácia pripadajúca na jeden znak, ktorú je možné získať z celého súboru. Inak povedané, je to počet bitov potrebných na opis jedného znaku.
Q
H=suma px.log2(1/px) [bit/znak]
x=0
Maximálna entropia Hmax sa dosiahne pri rovnakej pravdepodobnosti všetkých znakov (teda pri rovnomernom rozdelení pravdepodobnosti), t.j. p=1/m.
Hmax=log2(m) [bit/znak]
Pri nerovnakej pravdepodobnosti výskytu jednotlivých znakov je H<Hmax.
Redundancia R. Nadbytočnosť informácií. Inak povedané, je to nadbytočnosť vyplývajúca z nedokonalosti zápisu informácií.
Hmax-H H
R = -------- = 1 - ------
Hmax Hmax
Vhodným prekódovaním je možné znížiť redundanciu k nule. Zníženie redundancie sa dosahuje
kompresiou dát. V niektorých prípadoch sa však cielene do informácií vnáša umelá redundancia. Tieto,
navyše vložené informácie sa využívajú na detekciu a korekciu chýb,
ktoré vznikli napríklad pri prenose informácie. Redundanciu štatisticky zoradených dát je možné
znížiť vhodným prekódovaním (tzv. entropickým kódovaním), ktoré využíva kratších znakov pre dáta
s vyššou pravdepodobnosťou a dlhšie pre menej časté. Príkladom je napríklad Huffmanove kódovanie.
Napísané podľa: Jiráček M.: Informační základy komprese dat, ST 12/99
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 1 0 0 0 1 1 3 2 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 3 1 0 1 1 2 3 2 3 1 0 1 1 2 3 2 3 1 1 0 0 0 0 0 0 0 0 1 1 1 1 3 2 3 1 3 1 3 2 3 2 1 1 1 2 3 2 3 1 0 0 0 0 0 0 0 1 0 0 1 3 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 1 0 0 0 0 0 0 0 0 0 1 0 1 2 3 2 3 2 3 1 3 2 3 2 3 2 3 2 3 2 3 2 1 0 1 1 1 1 1 1 1 0 0 1 2 3 2 3 2 4 2 4 2 1 2 1 2 1 2 1 2 3 2 3 2 1 2 3 2 3 1 0 0 1 1 2 3 2 3 2 4 4 4 4 4 4 4 4 4 4 4 4 4 1 4 2 4 2 3 2 1 1 0 0 0 0 1 3 1 1 1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 2 1 0 0 0 0 1 1 1 2 3 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 2 1 1 1 0 0 1 2 3 1 1 4 4 4 4 4 4 4 4 1 4 4 4 4 4 4 4 4 4 4 4 2 3 2 1 0 1 0 0 1 2 3 2 4 4 4 4 4 4 4 4 4 1 4 4 1 4 4 4 4 4 4 4 4 2 3 1 0 0 0 0 0 1 2 4 4 4 4 1 1 1 1 4 4 1 4 1 4 4 1 1 1 1 4 4 4 4 2 1 0 0 0 0 1 1 1 4 4 4 4 4 1 5 1 1 1 1 1 1 1 1 1 5 1 4 4 1 4 2 3 1 0 0 0 1 4 4 4 4 1 1 1 4 4 1 1 1 1 4 4 4 1 1 1 1 4 4 1 1 4 4 2 1 1 0 0 1 4 4 4 4 4 1 4 4 4 4 4 1 4 4 4 4 4 1 4 4 4 4 4 4 1 4 1 4 4 1 0 1 4 4 4 4 4 1 4 4 4 4 4 1 4 4 4 4 4 1 4 4 4 4 4 4 1 4 4 1 1 0 0 0 1 1 1 4 4 1 4 4 4 4 4 4 1 1 1 1 1 4 4 4 4 4 4 1 4 4 4 1 0 0 0 0 0 0 0 1 4 4 1 1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1 4 4 4 1 0 0 0 0 0 0 0 0 0 1 4 4 4 1 1 4 4 4 4 4 4 4 4 4 4 1 1 4 4 1 1 0 0 0 0 0 0 0 0 0 0 0 1 4 4 4 4 1 1 1 1 1 1 1 1 1 1 4 4 4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 4 4 4 4 4 4 4 4 4 4 4 4 4 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 4 4 4 4 4 4 4 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 2 2 2 2 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 2 2 2 2 2 2 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
Tabuľka, jednotlivé znaky sú vyjadrené pomocou Huffmanovho kódu
| znak | bin | počet | px | Huff. kód |
| 0 | 000 | 408 | 0,3984 |
0
|
| 1 | 001 | 231 | 0,2256 |
111
|
| 2 | 010 | 81 | 0,0791 |
1101
|
| 3 | 011 | 48 | 0,0469 |
11001
|
| 4 | 100 | 254 | 0,2480 |
10
|
| 5 | 101 | 2 | 0,0020 |
11000
|
Entropia H=2,0265 bit/symbol
Maximálna entropia Hmax=2,5850 bit/symbol
Redundancia R=0,2160
Prekódovaním napr. pomocou Huffmanovho kódu znížime redundanciu.
Pre dĺžku kódu bude platiť:
N
L=suma pi.li , kde pi je pravdepodobnosť výskytu znaku a li počet bitov Huffmanovho kódu.
i=0
Pričom vždy platí: L>=H.
L=(0,3984*1+0,2256*3+0,0791*4+(0,0469+0,002)*5+0,248*2)=2,1321 bit
Potom na zakódovanie sekvencie pozostávajúcej z N znakov, je potrebných v priemerne N*2,1321 bitov.Redundancia R=1-L/Hmax=0,1753
Pozn.: Výpočet dvojkového logaritmu z dekadického: log2(x)=log10(x)/log10(2)
Výsledkom Huffmanovho kódovania je v konečnom dôsledku kompresia. Pôvodne bolo potrebné vyjadriť každý znak pomocou 3 bitov. Pri rozsahu dát 32*32=1024 obrazových bodov (znakov) je potrebných na opis obrázku 1024*3bit/znak=3072 bitov. Ak obrazové body vyjadríme pomocou Huffmanových kódov, na opis obrázka nám postačí 1024*2,1321=2184 bitov, čo predstavuje faktor kompresie 1,4.