Nagyon koszonom a segitseget azoknak, akik leirtak nekem a Huffman lenyeget.
Egy kicsit _nagyon_ rossz vaganyon voltunk vele, de sajnos nem volt tobb
informacionk, ezert mi kellett kitalaljuk (ugy nez ki, mellefogtunk :). Most
mar remelem meg tudjuk irni.
Koszonom
Cemc

Sziasztok!

Hasznalt Delphi (4-hez) konyvet keresek megvetelre,
vagy ha valaki tudna az arat ujonnan, informaciokent 
erdekelne.
Gondolom jelent meg tankonyv!

Tisztelettel:
Teki

> programozonak. Arrol van szo, hogy egyik haveremmel irtunk egy csomagolo
 > programot, amely egyelore csak egy file-ra muxik. Egyik konyvben lattam
 > valami gyenge leirast a Huffman-algoritmusrol, es az alapjan akartuk megirni
 > a progit. Ez arrol szol, hogy statisztikat csinalunk a karakterekrol a
 > file-ban, majd bitcsoportokat rendelunk hozzuk. Pl.: KEREKES SZEKEREK MENNEK
 > 8 db E = 00 (ezek a bitek)
 > 5 db K = 01
 > a kov. = 10
 > a kov. pedig = 1100, es kezdodik elolrol. A ket egyes azt jelenti, hogy a
 > kov. hany bitet kell egyutt venni. Ez mind jo is, amig van kb. 20
 > karakterfajta egy file-ban. De azon felul mar igy nez ki:
 > 1 db. Z = 1111111100000000 
 
Hogy rendeled a csoportokat hozza ?

Az optimalis modszer a (amivel maximalis tomoritest lehet elerni) a
kovetkezo:

Megszamolod az osszes elofordulast. Sorba rendezed oket. A ket
legkisebb elofordulashoz hozzarendelesz 1 ill. 0-t. Osszeadod a a ket
elofordulast es egy elemkent beszurod a rendezett listara. Ezt
folytatod, es ezzel kapsz egy fat. Legyen a fenti mondat a pelda:

E = 8 
K = 5
  = 2	Ez a szokoz, '.' lesz a jele
R = 2
S = 2
N = 2
Z = 1
M = 1

Hozzarendelunk Z -hez 0-t M -hez 1 -et. Osszeadjuk oket, es vissza a
tablara.

Z:0 M:1

E = 8 
K = 5
 . = 2
R = 2
S = 2
N = 2
ZM = 2

N legyen most 0, ZM 1. Osszeadva 4, betesszuk:

N:0 Z:10 M:11

E = 8 
K = 5
NZM = 4
 . = 2
R = 2
S = 2

Ugyanez R es S-re:

R:0 S:1 N:0 Z:10 M:11

E = 8 
K = 5
NZM = 4
RS = 4
 . = 2

Majd:

 .:1 R:00 S:01 N:0 Z:10 M:11

E = 8 
 .RS = 6
K = 5
NZM = 4

Majd:

K:0 .:1 R:00 S:01 N:10 Z:110 M:111

KNZM = 9
E = 8 
 .RS = 6

Majd:

E:0 K:0 .:11 R:100 S:101 N:10 Z:110 M:111

E.RS = 14
KNZM = 9

Vegul:

E:00 K:10 .:011 R:0100 S:0101 N:110 Z:1110 M:1111

Bithossz szerint sorbarakva (zarojelben az elofordulasok szama)

(8) E 00
(5) K 10
(2)   011
(2) N 110
(2) R 0100
(2) S 0101
(1) Z 1110
(1) M 1111

A bithosszokat osszeszorozva az elofordulasokkal az jon ki, hogy a
szoveg bekodolva 2*8 + 5*2 + 2*3 + 2*3 + 2*4 + 2*4 + 1*4 + 1*4 = 62
bit. Mivel 8 fele karakter volt (a szokozzel egyutt), ezek normalisan
kodolhatoak lennenek 3 biten. A szoveg eredetileg 23 karakter hosszu,
azaz 23*3 = 69 bites (minimalisan). Ezek alapjan lathato, hogy a
tomoritest ertunk el, meg ha csak 7 bitnyit is. Termeszetesen, ha
az eredeti karakterek 8 bitet foglaltak el egyenkent, akkor a 
184 bitbol 62 mar egesz szep teljesitmeny.

A fenti modszerrel generalt bithozzarendelesekrol a kovetkezot lehet
allitani: 

- Egyertelmu, azaz egyik karakterhez rendelt bitminta sem kezdodik
  ugy, mint egy masik karakterhez rendelt rovidebb bitminta. Azaz, ha
  egy karakterhez a 010 lett rendelve, nincs egyetlen mas bitminta sem,
  ami 010-val kezdodik. Ennek folyomanya, hogy a dekodolas memoria-
  mentes es egy binaris faval abrazolhato, amelynek minden csomopontja 
  egy-egy olvasott bitnek felel meg (es a 0 vagy 1 hatasara balra vagy 
  jobbra megyunk), a leveleken pedig a dekodolt szimbolumok, azaz 
  karakterek allnak.

- Az ezzel a modszerrel bekodolt adatblokk maximalis entropiaval fog
  rendelkezni *az adott karakterhossz mellett*. Azaz, ha a tomorito
  eljaras ugy mukodik, hogy minden karakterhez egy konstans bitmintat 
  rendel, akkor ez a modszer *az adott karakterhossz mellett*
  optimalis tomoritest biztosit.
  
Ezen felul meg egy igen erdekes kerdes merul fel. A betomoritett
fileba termeszetesen bele kell tenni a kitomoriteshez szukseges
fat is. Namost ez elegge sok helyet tud elfoglalni, ha az ember 
naivan letarolja minden karakterhez a bitkepet es annak a hosszat.
Szerencsere a fa letarolhato ugy is, hogy minden csomopontjahoz
kiirunk 1 bitet plusz minden levelehez 1 bitet + annyit, amennyi a
level tartalmat (a karaktert) tarolni tudja (ennyi info egyebkent 
barmely binaris fa tomoritett tarolasahoz eleg).

Hozzatennem, hogy ez az algoritmus egy igen kokorszaki dolog es
gyakorlatban nem igazan hasznaljak file tomoritesre (bar teljesen
mas celbol igen jo hasznat lehet venni neha). 

Zoltan