Huffmanovo kódování

Poll without page-refresh

Article on other languages:

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

Huffmanovo kódování je algoritmus využívaný pro bezeztrátovou kompresi dat^[1]. Konvertuje znaky vstupního souboru do bitových řetězců různé délky. Znaky, které se ve vstupním souboru vyskytují nejčastěji, jsou konvertovány do bitových řetězců s nejkratší délkou (nejfrekventovanější znak tak může být konvertován do jediného bitu), znaky, které se vyskytují velmi zřídka, jsou konvertovány do delších řetězců (mohou být i delší než 8 bitů).

Nejjednodušší metoda komprese touto metodou probíhá ve dvou fázích. Prvni projde soubor a vytvoří statistiku četností každého znaku. Ve druhé fázi se využije této statistiky pro vytvoření binárního stromu a k následné kompresi vstupních dat.

Dekomprese naopak pomocí rekonstruovaného binárního stromu dekoduje řetězce proměnlivé délky.

Algoritmus

Uvažujme příklad, kdy je cílem zakódovat text skládající se ze čtyřech různých symbolů (s₁, s₂, s₃, s₄), jejichž četnosti výskytu v textu jsou (0,08; 0,7; 0,1; 0,12).

Zdrojové znaky se uspořádají postupně podle pravděpodobnostního výskytu p (s₂, s₄, s₃, s₁).
Sečteme poslední dvě pravděpodobnosti (s₃ + s₁ = 0,18) a výsledek zařadíme podle velikosti mezi ostatní pravděpodobnosti – redukce (s₂, s₁₃, s₄).
Znovu sečteme poslední dvě pravděpodobnosti (s₁₃ + s₄ = 0,3) a výsledek opět zařadíme podle velikosti (s₂, s₁₃₄).
Sčítání pravděpodobností provádíme tak dlouho, až dojdeme k součtu 1 (s₂ + s₁₃₄).
Posledním dvěma znakům přiřadíme kódové znaky 1 (s₂, znak s vyšší pravděpodobností) a 0 (s₁₃₄).
Zpětným postupem přiřazujeme jednotlivým sčítancům vždy kódové znaky 1 a 0, dokud nepřiřadíme kódové znaky všem zdrojovým znakům.
Výsledný kód znaku je sestaven ze znaků 1 a 0 podle toho, jak se daný znak seskupoval s ostatními znaky. (s₁₃₄ = 0 → s₁₃ = s₁₃₄1 = 01; s₄ = s₁₃₄0 = 00 → s₃ = s₁₃1 = 011; s₁ = s₁₃0 = 010)

Poznámky

↑ Paradoxně se ale využívá i ve ztrátové kompresi, konkrétně v kompresi JPEG. Zde se používá v poslední fazi, kde se pomocí Huffmanova kódování zakóduje „zig-zag“ posloupnost hodnot bloku. V JPEG-u se využívá její beztrátovost.