[ALGORITMO] Huffman

[menphisx]

Ho letto il funzionamento della codifica di Huffman e vari esempi, e lo capita; ora però non capisco come fare ad ottenere il messaggio originale dal codice codificato.
A esempio se ho un messaggio "I need help"; trovo la frequenza di ogni lettera:

e 3
I 1
L 1
n 1
d 1
h 1
p 1

poi costruisco l'albero:

              9
        /             \
       4             5
    /      \        /   \
   2      2      2   e
  / \     /  \    /  \
p   h     d  n   I   L

ottengo quindi il codice

e 00
I 011
L 010
n 100
d 001
h 110
p 111

quindi il messaggio sarà:

   I   n  e   e   d   h   e   l   p
011|100|000|000|001|110|000|010|111

fin qui tutto chiaro; ora come lo decodifico ? Come passo dal codice ottenuto al messaggio originale ?

[Baldolo]

Pensavo di essere l'unico pazzo ad occuparmi di codici ed algoritmi di Huffman ed invece scopro (con piacere) che siamo almeno in due!
Dunque, ci ho sbattuto violentemente e volutamente la testa tempo fa, occupandomi di decodifiche jpeg. Per ricostruire il codice dovresti percorrere l'albero binario in questo modo: inizi a leggere il file e ti sposti a dx o a sx del tuo albero (partendo dalla radice) fino a quando incontri un nodo (una lettera); a questo punto leggi il successivo bit e ricominci da capo percorrendo l'albero dalla radice verso i nodi (le lettere). Nel tuo caso, ti sposti a sx se nella sequenza in input leggi '1', a dx se leggi '0'.
Fammi sapere se non sono stato chiaro.

Ciao.

[menphisx]

No! Quello che hai detto lo capito e che non so' come ricostruire l'albero.
Se ottengo il codice:

011|100|000|000|001|110|000|010|111

e lo salvo su file; nel file non ho informazioni sufficienti per ricostruire l'albero.
Ho solo i percorsi (0 -> sx, 1 -> dx), ma non so a che simboli appartengono.

[menphisx]

Comunque credo di aver risolto; non ho ancora provato ...
Praticamente salvo nell'header una tabella dei simboli con le varie frequenze e poi ricostruico l'albero da lì ...
Però così facendo il guadagno nello spazio risparmiato è molto minore, ma comunque buono ...

[Baldolo]

Sì, ci sei arrivato da solo! Ti avrei infatti risposto praticamente la stessa cosa. L'algoritmo di Huffman è usato principalmente nel codec jpeg. Ora, in ogni file jpeg (dove viene sfruttata pesantemente la codifica di Huffman), viene memorizzato uno header per informazioni di carattere generale dell’immagine da codificare (dimensioni, formato, ecc.); ebbene, tra queste informazioni, c’è anche il nostro albero di Huffman, già scritto in un formato ottimizzato per risparmiare quanto più spazio possibile. Se non l’hai già fatto, senza che ti inventi niente di nuovo, ti invito a vedere il modo in cui viene salvato, perché è istruttivo e interessante. Se vuoi ti giro qualche link.

[menphisx]

Originariamente inviato da Baldolo
Sì, ci sei arrivato da solo! Ti avrei infatti risposto praticamente la stessa cosa. L'algoritmo di Huffman è usato principalmente nel codec jpeg. Ora, in ogni file jpeg (dove viene sfruttata pesantemente la codifica di Huffman), viene memorizzato uno header per informazioni di carattere generale dell’immagine da codificare (dimensioni, formato, ecc.); ebbene, tra queste informazioni, c’è anche il nostro albero di Huffman, già scritto in un formato ottimizzato per risparmiare quanto più spazio possibile. Se non l’hai già fatto, senza che ti inventi niente di nuovo, ti invito a vedere il modo in cui viene salvato, perché è istruttivo e interessante. Se vuoi ti giro qualche link.

posta pure.

[Baldolo]

Ecco quanto. La maggior parte delle informazioni l'ho trovata qui: http://www.impulseadventure.com/
La definizione della tabella di Huffman viene chiamata DHT (Define Huffman Table) e fa parte dello header del codec jpeg.