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

Řádek 1: Řádek 1:
−
Podľa teórie informácie, entropické kódovanie je bezstratová kompresia dát, ktorá je nezávislá na vlastnostiach média.<ref><i>Entropy encoding</i>. San Francisco: Wikimedia Foundation. Dostupné také z: https://en.wikipedia.org/wiki/Entropy_encoding</ref> Pri efektívnom kódovaní ide o to, nájsť také, pri ktorom bude priemerná prenosová rýchlosť správ cez informačný kanál čo najväčšia, t.j. priemerný počet signálov použitých na zakódovanie správy bude čo najmenší. Inými slovami, pri entropickom kódovaní sa nahrádzajú symboly rovnakej dĺžky vo vstupnej správe kódovými slovami rôznej dĺžky a to tak, že najčastejšie sa vyskytujúce symboly majú priradené najkratšie kódové slová.<ref>UZEL,Petr. <i>Entropické kodéry</i>. 2009. Dostupné také z: https://is.cuni.cz/webapps/zzp/download/120008368/?lang=cs</ref> Pre entropické kódovanie platí vlastnosť prefixu – žiadne kódové slovo nie je začiatkom iného kódového slova. <ref>IVÁNEK, Jiří. <i>Vybrané kapitoly z kódování informací</i>. Praha, 2007. Dostupné také z: texty.jinonice.cuni.cz/studijni-texty/ivanek-jiri/ivanek_01.pdf/attachment_download/file</ref>
+
'''Entropické kódování''' je velmi často používaná metoda při bezstrátové kompresie. 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>
−
== Príklady entropického kódovania ==
+
== Příklady entropického kódování ==
−
Najznámejšie algoritmy entropického kódovania vynašli:
 
−
* [[Claude Shannon|C. Shannon]]
 
−
* [[D. Huffman]]
 
−
* [[R. Fano]]
 
  
−
===[[Huffmanove kódovanie]]===
+
===[[Shannon-Fanove kódovanie|Shannon-Fanovo kódování]]===
−
Je založené na predpoklade znalosti pravdepodobnosi výskytu kódovaných znakov. Pri tvorbe Huffmanovho kódu sa generujú binárne stromy, ktoré umožňujú vytvorenie kódových slov, pomocou cesty z počiatočného do koncového uzlu.
+
'''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í.<ref><i>Shannonovo–Fanovo kódování</i>. 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</ref>
−
===[[Shannon-Fanove kódovanie]]===
+
<br>Používá se v: ZIP/Implode<ref name =":1">BAŘINA, David. <i>Kompresní techniky</i> [online prezentace]. 15. Února 2013 [cit. 2018-01-22]. Dostupné z: http://www.fit.vutbr.cz/~ibarina/pub/compression-cs.pdf </ref>
−
Podobne ako pri Huffmanovom kódovaní, aj tu je výsledkom kódovania binárny strom, ktorý sa ale na rozdiel od neho konšturuje od koreňa. Pri kódovaní sa hodnotí pravdepodobnosť výskytu slov a priraďuje sa im kódové slovo zodpovedajúcej dľžky. Tento typ kódovania nám vydáva optimálny kód často,nie však vždy.  
+
===[[Huffmanove kódovanie|Huffmanovo kódování]]===
−
===[[Aritmetické kdovanie]]===
+
'''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. <ref>SHARMA, Mamta. <i>Compression using Huffman coding</i>. IJCSNS International Journal of Computer Science and Network Security, 2010, 10.5: 133-141. Dostupné také z: https://pdfs.semanticscholar.org/89c2/03919ce446762d9b768ac0974f54021f338e.pdf </ref>
−
Pri aritmetickom kódovaní sú správy reprezentované intervalom reálnych čísel medzi 0 a 1. So zväčšovaním správy sa zmenšuje interval potrebný na reprezentáciu a počet bitov potrebných na špecifikáciu intervalu narastá. Po sebe idúce symboly správy redukujú veľkosť intervalu podľa pravdepodobností vygenerovaných modelom. Častejšie symboly redukujú rozsah viac, ako menej časté symboly a preto pridávajú menej bitov do správy.<ref>WITTEN Ian, Neal Radford. <i>Arithmetic coding for data compression</i>. 1987. Dostupné také z: http://web.stanford.edu/class/ee398a/handouts/papers/WittenACM87ArithmCoding.pdf</ref>
+
<br>Používá se v: bzip2, Deflate, JPEG, MP3<ref name=":1">BAŘINA, David. <i>Kompresní techniky</i> [online prezentace]. 15. Února 2013 [cit. 2018-01-22]. Dostupné z: http://www.fit.vutbr.cz/~ibarina/pub/compression-cs.pdf </ref>  
  
 +
===[[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.<ref>WILLEN, IAN H.; NEAL, RADFORD M.; CLEARY, JOHN G. ARITHMETIC CODING FOR DATA COIUPRESSION. <i>Communications of the ACM</i>, 1987, 30.6. Dostupné také z: http://staff.ustc.edu.cn/~jingxi/p520-witten.pdf </ref>
 +
<br>Používá se v: kontextové kodéry, JPEG, Dirac<ref name=":1">BAŘINA, David. <i>Kompresní techniky</i> [online prezentace]. 15. Února 2013 [cit. 2018-01-22]. Dostupné z: http://www.fit.vutbr.cz/~ibarina/pub/compression-cs.pdf </ref>
 +
 +
===[[Golombovo-Riceovo kódování]]===
 +
'''Golombovo ková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.
 +
<br>'''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ší.<ref><i>Golombovo kódování</i>. 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 </ref>
 +
<br>Používá se v:JPEG-LS, FLAC, MPEG-4 ALS<ref name=":1">BAŘINA, David. <i>Kompresní techniky</i> [online prezentace]. 15. Února 2013 [cit. 2018-01-22]. Dostupné z: http://www.fit.vutbr.cz/~ibarina/pub/compression-cs.pdf </ref>
 +
 +
== Odkazy ==
 +
=== Reference ===
 
<references/>
 
<references/>
 +
 +
=== Související články ===
 +
* [[Kódování]]
 +
* [[Huffmanove kódovanie]]
 +
* [[Shannon-Fanove kódovanie]]
 +
* [[Komprese obrazových informací]]
 +
 +
=== Klíčová slova ===
 +
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 k opravě UISK]]

Verze z 22. 1. 2018, 17:35

Entropické kódování je velmi často používaná metoda při bezstrátové kompresie. 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 ková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

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

Související články

Klíčová slova

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

Citováno z „https://wikisofia.cz/w/index.php?title=Optimální_(entropické)_kódování_informačního_zdroje&oldid=51888“