Shannon-Fanovo kódování

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]
• Asymetrická kompresní metoda
• Dvouprůchodová kompresní metoda
• Semi-adaptivní kompresní metoda
• Dosahuje horších výsledků ve srovnání s Huffmanovým kódováním[4]

                                                                            C.E.Shannon  [5]                  

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.[6]

• 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[7]

Příklad

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

[8]