Shannon-Fanovo kódování

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 ^[1]

C.E.Shannon

Obsah

1 Časová a paměťová složitost algoritmu
2 Konstrukce binárního kódu
3 Pseudokód
4 Příklady
- 4.1 příklad 1)
- 4.2 příklad 2)
5 Odkazy

Časová a paměťová složitost algoritmu

Časová složitost algoritmu: O(n + |Σ| * log|Σ|)
Paměťová složitost algoritmu: O(|Σ|)

Z uvedeného popisu algortimu plynou následující fáze. Z hlediska časové složitosti je zde fráze výpočtu četnosti jednotlivých znaků, lineárně závislá na délce vstupního textu. Dále fáze seřazení znaků, závislá na použitém adícím algoritmu. Následuje generování výstupu, též lineárně závislé na délce vstupního textu. Paměťová složiost roste lineárně s počtem různých znaků ve vstupu.^[1]

Konstrukce binárního kódu

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.^[4]

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. ^[5]

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 ^[2]

Příklady

příklad 1)

Symbol	Počet výskytů
F	5
D	4
C	4
A	3
B	3
E	2

Inicializace Seznam je (F,D,C,A,B,E). Kódy všech symbolů jsou prázdné.

Symbol	Kód
F	-
D	-
C	-
A	-
B	-
E	-

Krok 1 = Rozdělit na dvě poloviny s přibližně stejným součtem četností

(F,D) - součet četností: 5 + 4 = 9
(C,A,B,E) - součet četností: 4 + 3 + 3 + 2 = 12

Symbol	Kód
F	0
D	0
C	1
A	1
B	1
E	1

Krok 2 = Nyní oba seznamy rozdělit na poloviny s přibližně stejným součtem četostí

Symbol	Kód
F	0 0
D	0 1
C	1 0
A	1 0
B	1 1
E	1 1

Krok 3 = Seznamy (F) a (D) již rozložit nejdou, zbývá zpracovat seznamy (C,A) a (B,E). Opět oba rozložit na poloviny s přibližně stejným součtem četností.