Huffman-kódolás
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őszelete (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
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
- Gary Stix (1991. szeptember 1.). „Profile: Information Theorist David A. Huffman”. Scientific American 265 (3), pp.54–58. o, Kiadó: Nature Publishing Group. (Hozzáférés: 2011. szeptember 1.)
- Huffman, Ken: My Uncle. Huffman Coding, 2010 (Hozzáférés: 2011)
- Haeberli, Paul: Geometric Paper Folding: Dr. David Huffman. GRAFICA Obscura, 1996 (Hozzáférés: 2011)
- Java-implementáció: GitHub:Glank
Kapcsolódó szócikkek
- Kódolás
- Számrendszerek az informatikában
- Bit
Informatikai portál • összefoglaló, színes tartalomajánló lap