Huffmanovo kódování: Porovnání verzí

m (Michal.Bily přesunul stránku Huffmanove kódovanie na Huffmanovo kódování: Český název)
 
(Není zobrazeno 5 mezilehlých verzí od 4 dalších uživatelů.)
Řádek 31: Řádek 31:
 
===Reference===
 
===Reference===
 
<references />
 
<references />
−
==Súvisiace články==
+
===Súvisiace články===
 
[[Optimální (entropické) kódování informačního zdroje]]
 
[[Optimální (entropické) kódování informačního zdroje]]
 +
[[Shannon-Fanove kódovanie]]
 +
 +
[[Kategorie:Informační studia a knihovnictví]]
 +
[[Kategorie:Zpracování informací a informační servis]]
 +
[[Kategorie:Články k ověření učitelem Souček M]]

Aktuální verze z 29. 3. 2020, 14:06

Základný popis

Znaky, vyskytujúce sa vo vstupnom súbore najčastejšie, sa konvertujú na bitové reťazce s najkratšou dĺžkou. Huffmanove kódovanie má vlastnosť prefixu, t.j. je jednoznačne dekódovateľné. Konštrukcia Huffmanovho kódovania je nejednoznačná t.j. výstupom môže byť viac kódov a jednotlivé kódové slová nemusia mať rovnakú dľžku. Tento jav nastáva vtedy, keď pri redukcii najmenších pravdepodobností máme na výber z viacerých hodnôt. Aj napriek tomuto javu majú Huffmanove kódy sú najkratšie a majú rovnakú priemernú dĺžku.[1]

História

David A. Huffman vynašiel algoritmus optimálneho kódovania v roku 1951, ešte počas štúdia na MIT, kde mu bola pridelená semestrálna práca na tému – najefektívnejší binárny kód. Túto prácu mu zadal jeho profesor Robert M. Fano. Huffman prišiel s ideou frekvenčného binárneho stromu a dokázal, že jeho metóda je najefektívnejšia. Týmto predčil svojho profesora a odstránil hlavnú trhlinu – stavia strom z dola nahor namiesto zhora nadol.[2]

Konštrukcia kódu

  1. Usporiadame si pravdepodobnosti výskytu jednotlivých znakov zostupne
  2. Sčítajú sa posledné dve pravdepodobnosti a výsledok zaradíme medzi ostatné pravdepodobnosti výskytu
  3. Krok č. 2 opakujeme dovtedy, kým sa nedopracujeme k jednému znaku s pravdepodobnosťou 1
  4. Výsledné kódové slová zapíšeme v opačnom poradí [1]

Príklad

Na jednoduchom príklade si ukážeme konštrukciu Huffmanovho kódovania. Budeme postupovať podľa krokov uvedených vyššie.

xi x1 x2 x3 x4 x5 x6 x7
Pi 0,12 0,2 0,11 0,2 0,09 0,09 0,19
Konštrukcia stromu

[3]

Ako máme možnosť vidieť na obrázku, postupne sa sčítavajú znaky s najnižšími pravdepodobnosťami, až kým sa nedporacujeme k pravdepodobnosti 1. Súčasne sa nám vytvoril strom, z ktorého vieme odčítať jednotlivé kódové slová. Na jednotlivé uzly si priradíme kódy 0 a 1.

Výsledné kódy jednotlivých znakov

xi x1 x2 x3 x4 x5 x6 x7
Pi 100 00 101 01 1100 1101 111

Využitie

Huffmanovo kódovanie sa v praxi využíva spolu s inými typmi kódovania, napr. pri kompresii videa(MPEG) alebo obrazu(JPEG).

Odkazy

Reference

  1. ↑ 1,0 1,1 KRAVECOVÁ, Daniela. Základy kódovania. 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
  2. ↑ Huffman coding. San Francisco: Wikimedia Foundation. Dostupné také z: https://en.wikipedia.org/wiki/Huffman_coding
  3. ↑ IVÁNEK, Jiří. Vybrané kapitoly z matematické informatiky a znalostního inženýrství. Praha: Státní nakladatelství technické literatury, 1990. ISBN 8070792175. Dostupné také z: http://uisk.xf.cz/podklady/ivanek3.pdf

Súvisiace články

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

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