Optimální (entropické) kódování informačního zdroje: Porovnání verzí

Aktuální verze z 27. 10. 2018, 15:40

Optimální entropické kódování je velmi často používaná metoda při bezztrátové kompresi. Entropický kodér komprimuje data takovým způsobem, že nahradí vstupní symboly odpovídající sekvencí s proměnnou délkou. Délka sekvence závisí na pravděpodobnosti výskytu původních symbolů v datech tak, že nejběžnější symboly budou reprezentovány nejkratšími sekvencemi. ^[1]

Příklady entropického kódování

Shannon-Fanovo kódování

Shannonovo-Fanovo kódování je statistická metoda bezeztrátové komprese navržená roku 1949 Shannonem, Weawerem a Fanem. Od Huffmanova kódování se liší pouze konstrukcí binárního stromu: Množina znaků je rekursivně dělena vždy na dvě podmnožiny, aby součet výskytů znaků v obou podmnožinách byl přibližně stejný. Jedné podmnožině je pak v kódu přiřazena binární 1 a druhé 0. Tento kód je tedy konstruován od kořene k listům a na rozdíl od Huffmanova kódování, jehož kód je tvořen od listů ke kořenu, nemusí být optimální.^[2]
Používá se v: ZIP/Implode^[3]

Huffmanovo kódování

Huffmanovo kódování je založené na frekvenci výskytu datového objektu (např. pixel v obrázcích). Hlavní myšlenkou je užít menší počet bitů k zakódování často se vyskytujících znaků. Kódy jsou uloženy v kódové knize, která může být vytvořená pro každý obraz zvlášť, nebo pro celou skupinu obrazů.V obou případech je však k umožnění dekódování nutný přenos kódu i s kódovou knihou. ^[4]
Používá se v: bzip2, Deflate, JPEG, MP3^[3]

Aritmetické kódování

Při aritmetickém kódování je zpráva reprezentována intervalem reálných čísel mezi 1 a 0.Čím se zpráva stává delší, tím se interval potřebný k jejímu zastoupení zmenšuje a počet bitů potřebných k jeho určení se zvětšuje. Po sobě jdoucí symboly zprávy redukují velikost intervalu podle svých pravděpodobností vygenerovaných modelem. Pravděpodobnější symboly redukují rozsah více, než méně pravděpodobné symboly, tudíž přidávají méně bitů do zprávy.^[5]
Používá se v: kontextové kodéry, JPEG, Dirac^[3]

Golombovo-Riceovo kódování

Golombovo kódování je bezeztrátová kompresní metoda patřící do skupiny kódu vynalezených Solomonem W. Golombem v 60. letech. Pro takové abecedy, které mají geometrické rozdělení pravděpodobnosti, bude Golombovo kódování optimální a bude tvořit prefixový kód. Z této vlastnosti plyne, že toto kódování bude velmi vhodné pro takové případy, kdy pravděpodobnost malých hodnot na vstupu bude mnohonásobně vyšší než pravděpodobnost velkých.
Ricovo kódování (podle Roberta F. Ricea) označuje podmnožinu Golombových kódů, které vytvářejí jednodušší (ale teoreticky suboptimální) prefixový kód. Rice použil tuto množinu kódů v rámci adaptivního kódování; "Riceovo kódování" tak může odkazovat buď na toto adaptivní kódování, nebo na speciální podmnožinu Golombových kódů. Zatímco v obecném Golombově kódování může být volitelný parametr libovolné kladné celé číslo, Riceovo kódování volí parametr tak, aby byl mocninou dvou. Tato vlastnost činí Riceovo kódování vhodnějším pro počítačové využití, protože násobení a dělení dvěma je v binární aritmetice mnohem efektivnější.^[6]
Používá se v:JPEG-LS, FLAC, MPEG-4 ALS^[3]

Odkazy

Reference

↑ KOMJÁTHY, Gergely. Bezeztrátová komprese obrazu. Brno, 2011. Bakalářská práce. Vysoké učení technické v Brně. Vedoucí práce David Bařina. Dostupné také z: https://www.vutbr.cz/www_base/zav_prace_soubor_verejne.php?file_id=117689
↑ Shannonovo–Fanovo kódování. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2018-01-22]. Dostupné z: https://cs.wikipedia.org/wiki/Shannonovo%E2%80%93Fanovo_k%C3%B3dov%C3%A1n%C3%AD
↑ ^3,0 ^3,1 ^3,2 ^3,3 BAŘINA, David. Kompresní techniky [online prezentace]. 15. Února 2013 [cit. 2018-01-22]. Dostupné z: http://www.fit.vutbr.cz/~ibarina/pub/compression-cs.pdf
↑ SHARMA, Mamta. Compression using Huffman coding. IJCSNS International Journal of Computer Science and Network Security, 2010, 10.5: 133-141. Dostupné také z: https://pdfs.semanticscholar.org/89c2/03919ce446762d9b768ac0974f54021f338e.pdf
↑ WILLEN, IAN H.; NEAL, RADFORD M.; CLEARY, JOHN G. ARITHMETIC CODING FOR DATA COIUPRESSION. Communications of the ACM, 1987, 30.6. Dostupné také z: http://staff.ustc.edu.cn/~jingxi/p520-witten.pdf
↑ Golombovo kódování. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2018-01-22]. Dostupné z:https://cs.wikipedia.org/wiki/Golombovo_k%C3%B3dov%C3%A1n%C3%AD

Související články

Klíčová slova

kódování, entropické kódování, komprese, komprese dat

[1] KOMJÁTHY, Gergely. Bezeztrátová komprese obrazu. Brno, 2011. Bakalářská práce. Vysoké učení technické v Brně. Vedoucí práce David Bařina. Dostupné také z: https://www.vutbr.cz/www_base/zav_prace_soubor_verejne.php?file_id=117689

[2] Shannonovo–Fanovo kódování. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2018-01-22]. Dostupné z: https://cs.wikipedia.org/wiki/Shannonovo%E2%80%93Fanovo_k%C3%B3dov%C3%A1n%C3%AD

[:1-3] 3,0 ^3,1 ^3,2 ^3,3 BAŘINA, David. Kompresní techniky [online prezentace]. 15. Února 2013 [cit. 2018-01-22]. Dostupné z: http://www.fit.vutbr.cz/~ibarina/pub/compression-cs.pdf

[4] SHARMA, Mamta. Compression using Huffman coding. IJCSNS International Journal of Computer Science and Network Security, 2010, 10.5: 133-141. Dostupné také z: https://pdfs.semanticscholar.org/89c2/03919ce446762d9b768ac0974f54021f338e.pdf

[5] WILLEN, IAN H.; NEAL, RADFORD M.; CLEARY, JOHN G. ARITHMETIC CODING FOR DATA COIUPRESSION. Communications of the ACM, 1987, 30.6. Dostupné také z: http://staff.ustc.edu.cn/~jingxi/p520-witten.pdf

[6] Golombovo kódování. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2018-01-22]. Dostupné z:https://cs.wikipedia.org/wiki/Golombovo_k%C3%B3dov%C3%A1n%C3%AD

[1]

[2]

[3]

[4]

[5]

[6]

@@ Řádek 1: / Řádek 1: @@
-Optimální entropické kódování je velmi často používaná metoda při bezstrátové kompresi. Entropický kodér komprimuje data takovým způsobem, že nahradí vstupní symboly odpovídající sekvencí s proměnnou délkou. Délka sekvence závisí na pravděpodobnosti výskytu původních symbolů v datech tak, že nejběžnější symboly budou reprezentovány nejkratšími sekvencemi. <ref>KOMJÁTHY, Gergely. <i>Bezeztrátová komprese obrazu</i>. Brno, 2011. Bakalářská práce. Vysoké učení technické v Brně. Vedoucí práce David Bařina. Dostupné také z: https://www.vutbr.cz/www_base/zav_prace_soubor_verejne.php?file_id=117689</ref>
+'''Optimální entropické kódování''' je velmi často používaná metoda při bezztrátové kompresi. Entropický kodér komprimuje data takovým způsobem, že nahradí vstupní symboly odpovídající sekvencí s proměnnou délkou. Délka sekvence závisí na pravděpodobnosti výskytu původních symbolů v datech tak, že nejběžnější symboly budou reprezentovány nejkratšími sekvencemi. <ref>KOMJÁTHY, Gergely. <i>Bezeztrátová komprese obrazu</i>. Brno, 2011. Bakalářská práce. Vysoké učení technické v Brně. Vedoucí práce David Bařina. Dostupné také z: https://www.vutbr.cz/www_base/zav_prace_soubor_verejne.php?file_id=117689</ref>
 == Příklady entropického kódování ==
@@ Řádek 32: / Řádek 32: @@
 kódování, entropické kódování, komprese, komprese dat
-[[Kategorie:Informační studia a knihovnictví]][[Kategorie:Informační technologie, knihovnické technologie]][[Kategorie:Hesla k opravě UISK]]
+[[Kategorie:Informační studia a knihovnictví]][[Kategorie:Informační technologie, knihovnické technologie]][[Kategorie:Hesla ke zpracování UISK]]