Huffman-kódolás

A Wikipédiából, a szabad enciklopédiából

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ódoknál. 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[szerkesztés | forrásszöveg szerkesztése]

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 l_i-vel jelöljük, akkor a Huffman-algoritmus által kapott fa esetében a \sum_{i=1}^{n}l_if_i ö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[szerkesztés | forrásszöveg szerkesztése]

Az a), b), c), d) ábrák
Az e) ábra

Az a, l, m, f, t és a szóköz (jelölése: \sqcup) karaktereket szeretnénk kódolni a Huffman-algoritmussal, megadva ezek gyakoriságát az alábbiak szerint:

\sqcup a l m f t
20 40 7 10 8 15

A gyakoriságokat növekvő sorrendbe rendezve, a következő sorozatot 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, a kapott kódot igen, de a hatékonyságot nem).

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:

\sqcup 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:

\sqcup 111
a 0
f 1000
l 101
m 1001
t 110

Források[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]

Kapcsolódó szócikkek[szerkesztés | forrásszöveg szerkesztése]