Huffman kód (tömörítési algoritmus)

Legyen adott 5 karakter előfordulási gyakorisága egy szövegben:
a: 3, b: 2, c: 1, e: 6, n:2

Ezeket az előfordulási gyakoriságokat arányaiban felírva: a: 3/14, b: 2/14, c: 1/14, e: 6/14, n: 2/14. Természetesen százalékban is meg lehet ezeket adni (a: 22%, b: 14%, c: 7%, e: 43%, n: 14%).

A Huffman kódok egy fa felrajzolásából kapjuk: Kiválasztjuk a két legkisebb előfordulási valószínűséggel rendelkező elemet, és egymás mellé írjuk a két előfordulási valószínűségi értéket. Majd ezt a két értéket levélként kezelve, az összegüket csomópontként a két levél fölé írjuk. Ezek után kiválasztjuk a harmadik legkisebb valószínűségű elemet, és megnézzük, hogy ennek értéke kisebb-e, mint a csomópont, amiben a két legkisebb valószínűségű elem összege van. Ha kisebb, akkor az említett csomóponttól jobbra, ha nagyobb, akkor a csomóponttól balra írjuk le a gyakorisági értéket, majd a többi elem valószínűségi értékét is ez alapján helyezzük el a fában, míg a gyökérig el nem jutunk (100%, vagy arányoknál a nevező értéke). Ekkor az egy csomópontból balra kiinduló ágra 1-est, a jobbra kiindulóra pedig 0-át írunk, és az egyes elemekhez vezető útvonal alapján felírjuk a kódot.

Néhány szabály, amit a Huffman kód alkalmazása során be kell tartani:

• A két legkisebb valószínűséggel előforduló érték kódja csak az utolsó bitben következik
• Mindig az 1 jelöli a nagyobb, és 0 a kisebb előfordulási gyakoriságot
• Testvérpár tulajdonság: az előfordulási gyakoriságok lentről felfelé, azon belül pedig jobbról balra növekednek. Tehát egy adott értéktől balra lévő érték nem lehet kisebb az adott értékünknél!

A Huffman kódban egyetlen bithiba több egymásra következő érték hibás értelmezését okozhatja. A Huffman kód egyik fontos jellemzője az átlagos szóhossz. Ez úgy számolható, hogy az egyes előfordulási gyakoriságokat megszorozzuk az adott elem kódjának hosszával, és ezeket a szorzatokat összeadjuk. A fenti példa esetében:

2*3/14+4*2/14+4*1/14+1*6/14+3*2/14=0,43+0,57+0,28+0,43+0,43=2,14

Tehát a példánk átlagos szóhossza 2,01. Az ábrát, amelyből a kódokat előállítjuk többféleképpen is fel lehet rajzolni (például, ha nem a 2 legkisebb, hanem a négy legkisebb előfordulási valószínűségű elemet vesszük levélnek). Bárhogy is készítjük el a fát, a Huffman kód átlagos szóhossza mindegyik esetben ugyanannyi.

Hogy ezen variációkból melyik hatékonyabb, azt úgy lehet megtudni, hogy kiszámoljuk a szórásnégyzetet, majd ebből a szórást. Amelyiknek kisebb a szórása az a hatékonyabb.

Átlagos szóhossz: 3*3/14+3*2/14, 3*1/14+1*6/14+3*2/14=0,64+0,43+0,21+0,43+0,43=2,14

(Másik fontos tulajdonsága egy Huffman kódnak, hogy mekkora a kódtömörítés mértéke. Ezt úgy lehet kiszámolni, hogy megnézzük hány biten tudjuk tárolni az elemeket, és azt elosztjuk az átlagos szóhosszal. Esetünkben 5 elemet 23 lehetőséggel tudjuk megjeleníteni, mivel 22-nal csak 4 lehetőségünk van, és az kevés az 5 elem megjelenítéséhez. Ez azt jelenti, hogy 3 bit kell a kódoláshoz, tehát a tömörítés mértéke:

3/2,14=300/214=1,4)