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

  1. Zdrojové znaky se uspořádají postupně podle pravděpodobnostního výskytu p (s2, s4, s3, s1).
  2. 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).
  3. Znovu sečteme poslední dvě pravděpodobnosti (s13 + s4 = 0,3) a výsledek opět zařadíme podle velikosti (s2, s134).
  4. Sčítání pravděpodobností provádíme tak dlouho, až dojdeme k součtu 1 (s2 + s134).
  5. Posledním dvěma znakům přiřadíme kódové znaky 1 (s2) a 0 (s134).
  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. (s134 = 0 → s13 = s1341 = 01; s4 = s1340 = 00s3 = s131 = 011; s1 = s130 = 010)

Příklad

[editovat] Poznámky

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


[editovat] Podívejte se také na