Shannon-Fanovo kódování: Porovnání verzí

Řádek 18: Řádek 18:
 
! Pravdepodobnosť výskytu !! 0,22 || 0,19 || 0,18 || 0,15 || 0,10 || 0,09 || 0,04 || 0,03
 
! Pravdepodobnosť výskytu !! 0,22 || 0,19 || 0,18 || 0,15 || 0,10 || 0,09 || 0,04 || 0,03
 
|}
 
|}
 +
[[File:Fanov_strom.jpg|400px]]<ref name=TUKE>KRAVECOVÁ, Daniela. <i>Základy kódovania</i>. Košice: Technická univerzita v Košiciach, 2012. ISBN 978-80-553-1178-4. Dostupné také z: http://web.tuke.sk/fei-km/sites/default/files/prilohy/15/Zaklady_kodovania_ucebnica.pdf</ref>
  
−
 
+
Jednotlivé kódové slová sa čítajú zhora nadol. V nasledujúcej tabuľke sú zobrazené výsledné kódové slová:
 +
{| class="wikitable"
 +
|-
 +
! a1 !! a2 !! a3 !! a4 !! a5 !! a6 !! a7 !! a8
 +
|-
 +
| 00 || 01 || 100 || 101 || 110 || 1110 || 11110 || 11111
 +
|}
  
 
=Využitie=
 
=Využitie=
−
 
+
V praxi sa využíva omnoho menej než Huffmanove kódovanie, pretože nie vždy produkuje optimálny kód, ale aj napriek tomu sa využíva pri kompresii dát vo formáte ZIP.
 
<references/>
 
<references/>

Verze z 16. 9. 2015, 02:24

Základný popis

Je pomenované po Claude Elwood Shannonovi a Robertovi Fanovi, ktorí zostrojili kód s vlastnosťou prefixu na základe pravdepodobností výskytu znakov.

História

Konštrukcia kódu

Postup konštrukcie je podobný ako pri Huffmanovom kódovaní. Rozdiel spočíva len smere konštrukcie binárneho stromu.

  1. Jednotlivé znaky si zoradíme zostupne podľa pravdepodobnosti výskytu
  2. Pri zachovaní poradia znakov, rozdelíme množinu na dve časti tak, aby bol výsledný rozdiel súčtov pravdepodobnosti čo najmenší
  3. Jednotlivým častiam pridelíme kódový znak 0 alebo 1
  4. Kroky 2 a 3 opakujeme dovtedy, kým sa nedopracujeme k jednoprvkovým množinám
  5. Jednotlivé kódové slová získame čítaním kódových znakov v poradí v akom im boli prideľované [1]

Príklad

Konštrukciu stromu podľa vyššie uvedeného postupu si ukážeme na jednoduchom príklade:

Zdrojová abeceda a1 a2 a3 a4 a5 a6 a7 a8
Pravdepodobnosť výskytu 0,22 0,19 0,18 0,15 0,10 0,09 0,04 0,03

Fanov strom.jpg[2]

Jednotlivé kódové slová sa čítajú zhora nadol. V nasledujúcej tabuľke sú zobrazené výsledné kódové slová:

a1 a2 a3 a4 a5 a6 a7 a8
00 01 100 101 110 1110 11110 11111

Využitie

V praxi sa využíva omnoho menej než Huffmanove kódovanie, pretože nie vždy produkuje optimálny kód, ale aj napriek tomu sa využíva pri kompresii dát vo formáte ZIP.

  1. ↑ IVÁNEK, Jiří. Vybrané kapitoly z kódování informací. Praha, 2007. Dostupné také z: texty.jinonice.cuni.cz/studijni-texty/ivanek-jiri/ivanek_01.pdf/attachment_download/file
  2. ↑ KRAVECOVÁ, Daniela. Základy kódovania. Košice: Technická univerzita v Košiciach, 2012. ISBN 978-80-553-1178-4. Dostupné také z: http://web.tuke.sk/fei-km/sites/default/files/prilohy/15/Zaklady_kodovania_ucebnica.pdf
Citováno z „https://wikisofia.cz/w/index.php?title=Shannon-Fanovo_kódování&oldid=22811“