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ů (💡 jako by slovníky):

*statické - model je statický pro všechny dokumenty (uložen jednou) *semiadaptivní (polostatické) - ∀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) je <u>prosté</u> kódové zobrazení znaků z abecedy A do prostoru slov v abecedě C

kódování

{{Zkazky|

  • komprese (2015, konzultace Kopecký) - pod kódováním bych já asi viděl obecnou problematiku kódování (tj. věci jako reprezentace nějaké posloupnosti znaků slovy nějaké abecedy, prefixovost, jednoznačnou dekódovatelnost, vztah mezi prefixovostí a jednoznačnou dekódovatelností, entropii, a podobně. To další jsou pak speciální případy s nějakými konkrétními vlastnostmi. Když budete umět Fibbonaciho/Eliasovy kódy jako speciální případy pro nekonečné množiny s nerovnoměrnou pravděpodobností výskytu znaků, určitě to nebude na škodu.

  • 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.

}} 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ý ⇒ jednoznačně dekódovatelný (opačně neplatí)

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 = tím méně informace nese (tím menší počet bitů je potřeba na její reprezentaci)

  • 💡 použítí viz: IDF/ITF

  • prům. entropie 1 znaku: AE(A) = -Σ ("pst výskytu znaku ai v textu") log( "pst výskytu znaku aᵢ v textu" )

    • očekávaná délka 1 znaku přes ∀znaky a jejich psti

  • entropie zprávy: E(A) = E(a₁...aₖ) = -Σ log( "pst výskytu znaku aᵢ v textu" )

    • 💡 tj. součet entropií znaků ve zprávě

    • platí že délka zakódované zprávy je |f(A)| > E(A)

    • redundance: R = |f(A)| - E(A)

{{collapse|1=speciální případy pro nekonečné množiny s nerovnoměrnou pravděpodobností výskytu znaků|2= 

Fibonacciho kody
  • Zalozeno na fibonacciho cislech radu >=2 (např. při řádu 4, se Fib. číslo Fₙ = Fₙ₋₁ + Fₙ₋₂ + Fₙ₋₃ + Fₙ₋₄). Cislo se rozdeli hladovou metodou na scitance v podobe fibonacciho cisel. Ty se seradi od nejmensiho po nejvetsi, zapisi formou '1' je, '0' neni scitanec a zakonci se jednickou navic.

  • pr. (fib cisla 1,2,3,5,8,13,21)

  • 1 -> 11, 2 -> 011, 3 ->0011, 4 -> 1011, 12-> 101011, 32 ->00101011

  • prosty binarni zapis by byl sice kratsi, ale neodlisitelny. Tady mi dve jednicky delaji jasny konec znaku. (pokud se vyskytují dvě jedničky za sebou někde jinde, je možné je nahradit vyšším Fibonacciho číslem, pokud postupuju při určování jedniček od nejvyššího čísla, tak se mi to nestane)

Eliášovy kódy
  • řada kódování, které mají různé vlstanosti

  • alfa kód (unární) – n-1 nul a na konci jednička, dekódovatelné, ale velmi dlouhé kódy

  • beta kód (binární) – klasické binární kódování, krátké kódy, ale nedekódovatelné

  • modifikovaný beta kód – stejně jako beta kód, ale bez úvodní jedničky

  • theta kód – speciální znak pro rozlišení konce kódu

  • gama kód – modifikovaný beta kód je obalený alfa kódem délky tohoto kódu – např. 37, v binárním kódu 100101, v modifikovaném beta kódu <font color="blue">00101</font>, v gama kódu <font color="teal">0</font><font color="blue">0</font><font color="teal">0</font><font color="blue">0</font><font color="teal">0</font><font color="blue">1</font><font color="teal">0</font><font color="blue">0</font><font color="teal">0</font><font color="blue">1</font><font color="teal">1</font>

    • jednička na liché pozici určuje konec znaku v textu (krátké kódy + dekódovatelný)

  • modifikovaný gama kód – na začátku má alfa kód délky modifikovaného beta kódu a za ním modifikovaný betakód <font color="teal">000001</font><font color="blue">00101</font>

    • není regulární (asi, že je potřeba dekódovat zprávu vždy odzačátku)

  • delta kód – obdoba modifikovaného gama kódu, ale místo alfa kódu délky využívá gama kódu délky <font color="teal">01001</font><font color="blue">00101</font>, kde <font color="teal">01001</font> je gama kód pro 6 (délka beta(37))

  • omega kód – pro velmi velká čísla – posloupnost beta kódů zakončená nulou B₀,B₁,...,<font color="blue">Bₖ</font>,<font color="red">0</font>

    • Bₖ je binární zápis slova, Bᵢ₋₁ je binárním vyjádřením délky slova Bᵢ znižené o 1, velikost B₀ je 2

    • př: 37: <font color="gold">10</font><font color="teal">101</font><font color="blue">100101</font><font color="red">0</font>

    • <font color="gold">00</font><font color="blue">1</font><font color="red">0</font> (1), <font color="gold">01</font><font color="blue">10</font><font color="red">0</font> (2), <font color="gold">01</font><font color="blue">11</font><font color="red">0</font> (3) nula na konci kódu je příznak toho, že při dekódování, pokud načtu první znak nulu, znamená to, že poslední přečtená část byla <font color="blue">Bₖ</font> a ne nějaké <font color="teal">Bᵢ</font>, i<k)

  • kódování čísel se používá například při indexaci dokumentů, kdy mám invertovaný soubor, kde je index termů a každý term má seznam ID dokumentů, ve kterých se vyskytuje (pro urychlení vyhodnocování dotazů je tento seznam setřízen – tyhle čísla se pak kódují nějakým prefixovým kódem. Optimalizace, využívá toho, že menší čísla mají kratší kódy – místo jednotlivých ID se kódují pouze přírustky ID (tzn. mám-li seznam 2,8,13,15 – tak se kódují čísla 2, 6, 5, 2)

Slajdy k 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 }}

[[Image:Stathuff.png|thumb|205px|StatickyHuffman(EMA MELE MASO)

'''Staticke Huffmanovo''' kodovaní

'''Dynamické''' (Adaptivní) '''Huffmanovo''' kódování

FGK (Faller, Galagher, Knuth)
Dynamické kodovanidekódování

Aritmetické kódování

Slovníkové metody

LZ algoritmy

LZW - ''Posíláme jen odkaz do slovníku (na začátku je v něm abeceda)''

LZ77 - ''Okénka (posíláme 3 údaje)''

Komprese bitových map

IdentifierHasInternetBitmaps
Y !! N
1 Yes 1 0
2 No 0 1
3 No 0 1
4 Unspecified 0 0
5 Yes 1 0

Řídké matice

Burrowsova-Wheelerova transformace
Vstup Všechny

Burrows-Wheelerova transformace (BWT) - ''Matice, permutace''

BSTW