Shannon-Fanovo kódování je technika pro sestavení prefixového kódu založená na seznamu symbolů a počtech jejich výskytů (případně pravděpodobnostech). Metodu nezávisle na sobě publikovali v roce 1949 Claude Elwood Shannon s Warrenem Weaverem a Robert Mario Fano.

Shannon-Fanův algoritmus lze využít i pro kompresi dat - je to metoda statistická, dvouprůchodová, semiadaptivní a asymetrická. Narozdíl od Huffmanova kódování není optimalita výsledného kódu zaručena.

Pseudokód

  1. Pro danou zprávu vytvoř seznam symbolů a zjisti počet jejich výskytů (nebo pravděpodobnost).
  2. Seznam symbolů seřaď do neklesající posloupnosti podle této hodnoty.
  3. Kódy všech symbolů jsou zpočátku prázdné.
  4. Rozděl seznam na dvě poloviny tak, aby součet sledovaných hodnot byl v obou částech zhruba stejný.
  5. Ke kódům symbolů v levé polovině připoj 0, ke kódům symbolů v pravé polovině připoj 1.
  6. Rekurzivně opakuj od kroku 4 na levou i pravou polovinu seznamu.

Příklad

Tabulka symbolů a jejich četností

Symboly jsou seřazené do neklesající posloupnosti podle počtu výskytů.

SymbolPočet výskytů
F5
D4
C4
A3
B3
E2
Inicializace

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

SymbolKód
F-
D-
C-
A-
B-
E-
diagram
Krok 1

Seznam je (F,D,C,A,B,E). Nyní jej rozdělíme na dvě poloviny s příbliž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
SymbolKód
F0
D0
C1
A1
B1
E1
diagram
Krok 2

Seznamy jsou (F,D) a (C,A,B,E). Nyní je oba rozdělíme na poloviny s příbližně stejným součtem četností.

  • (F,D) - součet četností: 5 + 4 = 9
    • (F) - součet četností: 5
    • (D) - součet četností: 4
  • (C,A,B,E) - součet četností: 4 + 3 + 3 + 2 = 12
    • (C,A) - součet četností: 4 + 3 = 7
    • (B,E) - součet četností: 3 + 2 = 5
SymbolKód
F00
D01
C10
A10
B11
E11
diagram
Krok 3

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

  • (F,D) - součet četností: 5 + 4 = 9
    • (F) - součet četností: 5
    • (D) - součet četností: 4
  • (C,A,B,E) - součet četností: 4 + 3 + 3 + 2 = 12
    • (C,A) - součet četností: 4 + 3 = 7
      • (C) - součet četností: 4
      • (A) - součet četností: 3
    • (B,E) - součet četností: 3 + 2 = 5
      • (B) - součet četností: 3
      • (E) - součet četností: 2
SymbolKód
F00
D01
C100
A101
B110
E111
diagram
Výsledek
SymbolKód
F00
D01
C100
A101
B110
E111

Reference