Huffmanovo kódování

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.

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.

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í

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).

Súvisiace články

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