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

Řádek 8: Řádek 8:
 
==Konstrukce binárního kódu==
 
==Konstrukce binárního kódu==
 
===Princip===
 
===Princip===
Princip je založen na rekurzivní proceduře, která přiřazuje, pro každou zdrojovou informaci, k jejímu kódovému slovu v jednom kroku binární číslici.  
+
Princip je založen na množině znaků rekursivně dělících se 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.[https://wikisofia.cz/wiki/Optimální_(entropické)_kódování_informačního_zdroje]
  
 
* Postup není optimální
 
* Postup není optimální
 
* Důležitá vlastnost: opětovné prefixovost
 
* Důležitá vlastnost: opětovné prefixovost
 +
  
 
Prefixovost Shannon-Fanova kódu můžeme zachytit binárním prefixovým stromem. Písmena vstupní abecedy jsou v ''listech'' a jejich kódy tvoří od cesta od ''kořene'' do daného vrcholu.
 
Prefixovost Shannon-Fanova kódu můžeme zachytit binárním prefixovým stromem. Písmena vstupní abecedy jsou v ''listech'' a jejich kódy tvoří od cesta od ''kořene'' do daného vrcholu.

Verze z 19. 12. 2018, 10:14

Základní popis

Shannon-Fanovo kódování je technika pro sestavení prefixového kódu založená na seznamu symbolů a počtech jejich výskytů. v roce 1949 metodu nezávisle na sobě publikovali Claude Elwood Shannon (otec teorie informace)[1] s Warrenem Weaverem a Robertem Mario Fano.[2]

  • Řešení nemusí být vždy optimální (nejkratší)
  • Používá se v kompresních datech [3]
                                                                                C.E.Shannon C.E.Shannon [4]                  

Konstrukce binárního kódu

Princip

Princip je založen na množině znaků rekursivně dělících se 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.[5]

  • Postup není optimální
  • Důležitá vlastnost: opětovné prefixovost


Prefixovost Shannon-Fanova kódu můžeme zachytit binárním prefixovým stromem. Písmena vstupní abecedy jsou v listech a jejich kódy tvoří od cesta od kořene do daného vrcholu.

  • Neprefixový kód = na cestě do nějakého listu leží nějaké písmeno vstupní abecedy[6]