- Huffmanovo kódovanie

Huffmanovo kódovanie

Toto kódovanie je pomenované podľa svojho objaviteľa pána D.A.Huffmana. Huffmanov kód patrí medzi kódy pri tvorbe ktorých sa využíva znalosť pravdepodobnosti výskytu jednotlivých kódovaných znakov. Ako prvý s myšlienkou priradiť kratšie kódy častejšie sa vyskytujúcim znakom a dlhšie kódy menej často vyskytujúcim sa znakom prišiel v.r. 1800 pán Samuel Morse. Tento princíp použil na zakódovanie 26 znakov anglickej abecedy pre potreby prenosu telegrafom, čím vznikol dobre známy Morseov kód (abeceda). Huffmanov algoritmus tvorby kódu generuje binárne stromy, kde cesty z počiatočného do koncového uzlu umožňujú vytvoriť kódové slová. Tvorbu binárneho stromu a príslušných Huffmanových kódov si ukážeme na príklade.

Majme vstupnú abecedu danú iba znakmi A,B,C,D a E s danou pravdepodobnosťou výskytu 0,4;0,1;0,1;0,1 a 0,3. Súčet pravdepodobností je rovný 1 a teda dané znaky tvoria celú abecedu. Jednotlivé znaky si zoradíme vzostupne podľa stúpajúcich pravdepodobností výskytu. Vyberieme dva znaky s najnižšou pravdepodobnosťou a sčítame ich pravdepodobnosti, pričom pod súčet podpíšeme znaky z ktorých súčtom vznikol. Ak ja viac znakov s rovnakou pravdepodobnosťou, môžeme do súčtu vziať ľubovolný z nich. Vzniknutý súčet 0,2 tvorí uzol stromu. V bodoch 2. a 4. postupujeme obdobným spôsobom ako v 1. V bode 5. sme dospeli až k vrcholu stromu, ktorý musí mať vždy hodnotu rovnú jednej a tvorba stromu sa skončila. Všimnite si, že všetky znaky (A,B,C,D a E) ležia v listoch stromu. 

1.    0,1  0,1  0,1  0,3  0,4
       B    C    D    E    A


2.    0,1  0,2  0,3  0,4
       D   / \   E    A
          B   C


3.       0,3  0,3  0,4
         / \   E    A
        D  0,2
           / \
          B   C


4.      0,4    0,6
         A     / \
             0,3  E
             / \
            D  0,2
               / \
              B   C

-----------------------------------------------------------------
5.       1         alebo         1     alebo     1       ....
      0/   \1                 0/   \1         0/   \1     
      A   0,6                0,6    A        0,6    A     
         0/  \1             0/  \1          0/  \1
         E  0,3            0,3   E          E  0,3
           0/  \1         0/  \1              0/  \1
           D  0,2        0,2   D              D   0,2
             0/  \1     0/  \1                  0/  \1
             B    C     C    B                  B   C
Znak p Kódové slová
A 0,4 0 1 1
B 0,1 1110 0001 0110
C 0,1 1111 0000 0111
D 0,1 110 001 010
E 0,3 10 01 00

Jednotlivé vetvy stromu si označíme binárnymi hodnotami 0 a 1 (označené sú modrou farbou) a môžeme začať z binárneho stromu odčítavať kódy prislúchajúce daným znakom. Začíname od vrcholu stromu a ľavou vetvou sa dostaneme k znaku A. Vetve ktorou sme išli prislúcha hodnota 0 a teda Huffmanov kód pre znak A bude 0. Analogickým spôsobom pri pohybe po vetvách stromu až k daným znakom získame ostatné Huffmanové kódy. Získané Huffmanové kódy pre znaky A,B,C,D a E sú v tabuľke v treťom stĺpci. Povšimnite si, že rôznym otáčaním vetiev v binárnom strome (druhý a tretí strom v bode 5.) a následnej konštrukcii Huffmanových kódov, získame pre danú abecedu rôzne kódy. Všetky riešenia sú správne. Dôležité je, že takto získaný kód má niektoré významné vlastnosti.

Prefixové kódy musia spĺňať tzv. podmienku prefixu, ktorá hovorí, že žiadne kódové slovo nesmie byť prefixom (počiatkom) reťazca iného kódového slova. Prefixový kód je jednoznačne dekódovateľný. Každý prefixový kód môžeme zobraziť pomocou binárneho stromu.

V praxi to znamená asi toľko, že ak kóder vyšle napríklad kódy (podľa tretieho stĺpca tabuľky) 1111100 odpovedajúce znakom C E A , dekóder ich bude vedieť jednoznačne dekódovať bez toho, aby sme jednotlivé kódy oddeľovali pomocou nejakých oddeľovacích značiek. Prirodzene, že dekóder musí disponovať rovnakou tabuľkou Huffmanových kódov (musí poznať strom ktorý vytvoril kóder) ktoré použil kóder pri kódovaní znakov. Jednoducho musí vedieť že 110 odpovedá znaku D atď.
Postup: dekóder príjme prvú hodnotu 1 a žačne sa pohybovať od vrcholu stromu až k jednotlivým listom. Po štyroch vetvách s hodnotami 1 sa dostane k listu, ktorému odpovedá znak C (1111). Z listu sa už ďalej nemôže pohnúť a vie, že ak sa dostal do listu, nasledujúca hodnota ktorú bude dekódovať, bude počiatkom kódového slova ďalšieho znaku (začne postupovať znova od vrcholu stromu). Toto je nesmierne dôležité, pretože takto môžeme kód jednoznačne dekódovať.

Znak Kódové slová
A 10
B 00
C 11
D 110

Pre porovnanie v nasledujúcej tabuľke je kód, ktorý nieje prefixový.

Napr. postupnosť 1101100 by sme nevedeli jednoznačne dekódovať,  pretože začiatočné bity 11 môžu predstavovať kód pre znak C, alebo začiatočné dva bity kódu D (110).

Huffmanov kód pridelí kód každému znaku zo vstupného súboru, kde najkratší kód má dĺžku 1 bit a ďalšie kódy majú vzrastajúcu dĺžku kódu (menej pravdepodobné znaky majú dlhší kód ako viac pravdepodobné). Optimálny počet bitov potrebných pre zakódovanie daného znaku sa dá vyjadriť pomocou vzťahu -log2(1/p), kde p je pravdepodobnosť výskytu znaku. Tak napríklad pre znak s pravdepodobnosťou výskytu 1/256 je potrebných -log2(1/256)=8 bitov. Pokiaľ je pravdepodobnosť výskytu znaku mocninou 1/2, počet bitov potrebných k zakódovaniu je vždy celé číslo. Problém pri použití Huffmanovho kódu nastáva v prípade, ak pravdepodobnosť výskytu znaku nieje mocninou 1/2. Napríklad znak z príkladu s pravdepodobnosťou 1/3 potrebuje na zakódovanie približne 1,6 bitov, ale dĺžka kódového slova môže byť len celé číslo (1,2,3,...). V príklade sme znak zakódovali pomocou 2 bitov, čo je však viac ako teoretické minimum 1,6 bitov. U ostatných znakov je to podobné. Z toho vyplýva, že správu sme zakódovali pomocou väčšieho počtu bitov, ako je teoretické minimum.

Huffmanov algoritmus komprimuje efektívne iba informácie so známym rozdelením pravdepodobnosti (poznáme rozdelenie pravdepodobnosti s akou zdroj informácií tieto informácie produkuje). Pri kódovaní informácií s "nesprávnym rozdelením" sa priemerná dĺžka kódového slova predĺži. Huffmanov kód je teda citlivý na odhad rozdelenia pravdepodobnosti. V praxi sa na zisťovanie štatistických informácií o zdroji dát používajú metódy na odhad rozdelenia pravdepodobnosti, ktoré priebežne robia odhad rozdelenia pravdepodobnosti . Existujú aj univerzálne kódovacie schémy, ako napríklad LZ, LZW a iné, ktoré dokážu komprimovať veľké množstvo údajov, bez potreby poznať štatistické charakteristiky zdroja. Huffmanovo kódovanie sa v praxi využíva hlavne v kombinácii s inými kompresnými algoritmami napr. pri kompresii obrazu a videa v štandardoch JPEG a MPEG a je tiež použité napr. v kompresnom algoritme LZ77 v metóde deflate.

Informačné zdroje

[1] Michael Schindler, "Practical Huffman coding", Aug., Oct. 1998
      http://www.compressconsult.com/huffman/
[2] Mark Nelson, "Arithmetic Coding + Statistical Modeling = Data Compression",
      Dr. Dobb's Journal February, 1991,
       http://www.dogma.net/markn/articles/arith/part1.htm

[hlavná strana]

Dušan SOVIČ