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

 
(Není zobrazeno 80 mezilehlých verzí od 5 dalších uživatelů.)
Řádek 1: Řádek 1:
−
=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'')<ref name="stringology"><i>Shannon-Fanovo kódování</i>. Dostupné také z: http://www.stringology.org/DataCompression/sf/index_cs.html</ref> s Warrenem Weaverem a Robertem Mario Fano.<ref name="voho"><i>Shannon-Fanovo kódování</i>. Dostupné také z: http://voho.eu/wiki/kodovani-shannon-fano/</ref>
−
Je pomenované po Claude Elwood Shannonovi a Robertovi Fanovi, ktorí zostrojili kód s vlastnosťou prefixu na základe pravdepodobností výskytu znakov.
+
 
−
=Konštrukcia kódu=
+
==Základní informace==
−
Postup konštrukcie je podobný ako pri Huffmanovom kódovaní. Rozdiel spočíva len smere konštrukcie binárneho stromu.
+
 
−
# Jednotlivé znaky si zoradíme zostupne podľa pravdepodobnosti výskytu
+
* Řešení nemusí být vždy optimální (nejkratší)
−
# Pri zachovaní poradia znakov, rozdelíme množinu na dve časti tak, aby bol výsledný rozdiel súčtov pravdepodobnosti čo najmenší
+
* Používá se v kompresních datech <ref><i>Teorie kódování: Shannon-Fanova metoda</i>. Praha: Konrád Černý. Dostupné také z: https://files.klaska.net/sites/files.klaska.net/files/manual_files/cvut/Teorie kodovani/Shannon-Fanovo k_dov_n_.pdf</ref>
−
# Jednotlivým častiam pridelíme kódový znak 0 alebo 1
+
* Asymetrická kompresní metoda
−
# Kroky 2 a 3 opakujeme dovtedy, kým sa nedopracujeme k jednoprvkovým množinám
+
* Dvouprůchodová kompresní metoda
−
# Jednotlivé kódové slová získame čítaním kódových znakov v poradí v akom im boli prideľované <ref>IVÁNEK, Jiří. <i>Vybrané kapitoly z kódování informací</i>. Praha, 2007. Dostupné také z: texty.jinonice.cuni.cz/studijni-texty/ivanek-jiri/ivanek_01.pdf/attachment_download/file</ref>  
+
* Semi-adaptivní kompresní metoda
−
=Príklad=
+
* Dosahuje horších výsledků ve srovnání s Huffmanovým kódováním <ref name="stringology"/>
−
Konštrukciu stromu podľa vyššie uvedeného postupu si ukážeme na jednoduchom príklade:
+
[[File:shannon.jpg|thumb|120px|C.E.Shannon]]
 +
 
 +
===Č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.<ref name="stringology"/>
 +
 
 +
==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.<ref><i>Optimální (entropické) kódování informačního zdroje</i>. Dostupné také z: https://wikisofia.cz/wiki/Optimální_(entropické)_kódování_informačního_zdroje</ref>
 +
 
 +
* 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. <ref>RADOMIL, Matoušek. <i>Metody kódování</i>. Brno, 2006, 96 s. Dostupné také z: http://www.uai.fme.vutbr.cz/~matousek/TIK/TIKv19.pdf</ref>
 +
 
 +
==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 <ref name="voho"/>
 +
 
 +
==Příklady==
 +
 
 +
=== '''příklad 1)''' ===
 +
 
 +
{| class="wikitable"
 +
|-
 +
! Symbol !! Počet výskytů
 +
|-
 +
| F || 5
 +
|-
 +
| D || 4
 +
|-
 +
| C || 4
 +
|-
 +
| A || 3
 +
|-
 +
| B || 3
 +
|-
 +
| E || 2
 +
|}
 +
[[File:1.PNG|thumb|200px|B)]]  [[File:2.PNG|thumb|200px|C)]][[File:3.PNG|thumb|200px|D)]]
 +
 
 +
 +
<table>
 +
<tr>
 +
<td> A)
 +
{| class="wikitable"
 +
|-
 +
! Symbol !! Kód
 +
|-
 +
| F || -
 +
|-
 +
| D || -
 +
|-
 +
| C || -
 +
|-
 +
| A || -
 +
|-
 +
| B || -
 +
|-
 +
| E || -
 +
|}
 +
 
 +
</td>
 +
<td> B)
 +
 
 +
{| class="wikitable"
 +
! Symbol !! Kód
 +
|-
 +
| F || 0
 +
|-
 +
| D || 0
 +
|-
 +
| C || 1
 +
|-
 +
| A || 1
 +
|-
 +
| B || 1
 +
|-
 +
| E || 1
 +
|}
 +
 
 +
</td>
 +
<td> C)
 +
 
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
−
! Zdrojová abeceda !! a1 !! a2 !! a3 !! a4 !! a5 !! a6 !! a7 !! a8
+
! Symbol !! Kód
 +
|-
 +
| F || 0 '''0'''
 +
|-
 +
| D || 0 '''1'''
 +
|-
 +
| C || 1 '''0'''
 +
|-
 +
| A || 1 '''0'''
 +
|-
 +
| B || 1 '''1'''
 
|-
 
|-
−
! Pravdepodobnosť výskytu !! 0,22 || 0,19 || 0,18 || 0,15 || 0,10 || 0,09 || 0,04 || 0,03
+
| E || 1 '''1'''
 
|}
 
|}
−
[[File:Fanov_strom.jpg|400px]]<ref name=TUKE>KRAVECOVÁ, Daniela. <i>Základy kódovania</i>. Košice: Technická univerzita v Košiciach, 2012. ISBN 978-80-553-1178-4. Dostupné také z: http://web.tuke.sk/fei-km/sites/default/files/prilohy/15/Zaklady_kodovania_ucebnica.pdf</ref>
 
  
−
Jednotlivé kódové slová sa čítajú zhora nadol. V nasledujúcej tabuľke sú zobrazené výsledné kódové slová:
+
</td>
 +
<td> D)
 +
 
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
−
! a1 !! a2 !! a3 !! a4 !! a5 !! a6 !! a7 !! a8
+
! Symbol !! Kód
 +
|-
 +
| F || 0 0
 +
|-
 +
| D || 0 1
 +
|-
 +
| C || 1 0 '''0'''
 
|-
 
|-
−
| 00 || 01 || 100 || 101 || 110 || 1110 || 11110 || 11111
+
| A || 1 0 '''1'''
 +
|-
 +
| B || 1 1 '''0'''
 +
|-
 +
| E || 1 1 '''1'''
 
|}
 
|}
  
−
=Využitie=
+
</td>
−
V praxi sa využíva omnoho menej než Huffmanove kódovanie, pretože nie vždy produkuje optimálny kód, ale aj napriek tomu sa využíva pri kompresii dát vo formáte ZIP.  
+
<td>  Konečná verze
−
==Odkazy==
+
 
−
===Reference===
+
{| class="wikitable"
−
<references/>
+
|-
−
==Súvisiace články==
+
! Symbol !! Kód
 +
|-
 +
| F || 0 0
 +
|-
 +
| D || 0 1
 +
|-
 +
| C || 1 0 0
 +
|-
 +
| A || 1 0 1
 +
|-
 +
| B || 1 1 0
 +
|-
 +
| E || 1 1 1
 +
|}
 +
 
 +
</td>
 +
</tr>
 +
</table>
 +
 
 +
'''Inicializace''' = Seznam je (F,D,C,A,B,E). Kódy všech symbolů jsou prázdné.
 +
 
 +
'''''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
 +
                                       
 +
'''''Krok 2''''' = Nyní oba seznamy rozdělit na poloviny s přibližně stejným součtem četostí
 +
                                         
 +
'''''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í.<ref name="voho"/>
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
=== '''příklad 2)''' ===
 +
 
 +
* Vstupní soubor: ABRAKADABRA
 +
* Jednotlivé znaky: A    B    D    K    R
 +
* Počty výskytů:  (5) (2) (1) (1) (2)
 +
* Vytvořený strom:
 +
[[File:ABDKR.PNG|200px]]<ref><i>Shannon-Fanovo kódování</i>. Dostupné také z: https://atrey.karlin.mff.cuni.cz/~tnovak/compress/huffman/shannon.html</ref>
 +
 
 +
==Využití==
 +
 
 +
#Využití distribuční funkce/kumulované pravděbodobnosti zdroje.
 +
#Při kompresy dat ve formátu ZIP.<ref>JAN, Outrata. <i>Komprese dat</i>. Dostupné také z: http://outrata.inf.upol.cz/courses/kd/komprese.pdf</ref>
 +
 
 +
== Odkazy ==
 +
 
 +
=== Reference ===
 +
 
 +
<references />
 +
 
 +
=== Související články ===
 +
 
 
[[Optimální (entropické) kódování informačního zdroje]]
 
[[Optimální (entropické) kódování informačního zdroje]]
 +
 
[[Huffmanove kódovanie]]
 
[[Huffmanove kódovanie]]
 +
 +
[[Kódování]]
 +
 +
=== Klíčová slova ===
 +
kódování, Shannon, Fano, Shannon-Fanovo kódování
 +
[[Kategorie:Informační studia a knihovnictví]]

Aktuální verze z 26. 1. 2019, 16:18

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]

Základní informace

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

Č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

  1. Pro danou zprávu vytvořit seznam symbolů a zjistit počet jejich výskytů (nebo pravděpodobnost)
  2. Seznam symbolů seřadit do neklesající posloupnosti podle této hodnoty
  3. Kódy všech symbolů jsou zpočátku prázdné
  4. Rozdělit seznam na dvě poloviny tak, aby součet sledovaných hodnot byl v obou částech zhruba stejný
  5. Ke kódům symbolů levé polovině připojit 0, ke kódům symbolů v pravé polovině připojit 1
  6. 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
B)
C)
D)


A)
Symbol Kód
F -
D -
C -
A -
B -
E -
B)
Symbol Kód
F 0
D 0
C 1
A 1
B 1
E 1
C)
Symbol Kód
F 0 0
D 0 1
C 1 0
A 1 0
B 1 1
E 1 1
D)
Symbol Kód
F 0 0
D 0 1
C 1 0 0
A 1 0 1
B 1 1 0
E 1 1 1
Konečná verze
Symbol Kód
F 0 0
D 0 1
C 1 0 0
A 1 0 1
B 1 1 0
E 1 1 1

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

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

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

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í.[2]





příklad 2)

  • Vstupní soubor: ABRAKADABRA
  • Jednotlivé znaky: A B D K R
  • Počty výskytů: (5) (2) (1) (1) (2)
  • Vytvořený strom:

ABDKR.PNG[6]

Využití

  1. Využití distribuční funkce/kumulované pravděbodobnosti zdroje.
  2. Při kompresy dat ve formátu ZIP.[7]

Odkazy

Reference

  1. ↑ 1,0 1,1 1,2 Shannon-Fanovo kódování. Dostupné také z: http://www.stringology.org/DataCompression/sf/index_cs.html
  2. ↑ 2,0 2,1 2,2 Shannon-Fanovo kódování. Dostupné také z: http://voho.eu/wiki/kodovani-shannon-fano/
  3. ↑ Teorie kódování: Shannon-Fanova metoda. Praha: Konrád Černý. Dostupné také z: https://files.klaska.net/sites/files.klaska.net/files/manual_files/cvut/Teorie kodovani/Shannon-Fanovo k_dov_n_.pdf
  4. ↑ Optimální (entropické) kódování informačního zdroje. Dostupné také z: https://wikisofia.cz/wiki/Optimální_(entropické)_kódování_informačního_zdroje
  5. ↑ RADOMIL, Matoušek. Metody kódování. Brno, 2006, 96 s. Dostupné také z: http://www.uai.fme.vutbr.cz/~matousek/TIK/TIKv19.pdf
  6. ↑ Shannon-Fanovo kódování. Dostupné také z: https://atrey.karlin.mff.cuni.cz/~tnovak/compress/huffman/shannon.html
  7. ↑ JAN, Outrata. Komprese dat. Dostupné také z: http://outrata.inf.upol.cz/courses/kd/komprese.pdf

Související články

Optimální (entropické) kódování informačního zdroje

Huffmanove kódovanie

Kódování

Klíčová slova

kódování, Shannon, Fano, Shannon-Fanovo kódování

Citováno z „https://wikisofia.cz/w/index.php?title=Shannon-Fanovo_kódování&oldid=57041“