Implementace databázových systémů/Komprese
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.
Obsah
Modely textu, kódování
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í
| Zážitky ze zkoušek |
|---|
|
Slajdy k OZD II (od slajdu 21) (Fibonacciho, Eliasovy kódy, fázování)
Znakové
Huffmanovo kódování (statické, dynamické) (🎓🎓🎓)
| Huffmanovo k. se pouziva v poslední fázi u
|
|---|
|
| Zážitky ze zkoušek |
|---|
|
Staticke Huffmanovo kodovaní
| statické kodovani
|
|---|
|
- 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í
- 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
| 💡 Λ (Vitter) |
|---|
- složitější úprava FGK s těmito vlastnostmi:
|
| další zdroje |
|---|
|
💡 je optimální pro pravděpodobnosti výskytů znaků, které jsou mocninami 1/2.
| aritmeticky zakodovat "JUJ!": |
|---|
|
abeceda = {J,U,!}
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) <1/4+1/8+1/16+1/32; 1/4+1/8> =bin <1/4+1/8+1/16+1/32; 1/4+1/8> |
Aritmetické kódování
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ᵢ = Σⁱⱼ₌₁ pⱼ neboli kumulovana pst. 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í
| další zdroje |
|---|
|
Slovníkové metody
LZ algoritmy
| Zážitky ze zkoušek |
|---|
|
Kompresni algoritmy vytvareji pri sve praci slovnik, ktery pouzivaji ke kodovani vstupu. Vsechny metody jsou adaptivni, pri cteni kodu vytvari slovnik a zaroven taky generuji vysledny kod. Jsou kodovany "fraze" (shluky znaku nebo slova), cislovany ve slovniku od nuly.
Existuji dve zakladni kategorie:
- organizujici slova prirozeneho jazyka (BSTW)
- organizujici retezce (LZ*)
LZW - Posíláme jen odkaz do slovníku (na začátku je v něm abeceda)
- Komprese:pocatecnimi frazemi jsou jednotlive znaky. V kazdem kroku se najde nejdelsi fraze ve slovniku shodna se vstupem a jeji kod se zapise. Nova fraze vznika pridanim dalsiho znaku na konec akt. pouzite fraze.
- pr. vstup abacdacacadaad
- poc. tabulka:
fraze a b c d cislo 0 1 2 3
- chod alg.
krok vstup fraze kod nova # 1 abacdacacadaad a 0 ab 4 2 bacdacacadaad b 1 ba 5 3 acdacacadaad a 0 ac 6 4 cdacacadaad c 2 cd 7 5 dacacadaad d 3 da 8 6 acacadaad ac 6 aca 9 7 acadaad aca 9 acad 10 8 daad da 8 daa 11 9 ad a 0 ad 12 10 d d 3 -
- Dekomprese: zacina se tak jako u komprese se slovnikem, ve kterem jsou pouze znaky. Nova fraze se tvori z predchozi plus prvniho pismena aktualni (je mozne, aby "nova" fraze sla hned na vystup - jeji zacatek znam - je z predchozi a posledni pismeno bude shodne s prvnim.
- Komprese i dekomprese vytvori stejny slovnik
LZ77 - Okénka (posíláme 3 údaje)
- na jeho zakladu jsou postaveny komprimacni programy soucasnosti(zip, arj,...)
- metoda typu sliding window - posunuju vstupem okenko, pomoci ktereho i koduju. Delim ho na dve casti hledaci (az 7 znaku a vyhledove az 7 znaku). Zprava je kodovana trojicemi <a, l, c> a je posun od aktualni pozice zpet, l je delka jiz kodovane casti ktera se znovu pouzije a c je novy znak. Kazda trojice tak zakoduje nejmene jeden a nejvice 7 znaku.
- proč zrovna 7 – vejde se to tak akorát do 3 bitů a je to rychlé
- pr. EMA MELE MASO se zakoduje <0,0,E>, <0,0,M>, <0,0,A>, <0,0,MEZERA>, <3,1,E>, <0,0,L>, <2,1,MEZERA>, <5,1,A>, <0,0,S>, <0,0,O>,
Dalsi algoritmy - existuje spousta variant LZ algoritmu (LZ78 – starší obdoba LZW, LZJ – variace na LZW, kde je omezena délka kódovaných řetězců,...)
| další zdroje |
|---|
|
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.)
Řídké matice
řídká matice obsahuje z velké většiny nuly, lze reprezentovat např.
- naivně ve tvaru matice (příliš veliké a neefektivní)
- seznamem indexů, kde se nachází nenulová hodnota
- pomocí r^d (radix) stromů
| Burrowsova-Wheelerova transformace | |||
|---|---|---|---|
| Vstup | Všechny rotace |
Seřazení rotací |
Výstup |
^BANANA@ |
^BANANA@ @^BANANA A@^BANAN NA@^BANA ANA@^BAN NANA@^BA ANANA@^B BANANA@^ |
ANANA@^B ANA@^BAN A@^BANAN BANANA@^ NANA@^BA NA@^BANA ^BANANA@ @^BANANA |
BNN^AA@A |
Burrows-Wheelerova transformace (BWT) - Matice, permutace
Pomocný algoritmus pro změnu pořadí symbolů (permutaci), tak aby se dobře komprimoval (často vyskytující se symboly dá k sobě).
- používá se v bzip2
- tranformace
- Ze vstupního řetězce (zakončeného symbolem EOF) vytvoří všechny jeho možné rotace.
- Tyto se dále klasicky seřadí.
- Ze seřazeného pole rotací původního řetězce se do výstupního zapíše postupně od počátku poslední symbol z každé rotace.
komprese - move-front jako BSTW akorát že inicializujeme slovník abecedou
BSTW
- metoda nenavazujici na LZ
- na zacatku prazdny slovnik, ukladaji se do nej cela slova, vzdy na zacatek. Za kazde slovo je poslan jeho index ve slovniku nebo cislo o jedna vyssi nez je pocet slov ve slovniku spolu s novym slovem. Po kazdem "pouziti" slova ze slovniku se to slovo presune na zacatek slovniku.
- Pr. kazdy sofsemista musi kazdy den bdit cely den
- zakoduje se na : 1 kazdy 2 sofsemista 3 musi 3 (<--- ted uz znamena kazdy) 4 den 5 bdit 6 cely 3 (=den)
| další zdroje |
|---|
|
http://cs.wikipedia.org/wiki/Burrowsova-Wheelerova_transformace
|
