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 = | |
| − | 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= | |
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, 09: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í
- ↑ 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
- ↑ Huffman coding. San Francisco: Wikimedia Foundation. Dostupné také z: https://en.wikipedia.org/wiki/Huffman_coding
Text je dostupný pod licencí Creative Commons Uveďte autora 3.0 Česko při dodržení případných autorských práv a dalších podmínek
© 2013 ISSN: 2336-5897
