Huffmanovo kódování
Z Wikipedie, otevřené encyklopedie
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.
Komprese
Dekomprese:
[editovat] Algoritmus
Uvažujme příklad, kdy je cílem zakódovat text skládající se ze čtyřech různých symbolů (s1, s2, s3, s4), 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 (s2, s4, s3, s1).
- Sečteme poslední dvě pravděpodobnosti (s3 + s1 = 0,18) a výsledek zařadíme podle velikosti mezi ostatní pravděpodobnosti – redukce (s2, s13, s4).
- Znovu sečteme poslední dvě pravděpodobnosti (s13 + s4 = 0,3) a výsledek opět zařadíme podle velikosti (s2, s134).
- Sčítání pravděpodobností provádíme tak dlouho, až dojdeme k součtu 1 (s2 + s134).
- Posledním dvěma znakům přiřadíme kódové znaky
1(s2) a0(s134). - Zpětným postupem přiřazujeme jednotlivým sčítancům vždy kódové znaky
1a0, dokud nepřiřadíme kódové znaky všem zdrojovým znakům. - Výsledný kód znaku je sestaven ze znaků
1a0podle toho, jak se daný znak seskupoval s ostatními znaky. (s134 =0→ s13 = s1341=01; s4 = s1340=00→ s3 = s131=011; s1 = s130=010)
[editovat] 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.

