Přeskočit na obsah

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

[editovat | editovat zdroj]

Uvažujme příklad, kdy je cílem zakódovat text skládající se ze čtyř 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, znak s vyšší pravděpodobností) 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

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

  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

[editovat | editovat zdroj]

Literatura

[editovat | editovat zdroj]

Externí odkazy

[editovat | editovat zdroj]