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

Verze z 15. 5. 2015, 11:04

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

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

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)

f: A → C⁺ je prosté kódové zobrazení znaků z abecedy A do prostoru slov v abecedě C

Kódování (čísel)

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ý kód je jednoznačně dekódovatelný

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

• prům. entropie 1 znaku: AE(A) = -Σ ("pst výskytu znaku ai v textu") log( "pst výskytu znaku aᵢ v textu" )
• entropie zprávy: E(A) = E(a₁...aₖ) = -Σ log( "pst výskytu znaku aᵢ v textu" )
  • platí že délka zakódované zprávy je |f(A)| > E(A)
  • redundance: R = |f(A)| - E(A)

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.

  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)

Aritmetické kódování

Diagram ukazující dekódování čísla 0.538 (kruhová tečka) pro ukázkový model. Oblast je rozdělená do podoblastí úměrně k četnostem symbolů, potom je podoblast obsahující tečku postupně rozdělen stejným způsobem.

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í

Slovníkové metody

LZ algoritmy

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:

1. organizujici slova prirozeneho jazyka (BSTW)
2. 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ů,...)

komprese bitových map,

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, 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ů

OZD II

^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)