KOMPRESE DAT Flashcards
Otázky kopírují témata v okruzích, avšak ne každá otázka odpovídá jedné otázce z okruhů. Některé státnicové otázky jsou rozděleny podle ucelených celků každé státnicová otázky.
Run-length encoding, RLE
- myšlenka, příznak, min. vel
- bmp
- efektivnější může být rle s předzpracováním vstupu dif. kód
- příklad
Move-to-front, MTF
- nejedná se o kódování, ale o transformaci vstupu, která usnadňuje následné kódování
- myšlenka (abeceda jako seznam, nejčastěji vyskytované symboly na začátku)
- lokálně adaptivní
- proč je užitečné mít symboly seřazeny?
- př.
- Varianty: move-ahead-k, wait-c-and-move, posun celých slov při kódování textu
Kódování čísel, unární kód
- při kódování čísel uvažujeme N čísla (celá či rac. lze na přir. bijektivně zobrazit)
- fixed to variable
Unární kódování
- pro N čísla
- prefix, délka i+1
- 1^i + 0
- opt. při P(2^-i)
Eliasovy kódy
Alfa
- pro i >= 0
- a(i) = 0^i+1
- l(a(i)) = i+1
- prefix, ale long
- opt. při P(i) = 2^-i
Beta
- pro i >= 0
- binární repr ve dvoj soustavě
- l(b(i)) = L log2i L + 1
- optimální, ale není prefixový
Gamma
- pro i >= 1
- g(i) = 0^(l(b(i))-1) + b(i)
- l(g(i)) = 2 L log(i) L + 1
- prefix, ale opt. při P(i)= 1/2i^2
Delta
- pro i >= 1
- d(i) = 0^l(b(l(b(i))))-1 + b(l(b(i))) + b(i) bez první 1
- l(d(i)) = 2 log(log(2i)) + log(i) + 1
(každej log je floorovanej)
- P(i) = 1/ 2i*log(2i)^2
Omega
- pro i >= 1
- rekurzivní alg pro encode:
1. zapiš 0
2. pokud i=1 konec
3. zapiš b(i) (vlevo)
4. i=l(b(i)) - 1 (!!)
5. go to 2
decode:
1. i=1
2. pokud je první násl bit 0, konec, i na výstup
3. i++
4. i = i dalších bitů do dekadické soustavy
5. go to 2
délka: suma j=1->k (log(i)^j +1) +1
Fibonacciho kód
+ Zeckendorfův teorém - tvrzení, říkající, že každé přirozené číslo lze jednoznačně zapsat jako součet jednoho nebo více různých členů Fibonacciho posloupnosti, přičemž žádné dva použité členy nejsou po sobě jdoucí.
- kódování podle posl 1 2 3 5 8 13
- zleva (ne zprava jako u bin)
- přidání 1 nakonec pro poznačení konce, prefix
Golomb
- parametr j > 0
- části kódu, i/j unary a i mod j binary
- pokud parametr je mocnina 2, binarni cast se koduje na log2(j) pocet bitu
- jinak L log2(j) L-bitove se koduje prvnich 2^ceil(log2(j)) -j hodnot zbytku vcetne nuly
- zbyle hodnoty ceil(log2(j)) bitove
- golomb-ricovo kodovani, pokud je j mocnina 2, efektivnejsi. FLAC, MPEG-4, for lossless audio
Tunstall
- blokový
- vzorec pro k
- všechny kódy se nemusí využít
- iteruje se tak dlouho, dokud počet symbolů je menší nebo rovno 2^k
- vezmeme nejpravděpodobnější symbol či řetězec symbolů a ten spojujeme se všema ostatníma
Shannon-Fan
- fixed to variable
- tabulka podle četnosti
- půlíme sloupec na 2 skupiny stejné pravděpodobnosti, shora potom 1, druhé sk 0 (záleží na impl)
- opakujeme dokud nelze dělit dál
- pokus o opt prefix, easy implement, ale huffman produkuje lepší kódování
- opt v případech, kdy součet pravd podmnož je stejný
- příklad, pravd. 0,5 0,25 0,25 0,125 0,125
Huffman semi-adaptive
- podobné shannon-fano, ale obecně produkuje lepší výsledky a je opt. prefix
- nejopt stejne jako shann, pokud pravd mají negativní mocniny dvojky
- seřazení symbolů podle pravd., nejmene pravd se kombinuji pro vytvoreni symbolu se souctem pravd.
- takto se pokrac dokud neni soucet 1
- soucet vsech vnitrnich pravd je prumer bit/symbol
- existuje 2^n-1 různých huffmanových stromů/kódů pro n symbolů
- očislovani i spojovani zalezi na implementaci, ale vsechny moznosti prodkuji stejne efektivni kompresi
- Dekoder - predani stromu moc, predani kodu nejednoznacne, proto se posilaji pravdepodobnosti symbolu a strom si spocita dekoder sam, pote easy
Huffman adaptive
- vyhody oproti semi-adapt v praxi
- semi-adapt predpokl ze jsou pravd. zname a nebo prochazi vstup dvakrát:
1. zjisteni pravdepodobnosti
2. tvorba stromu
3. zakodovani vstupu (2. pruchod)
v praxi zdlouhave. adapt huff to resi adaptivne, pri prvnim cteni vytvari strom a rovnou koduje. DEKODER tento proces zrcadli.
- escape symbol pro dekoder, aby vedel, že následuje nový symbol
- escape symbol ve strome vzdy but uplne nalevo ci napravo (000.. / 111..)
- uzly maji tzv sibling property - váhy/četnosti uzlů. kazdy nelistovy uzel ma presne dva potomky a vaha leveho musi byt <= sousedovi vpravo, jinak se prohazuji
- jejich rodic ma vahu jako soucet potomku
alg:
1. tvorba stromu s escape symbolem jako koren
2. cyklus: nacteni noveho symbolu
3. jedna se o novy symbol?
a) ano - na vystup kod pro escape symbol
následuj kódem pro daný symbol
b) ne - na vystup kod symbolu
přičti četnost daného symbolu
zkontroluj sibling property
- UPDATE TREE
Aritmetické kódování
- kódování vstupu na bin repr real number z intervalu [0;1)
- negativa huffmana, ideal při neg moc 2, pokud mame sym s P 0.4, dle teorie informace staci 1.32 bit
- takze jelikoz kazdy sym celocisel vel kodu, kazdy sym je zakodovan az +1 oproti entropii
- AK prirazuje kod celemu vstupu takze ztrata +1 oproti entropii se plynule rozlozi po celem vstupu - teorie
Postup:
1. start s intervalem [0;1), postupné zužování intervalu čtením symbolů na vstupu
2. čím užší interval, tím více bitů potřeba, více pravd sym zužují interval pomaleji
3. nakonec po dosažení konečného podintervalu se zvolí číslo reprezentující interval s nejnižší bitovou reprezentací
near optimal, fast, oddělení modelování od samotného kódování
Příklad (a,b,c) (0.2,0.4,0.4) input: cba
1. hledání podintervalu kumulativním dělením
2. binární expanze, nález binární hodnoty z intervalu
dekód - EOF symbol
inportant najít plně uzavřený podinterval, aby bylo kód prefix
Velké vstupy - extrémně úzký interval - příklad byl nekonečnou přesností
- v praxi se používá kon. přes., kompresně velmi blízko teoretickému modelu
- periodické přeškálovávání intervalu (sketch example)
Kontextové kódování, PPM
- běžné static metody mají fáze - modelování dat + kódování
- model přiřazuje symbolům pravděp., může být static/dynamic, ale převážně je založen na přístupech:
1. Frekvence - častější symb měnší kód, static/dyn
2. Kontext - model zohledňuje kontext symbolu při přiřazování pravděp. - jelikož dekodér nevidí do budoucnosti, používá se pouze kontext předchozích symbolů
- technicky tyto metody použ Markovův model k-tého řádu
- PPM je ideální příklad kontext. kód
Prediction with partial match
-nezjišťují se všechny kontexty dané abc, ale pouze kntxty na vstupu
-escape symbol znač. neex/první výskyt sym v daném kontxt
- k v praxi 5,6, míra komprese nejprve roste, poté klesá (větší kontexty bývají neaktuální), více kódování escape symbolu
- adaptivní modelov pravdp výsk sym v postupně zkracujícím se kntxtu, což je posloupnost bezprostředně předch symb na vstupu
Alg:
přiřaď umělé kontexty
while načti symbol a€A ze vstupu:
- k ← min(MAX, přečtené symb-1)
- while k >= 0 and n(alc^k) = 0:
— zapiš na výstup escap sym v c^k
— k ← k-1
- zapiš na výstup a v c^k
input, A, k
umělý kontext c^-1 = 1, ost. 0
c0 - ck
příklad podle alg, při while testu n=0 zapiš do tabulky počet předchozích výskytů daného symbolu v daném kontextu
Blokové třídění
- třídění bloku dat, kódování jinak, většinou mtf, kvůli opakujícím se posloupnostem
- nepoužívá podm pravděpodobnosti výskytů symbolů ani posloupností
kódování:
př. barbora
- vytvoří se n-1 permutací bloku, každý rotován o 1 symbol doleva
- tyto bloky se vzájemně seřadí lexikograficky
- na výstup jde poslední sloupec takto seřazeních bloků + index původního seřazení symbolů v uspořádaném sloupci
dekód
- vytvoříme dva sloupce, pravý obsahuje symboly ze vstupu, levý bude jejich seřazení
- spojíme šipkami symbol zlevého sloupce s jeho sousedem vpravo (stejné pořadí shora)
- začneme řádkem, který symbolizuje číslo na vstupu a zleva doprava se pohybujeme podle šipek, zprava doleva vodorovně - posloupnost symbolů zleva tvoří dekód
v praxi nevytváříme n-1 posunů vlevo (paměť), stačí nám ukazatel na odp. symbol
LZ77
Slovnikove metody
- slovnik frazi - staticky (nemenny př pro zname opakujici se fraze v datech, spec přip) / dynamicky (pridavat, mazat)
-slov met vhodne pro opakuj se fraze retezcu, pokud je vsak opakovani vzacne, vysledna komprese muze mit jeste vetsi velikost nez original, proto ex nekolik pristupu a metod
- tou prvni metodou, nejmene efektivni a nepouzivanou je lz77
- Lempel, Ziv, 1977 / LZ1
- Sliding window - search buffer (1000’ B) + look ahead buffer (10’ B) (slovnik je zde search buffer)
- Token (offset, delka, next symbol) 3 Bytes na výstup, poté posun okna o delku + 1 (symbol)
- asymetrická komprese - dekomp fast
příklad - výběr poslední nalezené shody zjednoduš praci dekoderu a velikost offsetu by nemela hrat roli pokud je repr 1 Bytem
-ALE pokud kombinace s huffmanem, tak mensi offsety budou mit mensi kody - žádná nalezená shoda (na zacatku) token (0,0,”s”)
LZSS - 3 benefits oproti LZ77
1. look ahead buffer je circular queue (posun pointeru a prepisovani, snadna prace, neni potreba posouvani)
2. search buffer je binární vyhl strom s lexikograf řazením (levy potomek obsahuje nizsi hodnoty nez pravy, vyhledavani logaritmicky rychlejsi)
3. token má 2 pole (pokud neni shoda, neplytva se 3 symboly, vystupem je nekomprimovany znak symbolu (vetsinou v ASCII), oboji vsak predchazeno jednobitovým příznakem
Deflate - dict + huff perfection, nejvíce popular
- vysledny kompr vstup metodou lz77 se nasledne zpracuje huffmanem, ktery vytvori kod i pro samotne tokeny
- offset muze byt dlouhy (search buffer 1000 bytů) ale delky zpravidla mensi. proto máme 2 tabulky, jednu obsahující huff kod pro delky a literaly + jednu s offsety
- zkratka huffman, kterej vytvari kody i pro tokeny (pro offsety a delky)
LZ78, reprezentace slovníku
Lempel, Ziv, 1978 / LZ2
- oproti LZ77 nepoužívá pos. okno, tkz SB ani LAB
- výstupní tokeny jsou dvouprvkové -> pointer do slovniku a kod symbolu (neobs delku, ptz vypl ze slovniku)
- slovnik drive nalezenych retezcu - starts empty, pouze s null symbolem na nulté pozici a omezen dostupnou pameti
- pri cteni vstupu sym postupne pridavany do slovniku
- postup: cteni symbolu x - prochazeni slovniku a hledani zda sym v je: dict
- pokud NENÍ - new záznam v dict x na násl free pozici a token (0,x) na output (konkatenace null a x)
- pokud JE v dict obsažen x na pozici 35 - načte se další symb ze vstupu př xy a hledá se, zda je xy v dict. Pokud nenalezen, output (35,y) - konkatenace pozice 35 x a y
- proces se opakuje do precteni celeho vstupu
- Příklad: barbara_a_bar…
- adaptivni slovnik, vytvareni stejneho slovniku i pri dekompr
Reprezentace dict
- idealni struktura slovniku je n-arni strom neboli trie (retrieval), kde uzly serazeny lexikograficky
- vyhody nevyhody vetsich dict: vetsi stromy mohou ulozit vice retezcu ale tokeny potom obsahuji vetsi ukazatele a pomalejsi vyhl v dict
- strom zacina s korenem null, pri cteni vstupu jsou ukladany stale vetsi a vetsi retezce
- velikost stromu omezena bud fixni velikosti nebo dostupnou pameti (tak jak tak je omezena)
- dusledek omezene velikosti: ze stromu se v teto metode nemaze, coz zjednodusuje proces komprese, avsak je jen otazka casu kdy dojde misto pro nove uzly
- metoda lz78 nespecifikuje, co v tomto pripade delat, tak mame nekolik moznosti:
1. strom/dict zmrazit - promenit na staticky
2. vymazat cely a zacit znovu
3. smazat nejstarsi pridane a nepouzivane uzly - kompl
4. unix - komplex solution kombinace predchozich - freeze, sledovat kompresni pomer, restart
