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 8 mezilehlých verzí od 5 dalších uživatelů.) | |||
Řádek 1: | Řádek 1: | ||
− | = Základný popis = | + | == 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.<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> | 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 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> | ||
− | = 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 = | + | == Konštrukcia kódu == |
# Usporiadame si pravdepodobnosti výskytu jednotlivých znakov zostupne | # 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 | # Sčítajú sa posledné dve pravdepodobnosti a výsledok zaradíme medzi ostatné pravdepodobnosti výskytu | ||
Řádek 9: | Řádek 9: | ||
# Výsledné kódové slová zapíšeme v opačnom poradí <ref name="TUKE" /> | # Výsledné kódové slová zapíšeme v opačnom poradí <ref name="TUKE" /> | ||
− | == Príklad == | + | === Príklad === |
Na jednoduchom príklade si ukážeme konštrukciu Huffmanovho kódovania. Budeme postupovať podľa krokov uvedených vyššie. | Na jednoduchom príklade si ukážeme konštrukciu Huffmanovho kódovania. Budeme postupovať podľa krokov uvedených vyššie. | ||
{| class="wikitable" | {| class="wikitable" | ||
Řádek 26: | Řádek 26: | ||
! P<sub>i</sub> !! 100 || 00 || 101 || 01 || 1100 || 1101 || 111 | ! P<sub>i</sub> !! 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=== | ||
+ | <references /> | ||
+ | ===Súvisiace články=== | ||
+ | [[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
Obsah
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
- 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]
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 |
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,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
- ↑ Huffman coding. San Francisco: Wikimedia Foundation. Dostupné také z: https://en.wikipedia.org/wiki/Huffman_coding
- ↑ 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