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
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
dělení modelů (💡 jako by slovníky):
- statické - model je statický pro všechny dokumenty (uložen jednou)
- semiadaptivní (polostatické) - ∀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 |
|---|
|
Kód K = (A,C,f), kde
- A = {a₁, ..., aₙ} je zdrojová abeceda, |A| = n
- C = {c₁, ..., cₘ} je cílová abeceda, |C| = m, obvykle C = {0,1}
- f: A → C⁺ je prosté kódové zobrazení znaků z abecedy A do prostoru slov v abecedě C.
- vlastnosti:
- jednoznačně dekódovatelný - ∀zakódovaný (cílový) řetěz Y ∃ max. 1 zdrojový řetěz X že f(X) = Y.
- prefixový - jednotliva kodova slova nejsou prefixem zadneho jineho slova
- 💡 prefixový ⇒ jednoznačně dekódovatelný (opačně neplatí)
Entropie (míra informace) znaku ai v textu je rovna hodnotě E(aᵢ) = -log( "pst výskytu znaku aᵢ v textu" ) bitů.
- 💡 tj. "obrácená hodnota" - čím je znak častější tím menší má entropii = tím méně informace nese (tím menší počet bitů je potřeba na její reprezentaci)
- 💡 použítí viz: IDF/ITF
- prům. entropie 1 znaku: AE(A) = -Σ ("pst výskytu znaku ai v textu") log( "pst výskytu znaku aᵢ v textu" )
- očekávaná délka 1 znaku přes ∀znaky a jejich psti
- entropie zprávy: E(A) = E(a₁...aₖ) = -Σ log( "pst výskytu znaku aᵢ v textu" )
- 💡 tj. součet entropií znaků ve zprávě
- platí že délka zakódované zprávy je |f(A)| > E(A)
- redundance: R = |f(A)| - E(A)
| speciální případy pro nekonečné množiny s nerovnoměrnou pravděpodobností výskytu znaků |
|---|
|
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 $
| Dynamické kodovani | dekódování |
|---|---|
|
|
- $ 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
příklad kódování "aa bb cc":
0. začneme stromem s 1 speciálním vrcholem
?(0)
1. kódujeme první znak zprávy a, vypíšeme prázdný řetězec následovaný definicí znaku a, vložíme do stromu a aktualizujeme frekvence ve stromu
- Input: aa bb cc
- Output: a
- OutBin: 000
(1) 0/ \1 ?(0) a(1)
2. kódujeme další a, pouze vypíšeme jeho kód a aktualizujeme frekvence ve stromu
- Input: aa bb cc
- Output: a1
- OutBin: 0001
(2) 0/ \1 ?(0) a(2)
3. kódujeme "mezeru", vypíšeme kód spec.uzlu ? a definici znaku "mezera", vložíme do stromu a aktualizujeme frekvence ve stromu (žádné výměny nejsou potřeba)
- Input: aa_bb cc
- Output: a10_
- OutBin: 00010001
(3) 0/ \1 (1) a(2) 0/ \1 ?(0) _(1)
4. kódujeme b, vypíšeme kód ? a definici b, vložíme do stromu a aktualizujeme frekvence ve stromu (žádné výměny nejsou potřeba)
- Input: aa bb cc
- Output: a10 00b
- OutBin: 0001000100010
(4)
0/ \1
(2) a(2)
0/ \1
(1) _(1)
0/ \1
?(0) b(1)
5. kódujeme další b, vypíšeme kód b a aktualizujeme frekvence ve stromu -> porušíme sourozeneckou vlastnost, musíme prohodit uzly na úrovni před kořenem a dokončíme aktualizaci frekvencí
- Input: aa bb cc
- Output: a10 00b001
- OutBin: 0001000100010001
(4)
0/ \1
(3) a(2)
0/ \1
(2) _(1)
0/ \1
?(0) b(2)
(5)
0/ \1
a(2) (3)
0/ \1
(2) _(1)
0/ \1
?(0) b(2)
| 💡 Λ (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
| Identifier | HasInternet | Bitmaps | |
|---|---|---|---|
| Y | N | ||
| 1 | Yes | 1 | 0 |
| 2 | No | 0 | 1 |
| 3 | No | 0 | 1 |
| 4 | Unspecified | 0 | 0 |
| 5 | Yes | 1 | 0 |
Bitmapy se používají jako indexy pro atributy s malými doménami (napr.: muž/žena, low/medium/high,...)
- velikost bitmapy se rovná počtu záznamů * velikost domény ⇒ rostou lineárně s databází
- dotazování se dělá pomocí bitových logických boolovských operací
- Komprese
Uvažujeme bitovou mapu, resp. její j-tý sloupec (i-tá pozice říká, že záznam i odpovídá určité j-té hodnotě, nebo např. že dokument i obsahuje term j)
Uvažujeme předpoklad, že existence bitu 1 nebo 0 je nezávislá (pravděpodobnost p, že je tam 0, (1-p), že je tam 1). Z bitového řetězce lze spočítat pravděpodobnost p.
Rozdělíme bitový řetězec na bloky délky k a pro všechny možné bloky vzhledem k umístění jedniček (2^k) vypočítáme jejich pravděpodobnost. Potom pomocí Huffmanova kódování přiřadíme jednotlivým blokům kódy, kterými zakódujeme bitový řetězec. Čím větší p a k, tím větší zisk komprese, ale při velkém k (> 10) exponenicálně narůstá slovník, což nemusí být v praxi použitelné.
Druhou možností je nekódovat bloky pevné délky, ale běhy nul, zakončené jedničkou – tj. 1, 01, 001, 0001, atd. až do pevně stanovené velikosti m (tj poslední blok bude m nul). Spočítáme pravděpodobnosti pro běhy s jedničkou: (p^j)(1-p) – j je počet nul, zbylá pravděpodobnost do 1 (100%) bude odpovídat běhu ze samých nul. A opět Huffmanovým kódováním přiřadím kódy. V tomto případě slovník roste s k pouze lineárně, ale je zase hodně závislý na pravděpodobnosti, že se na vyskytuje 0 (když se blíží k 1, pak je to velice výhodné, jinak zisk komprese klesá)
- 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.)
Slajdy k OZD II (od slajdu 92)
Řídké matice
řídká matice obsahuje z velké většiny nuly (např. vektorový index - cca 90% nul), lze reprezentovat:
- naivně ve tvaru matice (příliš veliké a neefektivní) ( $ \vec{d} $ = [w1, w2, ... , wk] )
- seznamem indexů, kde se nachází nenulová hodnota ( $ \vec{d} $ = [j1:wj1, j2: wj2, ... , jk: wjk] )
- kontrukce posuny - matici rozdělit na řádky, vhodně posuneme řádky (zaznamenáme), složíme řádky (sečteme), zaznamenáme do kterého řádku políčko patří
- viz: OZD II
| 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
|
