Huffmanovo kódování – aplet

Aplet demonstruje princip vytváření Huffmanova kódu. Jedná se o nejznámějšího zástupce prefixových kódů. Vlastnost prefixového kódu je, že žádné kódové slovo není předponou (prefixem) jiného, takže je možné slova po přijetí kódované zprávy jednoznačně rozlišit.

Ovládání

Aplet je tvořen dvěma poli pro vstupní a výstupní text, tabulkou pro tvorbu kódu a ovládacími prvky. Do levého vstupního pole se vepíše zprávu k zakódování a tlačítkem Kóduj se započne proces kódování. Klikáním na tlačítko Krok pod tabulkou se pak provádí jednotlivé kroky vytvoření Huffmanovy tabulky binárních kódů, tj. postupné slučování skupin prvků s nejnižší četností. Vrátit se o krok zpět umožňuje tlačítko Zpět.

Jakmile je kód vytvořen, zpřístupní se posuvník pro kódování samotné. Jeho posouváním se jednotlivé symboly nahrazují příslušným kódovým slovem z tabulky. Zároveň se v tabulce barevně zvýrazňují nahrazované znaky.

V jakémkoliv okamžiku je možno stisknout tlačítko Reset, které vyčistí tabulku a odemkne vstupní pole pro novou sekvenci znaků.

Algoritmus sestavení Huffmanovy tabulky

Algoritmus publikoval D. A. Huffman v roce 1952. Znaky častěji se vyskytující ve zprávě se reprezentují kratší kódovou posloupností než znaky zřídka se vyskytující. Pokud je výskyt znaků ve zprávě rozložený rovnoměrně, ke kompresi zprávy nedojde.

Z množiny symbolů vytvoříme frontu a vybereme dva s nejnižší četností/pravděpodobností výskytu.
Tyto dva symboly sloučíme, vytvoříme nový a zařadíme jej do fronty. Jeho četnost bude součtem četností sloučených prvků.
Původním symbolům přiřadíme binární hodnoty 1 a 0. Nezáleží na tom, jak bude symbol s vyšší a nižší pravděpodobností označen, ale je nutné vybrané pravidlo dodržovat po celou dobu tvorby kódu. Pokud mají symboly stejnou četnost, je jedno, jak je označíme. Zpracované symboly vyřadíme z fronty.
Frontu zpracováváme tak dlouho, dokud v ní nezbude pouze jeden prvek.
Nakonec projdeme vytvořeným stromem od kmene k větvím (symbolům) a každému symbolu přiřadíme výsledné kódové slovo podle hodnoty větve.

Kódování řetězce

Zakódování vstupního řetězce proběhne triviálně nahrazením každého vstupního znaku odpovídající posloupností nul a jedniček z Huffmanovy tabulky.

Dekódování

Dekódování probíhá tak, že se načítají jednotlivé bity kódu, a jakmile je nalezena shoda s některým kódem v tabulce, vypíše se dekódpvaný znak. Tak se postupuje až do konce bitového řetězce.