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í

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)

Huffmanovo kódování (statické, dynamické) (🎓🎓🎓)

Huffmanovo k. se pouziva v poslední fázi u
JPEG MP3,...

Zážitky ze zkoušek
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í

statické kodovani
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.

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

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: počet výměn podstromů je nejvýše $ 1 $, přidá se escape sekvenci pro první výskyt nového znaku minimalizuje nejen $ \sum^n_{i=1} d[i] . p[i] $ ale i $ \sum^n _{i=1} d[i] $ a $ max_i d[i] $ $ AL_{HD} ≤ AL_{HS} + 1 $ (nejlepší hodnota mezi dynamickými Huffmanovými metodami)

další zdroje
Slajdy k OZD II (od slajdu 40) (statické, adaptivní kódování) Dobře popsáno také na stránkách k DIS 530 http://www.stringology.org/DataCompression/fgk/index_en.html http://www.stringology.org/DataCompression/ahv/index_en.html

aritmetické kódování,

viz wen:Arithmetic coding

Slajdy k OZD II (od slajdu 47)

Dokumenty k DIS (myslím, že v posledním kroku příkladu je chyba)

LZ algoritmy,

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,

OZD II

Burrows-Wheelerova transformace.

http://cs.wikipedia.org/wiki/Burrowsova-Wheelerova_transformace

Reprezentace celých čísel (zrušeno 2010)

Zážitky ze zkoušek

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 OZD II (od slajdu 21) (Fibonacciho, Eliasovy kódy, fázování)