A Huffman-kódolás karakterek (jelek, betűk, számjegyek) olyan kódolását jelenti, amelyben az egyes kódok nem azonos hosszúságúak (különböző számú bitből állnak) annak érdekében, hogy a szövegek átlagosan rövidebbek legyenek, mint az azonos hosszúságú kódok használata esetében. Ez a karakterek gyakoriságának figyelembe vételével történik. A kódolás egy mohó stratégián alapszik, és az adattömörítésben igen hatékonyan használható.
Az algoritmus A karaktereket gyakoriságuk szerint növekvő sorrendbe rendezzük egy sorozatba (a sorrend nem szigorúan növekvő, tehát lehetnek egyenlő értékek is). A gyakoriságokat többnyire százalékban adjuk meg. Ezután egy bináris fát építünk fel lépésről-lépésre a következő módon. Kiválasztjuk a sorozat két legkisebb gyakoriságú elemét, amely egy háromcsúcsú bináris fa két levele lesz (amelyeket a gyakorisággal címkézzük meg), majd ezekhez hozzárendelünk egy gyökeret, amelyet a két gyakoriság összegével címkézünk meg (lásd a) ábra). Ezután a két vizsgált elemet kitöröljük a sorozatból, és azok összegét beszúrjuk az érték szerinti megfelelő helyre. Ezután folytatjuk az előző műveletet mindaddig, amíg van elem a sorozatban. Természetesen, a folytatásnál felhasználjuk a már meglévő csúcsokat is, csak újabb elemeknél hozunk létre újabbakat. Az így felépített fában a levelek az eredeti karaktereknek (illetve azok gyakoriságának) felelnek meg.
Az eredményül kapott fában, minden csúcs esetében címkézzük meg 0-val a belőle kiinduló bal oldali élt, 1-gyel pedig a jobb oldalit.
A gyökértől egy adott levélig egyetlen út halad. Ezen út éleihez rendelt 0 és 1 címkéket sorrendben összeolvasva, megkapjuk a levélhez rendelt karakter kódját. Látható, hogy a gyakoribb karakterek kódja rövidebb, míg a kevésbé gyakoribbaké hosszabb lesz.
Attól függően, hogy a bináris fa felépítésében egy adott lépésben melyik elem kerül balra és melyik jobbra, különböző eredményt kaphatunk, de ez nem befolyásolja a kapott kód hatékonyságát.
Az algoritmus pontos leírása:
Legyenek a gyakoriságok: f1 ≤ f2≤ ...≤ fn. Ameddig a sorozat nem üres, végezzük el a következőket: Amennyiben nem létezik az f1 és f2 címkéjű csúcs (egyike vagy mindkettő), hozzuk azt létre. Hozzuk létre az f1 + f2 címkéjű csúcsot, amely legyen az előbbi két csúcs szülője, azaz kössük össze a szülőcsúcsot az előbbi kettővel egy-egy éllel. Töröljük ki a sorozatból az f1 és f2 értékeket, és szúrjuk be a megfelelő helyre ezek összegét úgy, hogy a sorozat növekvő maradjon. Az így kapott sorozatot jelöljük továbbra is az f1 ≤ f2≤ ... módon. Az eredményül kapott bináris fa éleit címkézzük meg a fentebb leírt módon, megkapva ezáltal az egyes karakterek kódját.
Ha az i-edik levél gyökértől mért távolságát -vel jelöljük, akkor a Huffman-algoritmus által kapott fa esetében a összeg a lehető legkisebb. Ez biztosítja, hogy egy szöveg kódolása rövidebb lesz, mintha azonos hosszúságú kódot használtunk volna. Tulajdonképpen, bármilyen más kódolást használva, ennél jobb eredményt nem lehet elérni.
A visszakódolást az teszi lehetővé, hogy egyik kód sem előtagja (prefixe, prefixuma) a többi kódnak. Így egy szövegben az első olyan kezdőszelet, amelyik egyenlő egy kóddal, egyértelműen meghatározza a kódolt karaktert.
Ezt az algoritmust David A. Huffman (1925–1999) írta le először egy mesteri vizsgadolgozatban, és 1952-ben publikálta.
Példa bélyegkép|jobbra|320px|Az a), b), c), d) ábrák bélyegkép|jobbra|320px|Az e) ábra Az a, l, m, f, t és a szóköz (jelölése: ) karaktereket szeretnénk kódolni a Huffman-algoritmussal, megadva ezek gyakoriságát az alábbiak szerint:
a l m f t 20 40 10 8 7 15
A gyakoriságokat növekvő sorrendbe rendezve:
f m l t a 7 8 10 15 20 40
a következő számsorozatot kapjuk:
7, 8, 10, 15, 20, 40
Az első két elemből felépítjük az a) ábrán látható bináris fát. Ezt a két számot kihagyva, az összegüket beszúrva, a következőt kapjuk:
10, 15, 15, 20, 40
Itt most eldönthetjük, hogy az első vagy a második 15 felel meg a már létező csúcsnak. Tekintsük úgy, hogy az első (Ez a választás nem befolyásolja az eredmény hatékonyságát, de a kapott kódot igen).
Az újonnan kapott bináris fa a b) ábrán látható.
A következő sorozat:
15, 20, 25, 40.
Az innen kapott fa a c) ábrán látható. (Észrevehetjük, hogy az itt szereplő 15-nek új csúcs felel meg.)
Innen kapjuk, hogy a sorozat most már:
25, 35, 40,
és a megfelelő bináris fát a d) ábra mutatja.
Ezek után az utolsó lépésre marad a következő sorozat:
40, 60.
Az eredmény, amely már tartalmazza az élekhez rendelt címkéket is, az e) ábrán található.
A fáról leolvashatjuk a megfelelő kódokat:
011 a 1 f 0000 l 001 m 0001 t 010
Az „alma a fa alatt” szöveg kódolása:
1 001 0001 1 011 1 011 0000 1 011 1 001 1 010 010
(A szóközöket csupán azért tettük ki, hogy a karaktereket jól elkülönítsük, ezek nem elemei a kódolt szövegnek.)
Ha az utolsó lépésben a 40 lett volna a bal oldali csúcs, akkor a kódok így alakultak volna:
111 a 0 f 1000 l 101 m 1001 t 110
Források T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Új algoritmusok, Scolar Kiadó, Budapest, 2003. D. E. Knuth: A számítógép-programozás művészete 1. Alapvető algoritmusok, Műszak Könyvkiadó, Budapest, 2. kiadás, 1994. D.A. Huffman: A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the I.R.E., September 1952, pp. 1098–1102.
További információk
Java-implementáció: GitHub:Glank
Kapcsolódó szócikkek Kódolás
Kategória:Tömörítő algoritmusok