Huffmanovo kódování

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), zatímco 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. První 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 dekóduje řetězce proměnlivé délky.

Algoritmus

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

1. Zdrojové znaky se uspořádají postupně podle pravděpodobnostního výskytu p (s₂, s₄, s₃, s₁).
2. 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₄).
3. Znovu sečteme poslední dvě pravděpodobnosti (s₁₃ + s₄ = 0,3) a výsledek opět zařadíme podle velikosti (s₂, s₁₃₄).
4. Sčítání pravděpodobností provádíme tak dlouho, až dojdeme k součtu 1 (s₂ + s₁₃₄).
5. Posledním dvěma znakům přiřadíme kódové znaky 1 (s₂, znak s vyšší pravděpodobností) a 0 (s₁₃₄).
6. 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.
7. 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)

Je známo více variací Huffmanova kódování, ale není mezi nimi téměř žádný rozdíl v účinnosti komprese dat.

Poznámky

1. Paradoxně se ale využívá i ve ztrátové kompresi, konkrétně v kompresi JPEG. Zde se používá v poslední fázi, kde se pomocí Huffmanova kódování zakóduje „cik-cak“ posloupnost hodnot bloku. V JPEG-u se využívá její bezztrátovost. Další využití je ve ztrátové audio kompresi (MP3, Ogg/Vorbis, WMA, ACC)

Související články

• Shannon-Fanovo kódování
• LZW
• Deflate
• LZMA

Literatura

• SOBOTA, B., MILIÁN, J.: Grafické formáty, Kopp, ISBN 80-85828-58-8

Externí odkazy

• Webová aplikace generující Huffmanovy stromy
• Program ukazující proces tvorby Huffmanova stromu