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

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)

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

↑ 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

Literatura

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

Externí odkazy

Obrázky, zvuky či videa k tématu Huffmanovo kódování na Wikimedia Commons
Webová aplikace generující Huffmanovy stromy
Program ukazující proces tvorby Huffmanova stromu

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.

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

[1]