English
předchozí hlavní stránka obsah další

Shannon-Fanovo kódování

Základní informace

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

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

Z uvedeného popisu algoritmu plynou následující fáze. Z hlediska časové složitosti je zde fá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žitost roste lineárně s počtem různých znaků ve vstupu.

Historie

Tato metoda pochází z roku 1949. Publikovali ji nezávisle na sobě Claude Elwood Shannon (ten je označován jako otec teorie informace) s Warrenem Weaverem a Robert Mario Fano.

Popis

Jak je vidět v pseudokódu algoritmu, jsou vyžadovány dva průchody přes vstupní data. Na základě četnosti symbolů ve vstupním textu jsou jednotlivým symbolům přiřazeny kódy. Metodou shora dolů je tak vytvořen prefixový kód proměnné délky. Symboly se nejprve seřadí podle četnosti jejich výskytu. Potom probíhá rekurzivní dělení seznamu symbolů na pokud možno stejné poloviny podle četnosti znaků.

Nejprve se na výstup zapíše počet různých symbolů, použitých v textu. Potom se do výstupu vypíše zakódovaný strom, který si lze představit vystavěný nad rozděleným seznamem. Zapisuje se ohodnocení větví od kořene, zleva doprava. Levé hrany jsou ohodnoceny 1, pravé 0. První ohodnocení se zapisuje celé, dále se zapisují pouze nutné údaje. Dále se pomocí Fibonacciho kódu 2. řádu zapíše počet listů. Potom začne probíhat kódování vstupu.

Pseudokód


 1:  begin
 2:     spočti četnosti vstupních symbolů
 3:     setřiď je do neklesající posloupnosti
 4:     SF-Split(S)
 5:     output(počet symbolů, zakódovaný strom, symboly)
 6:     vytvoř výstupní zprávu
 7:  end
 8:  
 9:  procedure SF-Split(S)
10:  begin
11:     if (|S|>1) then
12:      begin
13:        rozděl S na S1 a S2 s přibližně stejným počtem výskytů
14:        ke kódovým slovům S1 přidej 1
15:        ke kódovým slovům S2 přidej 0
16:        SF-Split(S1)
17:        SF-Split(S2)
18:      end
19:  end

Odkazy

  1. Shannon-Fano coding. Wikipedia, the free encyclopedia.
  2. Claude Elwood Shannon. Wikipedia, the free encyclopedia.
  3. C. E. Shannon: A Mathematical Theory of Communication. The Bell System Technical Journal, Vol. 27, July, October, 1948.
  4. C. E. Shannon: Prediction and Entropy of Printed English. The Bell System Technical Journal, Vol. 30, 1951.
  5. C. E. Shannon: Communication Theory of Secrecy Systems. The Bell System Technical Journal, Vol. 28, 1949.

Ukázka