Shannon-Fanovo kódování: Porovnání verzí

Řádek 2: Řádek 2:
 
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'')[http://www.stringology.org/DataCompression/sf/index_cs.html] s Warrenem Weaverem a Robertem Mario Fano.[http://voho.eu/wiki/kodovani-shannon-fano/]
 
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'')[http://www.stringology.org/DataCompression/sf/index_cs.html] s Warrenem Weaverem a Robertem Mario Fano.[http://voho.eu/wiki/kodovani-shannon-fano/]
  
* Řešení nemusí být vždy optimální
+
* Řešení nemusí být vždy optimální (nejkratší)
 
* Používá se v kompresních datech [https://files.klaska.net/sites/files.klaska.net/files/manual_files/cvut/Teorie%20kodovani/Shannon-Fanovo%20k_dov_n_.pdf]   
 
* Používá se v kompresních datech [https://files.klaska.net/sites/files.klaska.net/files/manual_files/cvut/Teorie%20kodovani/Shannon-Fanovo%20k_dov_n_.pdf]   
 
                                                                                 C.E.Shannon [[File:shannon.jpg|120px|C.E.Shannon]] [https://history-computer.com/ModernComputer/thinkers/Shannon.html]                   
 
                                                                                 C.E.Shannon [[File:shannon.jpg|120px|C.E.Shannon]] [https://history-computer.com/ModernComputer/thinkers/Shannon.html]                   
  
 
==Konstrukce binárního kódu==
 
==Konstrukce binárního kódu==
 +
===Princip===
 +
Princip je založen na rekurzivní proceduře, která přiřazuje, pro každou zdrojovou informaci, k jejímu kódovému slovu v jednom kroku binární číslici.
  
 +
* 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[http://www.uai.fme.vutbr.cz/~matousek/TIK/TIKv19.pdf]
  
  

Verze z 19. 12. 2018, 00:38

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]
                                                                                C.E.Shannon C.E.Shannon [4]                  

Konstrukce binárního kódu

Princip

Princip je založen na rekurzivní proceduře, která přiřazuje, pro každou zdrojovou informaci, k jejímu kódovému slovu v jednom kroku binární číslici.

  • 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]