Implementace databázových systémů/Komprese: Porovnání verzí
Z ωικι.matfyz.cz
| Řádka 19: | Řádka 19: | ||
*semiadaptivní (polostatické) - každý dokument má vlastní model (pošle se s dokumentem) | *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) | *dynamická (adaptivní) - oba algoritmy si model tvoří na základě již zpracovaných dat (musí se dekodovat od zacatku) | ||
| + | |||
| + | ==Znakové== | ||
=== Huffmanovo kódování (statické, dynamické) (🎓🎓🎓) === | === Huffmanovo kódování (statické, dynamické) (🎓🎓🎓) === | ||
| Řádka 119: | Řádka 121: | ||
: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) | :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é== | |
=== LZ algoritmy, === | === LZ algoritmy, === | ||
{{zkazky| | {{zkazky| | ||
Verze z 11. 5. 2015, 14:59
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í
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)
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
Tato část je neúplná a potřebuje rozšířit. příklad na nějakém textu
| 💡 Λ (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.
aritmetické kódování,
| 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> |
| další zdroje |
|---|
|
Slovníkové
LZ algoritmy,
| Zážitky ze zkoušek |
|---|
|
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,
Burrows-Wheelerova transformace.
http://cs.wikipedia.org/wiki/Burrowsova-Wheelerova_transformace
Reprezentace celých čísel (zrušeno 2010)
| Zážitky ze zkoušek |
|---|
|
Slajdy k OZD II (od slajdu 21) (Fibonacciho, Eliasovy kódy, fázování)
