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

m
Řádek 1: Řádek 1:
==Základný popis==
+
==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.
+
[<ref>Shannon-Fanovo kódování je technika pro sestavení '''prefixového kódu''' založená na seznamu symbolů a počtech jejich výskytů.</ref>]
  
=Konštrukcia kódu=
 
Postup konštrukcie je podobný ako pri Huffmanovom kódovaní. Rozdiel spočíva len smere konštrukcie binárneho stromu.
 
# Jednotlivé znaky si zoradíme zostupne podľa pravdepodobnosti výskytu
 
# Pri zachovaní poradia znakov, rozdelíme množinu na dve časti tak, aby bol výsledný rozdiel súčtov pravdepodobnosti čo najmenší
 
# Jednotlivým častiam pridelíme kódový znak 0 alebo 1
 
# Kroky 2 a 3 opakujeme dovtedy, kým sa nedopracujeme k jednoprvkovým množinám
 
# Jednotlivé kódové slová získame čítaním kódových znakov v poradí v akom im boli prideľované <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>
 
=Príklad=
 
Konštrukciu stromu podľa vyššie uvedeného postupu si ukážeme na jednoduchom príklade:
 
{| class="wikitable"
 
|-
 
! 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
 
|}
 
[[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=
 
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.
 
==Odkazy==
 
===Reference===
 
<references/>
 
==Súvisiace články==
 
[[Optimální (entropické) kódování informačního zdroje]]
 
[[Huffmanove kódovanie]]
 
  
 
[[Kategorie:Informační studia a knihovnictví]][[Kategorie:Hesla ke zpracování UISK]]
 
[[Kategorie:Informační studia a knihovnictví]][[Kategorie:Hesla ke zpracování UISK]]

Verze z 18. 12. 2018, 23:01

Základní popis

[[1]]

  1. Shannon-Fanovo kódování je technika pro sestavení prefixového kódu založená na seznamu symbolů a počtech jejich výskytů.