26 - Klasifikace metod komprese dat (ztrátové, bezeztrátové, intuitivní, algoritmické, četnost výskytu, pravděpodobnost výskytu), princip kódování délek sledů, kódování "přesuň na začátek."
pondělí 21. května 2018
17:23
Klasifikace metod komprese dat
Ztrátová/bezztrátová komprese - ztratová dosahuje vyššího kompresního poměru, za cenu ztráty jisté informace. Po dekompresi již nezískáme původní vstupní datový tok. Hodí se zejména pro kompresi obrazků, zvuku a videa, kde malou ztrátu informace nemusí človek poznat. Naopak je neprosto nevhodná pro kompresi textu, změna jediného bitu by znamenala znehodnocení celého vstupního souboru.
Asymetrická/symetrická komprese - jedná se o případ, kdy kodér a dekodér využívají stejný algoritmus, ale v inverzním režimu. U asymetrické pracuje buď kodér nebo dekodér výrazně déle. To není na závadu. např. pri archivaci dat, ktera budou často čtena, může  komprese trvat déle. Většina moderních kompresních metod je asymetrická.
Neadaptivní/adaptivní kompresní metoda - je fixní, nemění svůj výpočtový postup. Je navržena pro určitý typ dat, např. fax. Naopak adaptivní metoda zkoumá vstupní data a na základě jejich analýzy přizpůsobuje své operace.
Základní principy komprese dat:
Intuitivní – např. redukce abecedy apod. 
Diferenční (nebo též relativní) – zaznamenává se pouze změna hodnoty aktuálního znaku oproti předcházejícímu symbolu (v posloupnosti symbolů) 
Kódování délek sledů stejných hodnot
Statistické – znaky se kódují podle pravděpodobnosti výskytu kódem s proměnnou délkou kódového slova 
Slovníkové – vytvářejí se slovníky omezené velikosti z předcházejících slov nebo slabik
Kontextové, nebo též predikční – z předchozích a sousedních hodnot lze často odhadnout skutečnou hodnotu, většinou s malou chybou, tato „chyba“ se kóduje 
Intuitivní kompres: Jedná se o první kompresní metody. 
Braillův kód: umožňuje slepým číst. Braillův kód je tvořen skupinami 3x2 bodů, vytlačených do tlustého papíru. Každý bod nese informaci jednoho bitu, což dává celkem 6 bitů na jeden obrazec, tedy 64 různých obrazců. 
Morseův kód
Odstranění mezer: Pokud text obsahuje mnoho mezer, které nejsou významové, mohou se odstranit a jejich pozice se mohou vyznačit bitovým řetězcem. Místo aby každá mezera zabrala bajt (ASCII), tak se 8 pozic textu zakóduje do jednoho bajtu (0 znamená že zde není mezera a 1 že zde mezera je). 
Kód ASCII je sedmibitový, takže anglické texty by se mohly do výstupního toku kódovat pouze sedmibitovými kombinacemi. Kompresní poměr je zde 7/8 = 0,875.
Pravděpodobnostní model: Tento přístup je významný u metod statistické komprese dat. Před vlastní kompresí se musí vytvořit model dat. Ten se získá přečtením celého vstupního toku a spočítáním frekvence výskytu jednotlivých symbolů. Komprese se pak provádí na základě dalšího čtení vstupního toku znak po znaku a informací z pravděpodobnostního modelu. Čtení celého vstupního toku dvakrát je zdlouhavé a proto praktické kompresní metody používají odhadů, nebo se přizpůsobují podle dat, která se mají komprimovat.
Entropie obecně je míra neuspořádanosti daného systému a v kódování označuje nejnižší počet bitů potřebných k reprezentaci daného symbolu či řetězce. Uvažujeme-li řetězec s i symboly, předtavuje Pi pravděpodobnost jeho výskytu. Potom se entropie textu vyjádří jako -Σ Pi log2 Pi  pro všechna i. Analogicky můžeme definovat entropii jednoho symbolu jako -Pi log2 Pi. Jednotky jsou bity.
RLE (Run length encododing) - kódování délek sledů
Základní myšlenka této metody je následující: pokud se datová položka d vyskytuje ve
vstupním toku za sebou n-krát, nahradí se n výskytu jedinou dvojicí nd. Těchto n postupných výskytu datové položky se nazývá délka sledu n a tento postup komprese dat se nazývá kódování délek sledu nebo RLE. Tento princip použijeme jednak pro kompresi textu a pak i pro kompresi obrazu.
Diferenční kódování: Jedná se o variantu RLE, někdy se nazývá diferencováni/diferenční(z matematiky). Tato metoda se používá v případech, kdy vstupní datový tok je tvořen čísly, které se navzájem příliš neliší anebo podobnými řetězci. Příkladem pro první případ může být telemetrie a pro druhý případ přenos faxových dat nebo komprese LZW. Příklad v telemetrii: měřící stanice měří teplotu a postupně odesílá čísla do centrály. Máme např. posloupnost teplot: 115, 116, 120, 114, 200, 202, 204. Tuto posloupnost lze převést na posloupnost 115,1,4,-6,200,2,2. To znamená, že se odešle první číslo a následující čísla jsou již jen diference vůči předchozímu číslu, které se koduje na menším počtu bitů. Pokud je změřená hodnota s velkým rozdílem, je odeslána jako skutečná hodnota.
Přesun na začátek (Move to front - MTF)
Základní myšlenkou tohoto postupu je udržovat abecedu A symbolů jako seznam,
ve kterém jsou  často se vyskytující symboly umístěny na začátku. Např. symbol „s“ je zakódován jako počet symbolů, které jej v seznamu předcházejí. Takže když A = („t“, „h“, „e“, „s“) a máli se jako následující symbol vstupního toku kódovat „e“, bude zakódován jako 2, protože jej předcházejí dva symboly. 
Existuje několik možných variant této metody; ta základní pridává další krok. Když se použije symbol „s“, tak se přesune na začátek seznamu. Tedy po zakódování „e“ se abeceda modifikuje na A= („e“, „t“, „h“, „s“, ...). Tento krok přesunu na začátek respektuje naději, že když se ze vstupního toku přečetlo „e“, bude se zase číst mnohokrát a stane se alespoň na chvíli společným symbolem. 
Metoda Přesun na začátek je lokálně adaptivní, protože se adaptuje podle frekvence symbolu v lokálních oblastech vstupního toku. Tato metoda dává dobré výsledky, když vstupní tok splňuje tuto naději, tj. když obsahuje koncentrace identických symbolů (když se lokální frekvence symbolu oblast od oblasti vstupního toku výrazně mění). Nazýváme to „koncentrační vlastnost").
Notes*
Otazka (predmet) (okruh): 26. Klasifikace metod komprese dat 
Kdo me primarne zkousel: Drábek Vladimír, doc. Ing., CSc.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Rekl jsem, co to je komprese, neco o entropii. Pak rozdeleni na ztratove/bezztratove, symetricke/asymetricke. Pak se Drabek zeptal na kodovani "presun na zacatek", popsal jsem, na jakem predpokladu je zalozene, s cim ho kombinujeme a jak funguje. Zazvonil budik a stacilo to. Drabek byl mily. Jen mi prvni polovinu (nez se zeptal) prislo, ze mne neposloucha vubec nikdo, ani on - dokonce jsem premyslel, jestli vubec mam mluvit, nebo se na neco ceka 
->A
From <[link]> 
Otazka (predmet) (okruh): 26. Klasifikace metod komprese dat (ztrátové, bezeztrátové, intuitivní, algoritmické, četnost výskytu, pravděpodobnost výskytu), princip kódování délek sledů, kódování MTF.
Kdo me primarne zkousel: Drábek
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Na papírku bylo jen "Klasifikace metod komprese dat...", Drábek říkal, ať začnu zase sám, úplně mi v tu chvíli ta jednotlivá rozdělení vypadla. Nakonec jsem si ale začal vzpomínat. Drábek pak po mně chtěl vysvětlit blíže ztrátové/bezztrátové komprese. Když jsem odpověděl, tak chtěl vědět, jaký je rozdíl v kompresním poměru mezi nimi. Tak jsem řekl, že u ztrátových můžeme vždy docílit vyšší komprese. To mi odkývl, ale zeptal se, jestli bych mu mohl říct tím pádem přesný poměr mezi těmi ztrátovými a bezztrátovými. To už jsem nevěděl. Řekl, že to je 100:1. (Proč tomu tak je, mi došlo až ve chvíli, kdy jsem opouštěl školu). Pak chtěl ještě vědět MTF. Nakonec Hanáček ještě dodal dodatečnou otázku, nepamatuji si přesně jakou, ale bylo to něco s kompresemi šifrovaného textu. Cokoli jsem řekl, bylo špatně 
 Naštěstí výslednou známku to neovlivnilo.
From <[link]> 