Domů » Informatika » Kódování » Shannon-Fanovo kódování

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ů (případně pravděpodobnos­tech). 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ů.

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é.

počáteční stav

Symbol Kód
F –
D –
C –
A –
B –
E –
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

první krok

Symbol Kód
F 0
D 0
C 1
A 1
B 1
E 1
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

po druhém kroce

Symbol Kód
F 00
D 01
C 10
A 10
B 11
E 11
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
      • © – 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

po třetím a posledním kroce

Symbol Kód
F 00
D 01
C 100
A 101
B 110
E 111
Výsledek
Symbol Kód
F 00
D 01
C 100
A 101
B 110
E 111

Reference