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ů (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 = 00 → s3 = 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.

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

Literatura

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

Externí odkazy

Média použitá na této stránce

Huffmanovo kodovani.svg
Huffmanovo kódování