Huffman-kódolás -- egy bemenetnek ugye valóban lehet több bitszinten eltérő, de egymással egyenértékű, helyes megoldása? Az egyes implementációk kimenetei miért térnek el (általában)?

A Huffman-kódolás ugye azon alapul, hogy a karakterekt/bájtokat gyakoriság szerint sorrendbe rakjuk, és ennek mentén bináris fát építünk belőle úgy, hogy lépésenként az első két elemet azok gyakoriságának összegével helyettesítve végezzük el a következő lépést.

Ha minden karakter gyakorisága eltérő, és minden lépésben olyan összeg keletkezik, ami nem szerepel a gyakoriság számsorába, akkor egyetlen megoldás lesz. De ha két elem, vagy részfa gyakorisága azonos, akkor a kialakuló sorrend erősen függ attól, hogy milyen rendezési, beszúrási algoritmust használunk. A kódolás egyik estben sem lesz hatékonyabb, vagy kevésbé hatékony, de más kódot fog adni.

Pl. legyen egy olyan adatunk, amiben csak három karaktert tartalmaz (mondjuk A, B és C), és ezek gyakorisága a következő:

A: 10 darab

B: 10 darab

C: 20 darab

Itt a kiinduló sorrend elve lehet az, hogy A,B,C és lehet az is, hogy B,A,C. Mindenképpen az A és a B kap egy közös gyökeret, de hogy melyik melyik oldalra kerül, az a rendezési algoritmustól is függ.

A második lépésben az A és B gyakoriságának összegét szúrjuk be, ami 10+10=20, itt a beszúró algoritmustól függ, hogy az a C gyakorisága elé vagy mögé kerül.

Tehát a következő fák alakulhatnak ki:

(A, B), C

(B, A), C

C, (A, B)

C, (B, A)

Így az A, B, C karaktereket kódja is eltérő lehet:

00, 01, 1

01, 00, 1

10, 11, 0

11, 10, 0

Látható, hogy a hatékonyság ugyanaz, hiszen A és B két bittel, C meg egy bittel van kódolva, mindegyik egy 60 bites kódot fog eredményezni.

"egy bemenetnek ugye valóban lehet több bitszinten eltérő, de egymással egyenértékű, helyes megoldása?"

Lehet, sőt, van is.

"Az egyes implementációk kimenetei miért térnek el (általában)?"

Ez több dologtól függhet. A fő ok az eltérő algoritmus, ami a kódfát építi fel. Lásd az előző hozzászólást. A másik ilyen ok: az adat-elemzésben van a különbség.

Találkoztam már olyan implementációval is, ami az adatok egy kisebb részét nem is tömörítette.