PDA

Visualizza la versione completa : [ALGORITMO] Huffman


menphisx
09-05-2008, 21:46
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
23-05-2008, 15:31
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
23-05-2008, 23:21
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
25-05-2008, 01:41
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 ...

:madai!?:

Baldolo
26-05-2008, 10:29
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
26-05-2008, 10:31
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
27-05-2008, 10:23
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.

Loading