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

(Založena nová stránka s textem „== Základný popis == Huffmanové kódovanie. Znaky, vyskytujúce sa vo vstupnom súbore najčastejšie, sa konvertujú na bitové reťazce s najkratšou…“)
 
Řádek 1: Řádek 1:
== Základný popis ==
+
= Základný popis =
Huffmanové kódovanie. 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.  
+
Huffmanové kódovanie. 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.<ref>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>
== História==
+
= 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.<ref><i>Huffman coding</i>. San Francisco: Wikimedia Foundation. Dostupné také z: https://en.wikipedia.org/wiki/Huffman_coding</ref>
 
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.<ref><i>Huffman coding</i>. San Francisco: Wikimedia Foundation. Dostupné také z: https://en.wikipedia.org/wiki/Huffman_coding</ref>
 
+
= Konštrukcia kódu =
 +
* Usporiadame si pravdepodobnosti výskytu jednotlivých znakov zostupne
 +
* Sčítajú sa posledné dve pravdepodobnosti a výsledok zaradíme medzi ostatné pravdepodobnosti výskytu
 +
*      Krok č. 2 opakujeme dovtedy, kým sa nedopracujeme k jednému znaku s pravdepodobnosťou 1
 +
*      Výsledné kódové slová zapíšeme v opačnom poradí
 +
 
<references />
 
<references />

Verze z 15. 9. 2015, 10:16

Základný popis

Huffmanové kódovanie. 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

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