|
|
| Řá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]] |
