Bináris fával esetleg más módon van megoldva ez a Huffman-algoritmus?

A Rosetta Code-n 60 nyelvben van megírva a Huffman-algoritmus:

[link]

#4 Olvasd el a világ számos pontjáról érkező véleményeket.

[link]

A kettes jót ír, valóban egyszerűbb a huffmann kódolás algoritmusát szöveges leírás alapján befogadni, mint forráskódból.

Ird le, hogy honnan nem érted és segítünk. Kezdjük innen:

A tömörítendő adathalmazon, ami jobbára byte-ok egydimenziós tömbje, végig kell lépkedni és megszámolni, hogy bizonyos értékű byte-okból mennyi van benne.

alma a fa alatt

Ez tartalmaz

a : 6

l : 2

m : 1

f : 1

t : 2

space : 3

A számítástechnikában léteznek adatszerkezetek.

Ezen belül léteznek un. speciális adatszerkezetek.

Ilyen pl a verem, a sor, stb.

Ezek jellemzője, hogy a bennük eltárolt adatok egy bizonyos struktúrában helyezkednek el. Ami nem jelent mást, mint hogy a bennük lévő adatokhoz nem férhetünk hozzá akárhogy.

Pl., ha a veremben eltároljuk egy szó vagy mondat kataktereit. Akkor azt fordított sorrendben vehetjük onnan ki.

ADAM-ból MADA lesz, 12,19,27,4,6-ból pedig 6,4,27,19,12.

Mire is jó ez? Hát pl arra, hogy bizonyos sorrendet, ha törik, ha szakad, erőlködés nélkül fenn tudjunk tartani.

Ha pl. a főprogramból meghívunk egy függvényt, akkor a függvény lefutása után hívás helyére kell visszatérnünk, igaz?

Hát erre jó a verem, mert a függvény meghívása előtt a verembe beteszem azt a memória-pozíciót, ahol éppen vagyok a programban (plusz egy) akkor a függvény lefutása után elég a veremből kiolvasnom, hogy hol kell folytatnom a programomat. Ez akkor még érdekesebb, ha a függvényből is meghívok még egy és még egy függvényt.

Mivel a veremből mindig a legutoljára oda betett értéket vehetem ki csak, így garantált, hogy mindig a megfelelő helyre tárek vissza.

Na, a bináris fa is hasonló, az adatok abban is valamilyen struktúra szerint foglalnak helyet.

Egy bináris fának van egy gyökere, ahonnan két irányba lehet tovább építkezni, jobbra és balra, aztán ezekből is jobbra és balra. Ezért bináris. Ha egy bináris fában eltárolunk adatokat, akkor a kiolvasás megad egy elkivánt struktúrát, ahogy a veremnél.

A -Lalalala- string bináris fában eltárolva kinézhetne úgy, hogy a gyökérben lenne az l betű, jobbra az a, balra pedig semmi.

Ez két karakter, igaz?

Na, ehhez a két karakterhez már csak a kiolvasás módját kell mellé bitsorozat formájában eltárolni és kész is van a tömörített kód.

Mi a kiolvasás módja?

Hát az, hogy elindulok a gyökértől, és leírom amit találok. Tovább lépek és ha 1-es a bit, akkor a-t írok le, ha 0 akkor meg z-t.

gyökér: l

jobb: a (1)

bal: nincs

Jobbra egyes, balra nulla. A lalalala string így az: 1,1,1,1 bitsorozattal eltárolható.

A kiolvasás úgy megy, hogy leírom a gyökérben talált karaktert, ez itt az l. kiolvasom a bitsorozat első bitjét, ami egyes, így a gykértől balra lépek el. Amit itt találok (a), azt leírom a már leírt l mellé. mivel a fa lefelé nem folytatódik tovább, így kilépek és ujra a gyökeret olvasom, ami megint csak l, leírom, majd ha egyes a bitsorozat következő tagja, akkor megint jobbra lépek el és az ott talált a betűt írom le és így tovább, amíg a bitsor végére nem érek. Nulla ugye nem lehet, mert nincs is bal részfánk.

A végén megkapom pontosan azt a karaktersorozatot, amit betömörítettem.

Egy karakter nyolc biten tárolódik el. A lalalala nyolc karakterből áll.

A lalalala esetében tehát nyolcszor nyolc, azaz hatvannégy bitet igényel az, hogy eltároljuk, tömörítetlen formában.

A tömörítésünkkel (ez a fa és mellé a bitsorozat)ezt a hosszot lecsökkentettük kétszer nyolc, plusz egy bit jelzőbitre (ez informál, hogy a gyökér (l) utáni elem (a) jobb vagy baloldali-e) plusz a bitsor, ami most itt, esetünkben még négy bit.

Ez összesen 21 bit, ami az eredeti 64 bit helyett egy remek kompressziós arány, mivel annak alig egyharmada.

Ez a leírás az elvet, az adatstruktúrák hasznosságának elvát próbálja meg megértetni veled.