Editace stránky 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.''

=== Modely textu, kódování ===
[[Image:Komprese.png|right|thumb|604px|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í ===
{{Zkazky|
* '''komprese, obecně + komprese čísel (2008 Kopecký)''' - opět jsem neměl moc jasnou představu, kde je to využíváno - nicméně po lehkým naťuknutí jsem rovnou použil předchozí pohovor o indexaci dokumentů a správně řekl, že se to používá v tom invertovaném souboru pro kódování seznam těch dokumentů, kde se term vyskytuje. Pak jsem byl ještě poučen, že jak je ten seznam setřízen, tak se nekódují konkrétní čísla, ale přírustek od předchozího indexu. 
}}
Slajdy k [http://www.ksi.mff.cuni.cz/~zemlicka/pdf/compression.pdf OZD II] (od slajdu 21) (Fibonacciho, Eliasovy kódy, fázování)


==Znakové==

=== Huffmanovo kódování (statické, dynamické) (🎓🎓🎓) === 
{{zarovka 
| 
* JPEG 
* MP3,...
 | Huffmanovo k. se pouziva v poslední fázi u 
}}
{{Zkazky|
* '''Huffmanovo kódování (?)''' - stručně jsem popsal a nakreslil příklad k statické verzi, popsal jsem jak funguje dynamická, jak se mění strom atd.
* '''Huffmanovo kódovanie (Galamboš)''' - toto som vedel, takže sa v tom moc nevŕtal 
* '''Huffmanovo kódování - statické, dynamické (Holubová)''' - Hned na zacatku mi bylo receno, ze se mam zamerit na dynamicke H. kodovani. Mel jsem cokoliv zakodovat a dekodovat. 
}}
====Staticke Huffmanovo kodovaní====
{{zarovka 
| 
# Spočítáme frekvence výskytů symbolů (včetně mezer).
# Seřadíme znaky od nejmenší frekvence.
# Spojováním dvojic zleva vytváříme strom. Nové vrcholy zařazujeme do řady (co nejvíce doprava).
# Levé hrany jsou 0, pravé 1.
 | statické kodovani 
}}

:'''Vstup:''' seznam <math>n</math> zdrojovych jednotek ke kodovaní, <math>p</math> - usporadana posloupnost <math>n</math> vah (pravdepodobností) <math>p[i]</math> (<math>1 ≤ i ≤ n</math>) 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 <math>O(n)</math>

<pre>
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
</pre>

====Dynamické (Adaptivní) Huffmanovo kódování====
[[Image:ahc.png|right|thumb|394px|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 <math>T_1</math>, uzel <math>o</math>
:'''Výstup:''' modif. Huff. strom <math>T_2</math>

<pre>
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
</pre>

* <math>AL_{HD} ≤ 2 . AL_{HS}</math>, kde <math>AL_{HD}</math> je průměrná délka kódových slov dynamického Huffmanova kódování a <math>AL_{HS}</math> statického
{{TODO|příklad na nějakém textu}}
{{collapse|💡 '''Λ (Vitter)'''| - složitější úprava FGK s těmito vlastnostmi:
* počet výměn podstromů je nejvýše <math>1</math>, přidá se escape sekvenci pro první výskyt nového znaku
* minimalizuje nejen <math>\sum^n_{i=1} d[i] . p[i]</math> ale i <math>\sum^n _{i=1} d[i]</math> a <math>max_i d[i]</math>
* <math>AL_{HD} ≤ AL_{HS} + 1</math> (nejlepší hodnota mezi dynamickými Huffmanovými metodami)
}}
{{Zdroje|
* Slajdy k [http://www.ksi.mff.cuni.cz/~zemlicka/pdf/compression.pdf#40 OZD II] (od slajdu 40) (statické, adaptivní kódování)
* Dobře popsáno také na stránkách k [http://www.ms.mff.cuni.cz/~kopecky/vyuka/dis/ DIS] 530
* http://www.stringology.org/DataCompression/fgk/index_en.html
* http://www.stringology.org/DataCompression/ahv/index_en.html 
}}

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

{{zarovka|1=
abeceda = {J,U,!} 
: Pᵢ ={1/2, 1/4 , 1/4}
<pre>
  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)</pre>
<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>
|2=aritmeticky zakodovat "JUJ!"
}}
=== Aritmetické kódování  ===
[[Soubor:400px-Arithmetic encoding.svg.png|400px|thumb|right|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".
<pre>λ -> ⟨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)
</pre>
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í{{zdroje|1=
:''viz [[wen:Arithmetic coding]]''
:Slajdy k [http://www.ksi.mff.cuni.cz/~zemlicka/pdf/compression.pdf#47 OZD II] (od slajdu 47)
:Dokumenty k [http://www.ms.mff.cuni.cz/~kopecky/vyuka/dis/11/dis11_v1.html DIS] (myslím, že v posledním kroku příkladu je chyba)
}}

==Slovníkové metody==
=== LZ algoritmy  ===
{{zkazky|
* '''Komprese PNG a GIF (2012, Grafika, Zara)''' -  Nejhorsi otazku sem si nechal na konec...tuhle sem absolutne nemel pripravenou, navic ji zkousel Zara Snazil sem se co nejdyl mluvit o obecnych metodach komprese obrazu ( RLE, Huffman, LZ77, LZW, Aritmeticke kodovani, Transformace obrazu ) ...to me ale Zara brzo zarazil ze to moc nesouvisi s tim na co se me ptaji at zacnu byt konretnejsi Tak sem otocil papir a tam sem mel par strohych poznamek o PNG a GIF formatech Kdyz sem to zacal komentovat tak me Zara prerusil at je spis vzajemne porovnam kdyz o nich mluvim. Co konkretne ho zajimalo: oba bezeztratove, LZ77 vs LZW, ze oba pouzivaji progresivni metodu zobrazeni, Proc muze mit PNG lepsi kompresni pomer nez GIF kdyz GIF pouziva modernejsi LZW oproti LZ77 ( odpoved ze LZ77 muze byt lepsi nez LZW na nekterych vstupech protoze je to uplne neco jinyho se mu moc nelibila...spravna odpoved je podle Zary ze tam je lepsi prediktor) No casto sem tady tipoval, hodne sem toho nevedel, parkrat me Zara poucil jak ze to vlastne je...celkem bida, ale mel sem pocit ze k vyhazovu sem mel jeste furt nejakou rezervu
}}
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:
<pre>	fraze   a   b   c   d
	cislo   0   1   2   3</pre>
*chod alg.
<pre>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   -
</pre>
*	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ů,...)
{{zdroje|
Slajdy k [http://www.ksi.mff.cuni.cz/~zemlicka/pdf/compression.pdf#56 OZD II] (od slajdu 56) (LZ77, LZSS, LZ78, LZW a další)
}}

== komprese bitových map, ==
:Slajdy k [http://www.ksi.mff.cuni.cz/~zemlicka/pdf/compression.pdf#92 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, ==
[http://www.ksi.mff.cuni.cz/~zemlicka/pdf/2011/matcomp.pdf OZD II]

== Burrows-Wheelerova transformace. ==
http://cs.wikipedia.org/wiki/Burrowsova-Wheelerova_transformace