Wikipédia

„Huffman-kódolás” változatai közötti eltérés

Laptörténet interaktív böngészése
[ellenőrzött változat][ellenőrzött változat]
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
a Informatikai portál AWB
Nincs szerkesztési összefoglaló
5. sor:
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: ''f<sub>1</sub> ≤ f<sub>2</sub>≤ ...≤ f<sub>n</sub>''.
* Ameddig a sorozat nem üres, végezzük el a következőket:
:* Amennyiben nem létezik az '' f<sub>1</sub> '' és '' f<sub>2</sub> '' címkéjű csúcs (egyike vagy mindkettő), hozzuk azt létre.
:* Hozzuk létre az '' f<sub>1</sub> + f<sub>2</sub> '' 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 '' f<sub>1</sub> '' és '' f<sub>2</sub> '' é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 '' f<sub>1</sub> ≤ f<sub>2</sub>≤ ... '' 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 <math>l_i</math>-vel jelöljük, akkor a Huffman-algoritmus által kapott fa esetében a <math>\sum_{i=1}^{n}l_if_i</math> ö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.
27. sor:
 
==Példa==
[[Fájl:Huffman 1.JPG|bélyegkép|jobbra|320px|Az ''a)'', ''b)'', ''c)'', ''d)'' ábrák]]
[[Fájl:Huffman 2.JPG|bélyegkép|jobbra|320px|Az ''e)'' ábra]]
Az a, l, m, f, t és a szóköz (jelölése: <math>\sqcup</math>) karaktereket szeretnénk kódolni a Huffman-algoritmussal, megadva ezek gyakoriságát az alábbiak szerint:
 
{| {{széptáblázat}}
52. sor:
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ó.
64. sor:
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.
101. sor:
|}
 
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:
 
{| {{széptáblázat}}
131. sor:
 
==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.
 
145. sor:
* [[Számrendszerek az informatikában]]
* [[Bit]]
 
{{Portál|Informatika|i }}
{{DEFAULTSORT:Huffmankodolas}}
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Huffman-kódolás”