eXe

Nyní se již dostáváme k Huffmanovu kódování. Po úvodním seznámení se základním principem Huffmanova algoritmu budou následovat dvě podkapitoly s konkrétními příklady kódování.

Přibližný čas, který strávíte studiem této kapitoly, je 30 - 40 minut.

Huffmanův algoritmus kódování je jedním z klasických algoritmů používaných pro bezeztrátovou kompresi dat (bezeztrátové komprese PKZIP, BZIP2 atd. a v jistém kroku i jinak ztrátové komprese JPEG a MP3). Prakticky existují dva typy Huffmanova kódování, a to kódování statické a kódování adaptivní (dynamické). V tomto textu se budeme zabývat pouze statickým kódováním. Základní myšlenkou je zakódování znaků podle počtu jejich výskytů ve vstupu tak, že znaky, které se vyskytují nejčastěji, mají nejkratší kód.

Algoritmus, který při zadané pravděpodobnosti výskytu zdrojových symbolů p_i vytvoří kód minimální délky, objevil D. A. Huffman (čti: Hafmen) v roce 1952. Tento algoritmus není a ani nebyl nikdy patentován, přesto v implementaci v Open Source programech BZIP2 algoritmus poráží, nebo je rovným soupeřem jiných, draze licencovaných kompresních algoritmů (aritmetická komprese apod.).

Statické kódováni je dvoufázová metoda. Nejprve se provede výpočet četnosti, resp. pravděpodobnosti výskytu daného znaku ve vstupním proudu. Dále se podle algoritmu vypočte prefixový kód, tj. provede se zakódování znaků zdrojové abecedy pomocí prefixového kódu do kódové abecedy. Tento algoritmus používá tzv. binární stromy, kde hodnoty uzlů od kořene k listům stromu tvoří jednotlivá kódová slova.

Huffmanova konstrukce binárního kódu

Zdrojové znaky uspořádáme sestupně podle pravděpodobností tak, aby platilo: p₁≥p₂≥... ≥p_r, kde r je počet znaků.
Pokud máme je dva zdrojové znaky (r=2), je nejkratší kód zřejmý:

Znak	a₁	a₂
Kód K	0	1

Pokud obsahuje zdrojová abeceda tři znaky, pracujeme s tzv. redukovanou abecedou, která má znaky a₁ a a_2,3, které mají pravděpodobnost výskytu znaku ve zprávě p₁ a p_2,3 = p₂ + p₃:

Znak	a₁	a_2,3
Kód K	0	1

Kódové slovo "1" rozdělíme na dvě slova "10" a "11" a dostaneme nejkratší kód původní abecedy:

Znak	a₁	a₂	a₃
Kód K	0	10	11

Stejným způsobem by bylo možné postupovat i v případě libovolného počtu zdrojových znaků.

V následujících podkapitolách si ukážeme dva algoritmy, které se hodí pro praktické použití. První z nich je kódování pomocí binárního stromu, druhý je kódování pomocí tabulky.