Implementace databázových systémů/Komprese: Porovnání verzí

Verze z 11. 5. 2015, 15:08

okruhy 09/10: Komprese dat: predikce a modelování, reprezentace celých císel, obecné metody komprese, komprese textu. Huffmanovo kódování (statické, dynamické), aritmetické kódování, LZ algoritmy, komprese bitových map, rídkých matic.

okruhy 14/15: Komprese dat: modely textu, kódování, Huffmanovo kódování (statické, dynamické), aritmetické kódování, LZ algoritmy, komprese bitových map, rídkých matic, Burrows-Wheelerova transformace.

Modely textu, kódování

komprese textu

obecné typy redukce dat:

• ztrátová (nazývá se kompakce) - např. obraz, zvuk, video
• bezeztrátová (nazývá se komprese a je reverzibilní přes dekopresi)

Proces komprese má 2 fáze:

• modelování (modely textu) - přiřazení pravděpodobností jednotkám textu (znaky nebo m-tice znaků pevné délky)
• kódování - transformace do nového kódu pomocí modelu

prefixový kód - jednotliva kodova slova nejsou prefixem zadneho jineho slova

dělení modelů:

• statická - model je statický pro všechny dokumenty (uložen jednou)
• semiadaptivní (polostatické) - každý dokument má vlastní model (pošle se s dokumentem)
• dynamická (adaptivní) - oba algoritmy si model tvoří na základě již zpracovaných dat (musí se dekodovat od zacatku)

kódování

Slajdy k OZD II (od slajdu 21) (Fibonacciho, Eliasovy kódy, fázování)

Znakové

Huffmanovo kódování (statické, dynamické) (🎓🎓🎓)

Staticke Huffmanovo kodovaní

Vstup: seznam $ n $ zdrojovych jednotek ke kodovaní, $ p $ - usporadana posloupnost $ n $ vah (pravdepodobností) $ p[i] $ ($ 1 ≤ i ≤ n $) jejich vyskytu ve zprave

Vystup: kodova slova dana zretezením ohodnocení hran na cestach od korene k jednotlivym listum binarního stromu

• výsledný strom se nazývá Huffmanův, výsledný kód je prefixový
• místo pravděpodobností můžeme použít i četnosti znaku, ohodnocení hran stromu pomocí 0 a 1 je konvencí (je tudíž možno použít i ohodnocení opačné)
• Huffmanuv i Shannon-Fanův kód je možné generovat v čase $ O(n) $

BEGIN
 ∀ jednotku i vytvoř list o(p[i])
 (uzel ohodnocený pravděpodobností p[i]);
 k := n;
 WHILE k ≥ 2 DO
  BEGIN
   vyber z p dvě nejmenší nenulové p[r] a p[s], kde r ≠ s;
   q := p[r]+p[s];
   vytvoř uzel ohodnocený q;
   hranám < o(q); o(p[r]) > a < o(q); o(p[s]) >
    přiřaď ohodnocení 0 a 1;
   p[r] := q; p[s] := 0; k := k-1
  END
END

Dynamické (Adaptivní) Huffmanovo kódování

Sourozenecká vlastnost stromu: ∀ uzel má sourozence a četnosti v uspořádání podle č.šipky neklesají

• strom reorganizován podle toho, jak se mění pravděpodobnosti v průběhu kódování (tj. poruší se sourozenecké pravidlo)
• nepředpokládají se žádné informace o pravděpodobnostech zdrojových jednotek (strom ale můžeme inicializovat vstupní abecedou)

FGK (Faller, Galagher, Knuth)

Vstup: daný Huffmanův strom $ T_1 $, uzel $ o $

Výstup: modif. Huff. strom $ T_2 $

BEGIN
 current:=o;
 WHILE current ≠ root DO
  BEGIN
  vyměň uzel a jeho příp.podstrom v current s uzlem o', který má nejvyšší pořadí mezi uzly se stejnou frekvencí;
  četnost[current]++
  current:=predcessor(current)
 END
END

• $ AL_{HD} ≤ 2 . AL_{HS} $, kde $ AL_{HD} $ je průměrná délka kódových slov dynamického Huffmanova kódování a $ AL_{HS} $ statického

💡 je optimální pro pravděpodobnosti výskytů znaků, které jsou mocninami 1/2.

aritmetické kódování,

  0|---J---|1/2----------U----|(1/2+1/4) -------------!---|1
  0|---J---|1/4----------U----|(1/4+1/8) -------------!---|1/2 
1/4|---J---|(1/4+1/16)---U----|(1/4+1/16+1/8+1/32) ---!---|(1/4+1/8)

vyjadruje kod jako interval z <0;1).

Komprese: rozdelim interval <0;1) na useky odpovidajici relativnim cetnostem jednotlivych znaku. Pri kodovani znaku se z intervalu <0;1) "stane" interval <x;y) odpovidajici kodovanemu znaku. Tento interval se pote vezme jako jednotkovy do dalsi iterace.

Reprezentujeme-li interval dvojici(L,S), kde L je dolni mez intervalu a S jeho delka, postupny vyvoj techto velicin muzeme vyjadrit takto:

L := L + S. cpᵢ

S := S . pᵢ

kde pᵢ je pravdepodobnost vyskytu kodovaneho znaku a cpᵢ = $ \sum_{j=1}^i $ pⱼ neboli kumulovana pravdepodobnost. Pocatecni nastaveni je L=0 a S=1

Dekomprese: rozdelim interval <0;1) na useky odpovidajici relativnim cetnostem jednotlivych znaku. Znak intervalu, ktery obsahuje kodovy interval dam na vystup a v tomto intervalu dale hledam.

Nevyhody: je treba aritmetiky velke presnosti, behem kodovani neni vystup – oboje lze ošetřit tím, že jakmile jsou známé první bity, tak se odešlou na výstup a dál se pokračuje se zbylým intervalem, který se jakoby posune o řád níž (např. pokud vím, že je interval [0; 0,001) v bitovém kódování, tak výsledný kód bude určitě vypadat [0,00???; 0,00???))

Priklad: Mame abecedu {a,b,c,d} s pravdepodobnostmi 1/2, 1/4, 1/8 a 1/8 a kodujeme "abc".

λ -> <0;1)  
'a' - <0;1) -> <0;1/2)
'b' - <0;1/2) -> <1/4;3/8)
'c' - <1/4;3/8)-> <25/64; 26/64)

kód není prefixový => je třeba nějaký speciální znak pro odlišení konce kódu

oproti Huffmanovu kódování výhodné zejména pokud jeden znak je mnohem pravděpodobnější než ostatní

Slovníkové

LZ algoritmy,

Slajdy k OZD II (od slajdu 56) (LZ77, LZSS, LZ78, LZW a další)

komprese bitových map,

Slajdy k OZD II (od slajdu 92)

• pomocí Huffmanova kódování
  • kódováním posloupností pevné délky
  • kódování běhů (posloupnost nul ukončených jedničkou apod.)

rídkých matic,

OZD II

Burrows-Wheelerova transformace.

http://cs.wikipedia.org/wiki/Burrowsova-Wheelerova_transformace