Shannon-Fanovo kódování
Verze z 19. 12. 2018, 10:09, kterou vytvořil Marie.Cerna (diskuse | příspěvky)
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]
Pseudokód
- Pro danou zprávu vytvořit seznam symbolů a zjistit počet jejich výskytů (nebo pravděpodobnost)
- Seznam symbolů seřadit do neklesající posloupnosti podle této hodnoty
- Kódy všech symbolů jsou zpočátku prázdné
- Rozdělit seznam na dvě poloviny tak, aby součet sledovaných hodnot byl v obou částech zhruba stejný
- Ke kódům symbolů levé polovině připojit 0, ke kódům symbolů v pravé polovině připojit 1
- Rekurzivně opakovat od kroku 4 na levou i pravou polovinu seznamu [8]
Příklad
1)
Symbol | Počet výskytů |
---|---|
F | 5 |
D | 4 |
C | 4 |
A | 3 |
B | 3 |
E | 2 |
2)
- Vstupní soubor: ABRAKADABRA
- Jednotlivé znaky: A B D K R
- Počty výskytů: (5) (2) (1) (1) (2)
- Vytvořený strom: