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

Řádek 18: Řádek 18:
 
*Neprefixový kód = na cestě do nějakého ''listu'' leží nějaké písmeno vstupní abecedy[http://www.uai.fme.vutbr.cz/~matousek/TIK/TIKv19.pdf]
 
*Neprefixový kód = na cestě do nějakého ''listu'' leží nějaké písmeno vstupní abecedy[http://www.uai.fme.vutbr.cz/~matousek/TIK/TIKv19.pdf]
  
 
+
===Příklad===
 +
* Vstupní soubor: ABRAKADABRA
 +
* Jednotlivé znaky: A    B    D    K    R
 +
* Počty výskytů:  (5) (2) (1) (1) (2)
 +
* Vytvořený strom:
 +
[[File:strom.PNG|200px]][https://atrey.karlin.mff.cuni.cz/~tnovak/compress/huffman/shannon.html]
  
  

Verze z 19. 12. 2018, 09:33

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]

Příklad

  • Vstupní soubor: ABRAKADABRA
  • Jednotlivé znaky: A B D K R
  • Počty výskytů: (5) (2) (1) (1) (2)
  • Vytvořený strom:

Strom.PNG[7]