Papp Róbert
Huffman tömörítési mód
(Írta Papp Róbert <twisterrob@freemail.hu>, Paulik Rübert magyarázata alapján; 2005. 06. 11.)


Tegyük fel, hogy a kódolandó sztring PAPAMAMA.
1. Ebben megszámoljuk a karakterek számát:
	P: 2
	A: 4
	M: 2
2. Felírjuk a Huffman-fát (A kakaterek számának megfelelően csökkenő sorrendben):
	A   P       M
	4   2       2
	|   \_0___1_/ -- Összeadjuk a 2 legkisebb értéket
	4       4
	\_0___1_/     -- Ismét összeadjuk a 2 legkisebb értéket
	    8
3. Majd leolvassuk a biteket, alulról indulva a fában:
Ha balra megyünk, akkor 0 értéke következik a bitsorban, ha jobbra, akkor 1.

Tehát az első érték a 8-tól balra indulunk: csak az A érték található, tehát A=0

A második érték a 8-tól jobbra 1-gyel kezdődik, mert itt már elágazik a fa.
A 4-nél ismét megnézzük balra: itt már csak a P érték van, tehát a következő bit 0 -> így P=10
Visszamegyünk a 4-hez, és megnézzük jobbra is, itt csak M érték van, és mivel jobbra mentünk, ezért 1 a következő bit -> így M=11

4. Felírjuk az eredeti sztringet behelyettesítve az értékeket.
PAPAMAMA -> A=0, P=10, M=11
P  A P  A M  A M  A -> 8 karakter = 64 bit
10 0 10 0 11 0 11 0 -> 12 bit, tehát 12 / 64 = 5,3-szeres a tömörítés.
5. Visszafejtés (dekódolás)
Megvan a bináris sor: 100100110110 és a karakterek értékei: A=0, P=10, M=11

Megnézzük az 1. bitet: 1
        -> Van ilyen érték? nincs, tehát tovább nézzük
Hozzávesszük a 2. bitet: 0
        -> 10 -> Van ilyen érték? van P=10, tehát az 1. karakter P
Megnézzük a 3. bitet: 0
        -> Van ilyen érték? van A=0, tehát a következő karakter A
Megnézzük a 4. bitet: 1
        -> Van ilyen érték? nincs, tehát tovább nézzük
Hozzávesszük a 5. bitet: 0
        -> 10 -> Van ilyen érték? van P=10, tehát a következő karakter P
Megnézzük a 6. bitet: 0
        -> Van ilyen érték? van A=0, tehát a következő karakter A
Megnézzük a 7. bitet: 1
        -> Van ilyen érték? nincs, tehát tovább nézzük
Hozzávesszük a 8. bitet: 1
        -> 11 -> Van ilyen érték? van M=11, tehát a következő karakter M
Megnézzük a 9. bitet: 0
        -> Van ilyen érték? van A=0, tehát a következő karakter A
Megnézzük a 10. bitet: 1
        -> Van ilyen érték? nincs, tehát tovább nézzük
Hozzávesszük a 11. bitet: 1
        -> 11 -> Van ilyen érték? van M=11, tehát a következő karakter M
Megnézzük a 12. bitet: 0
        -> Van ilyen érték? van A=0, tehát a következő karakter A
És meg is van az eredeti karaktersorozatunk:
PAPAMAMA
:)
© All rights reserved by TWiStEr & PaulikR. Köszönöm -[PaulikR]-nek a segítséget!