Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Interazione e Multimedia, 9 CFU => Topic started by: peppe89ct on 09-11-2010, 18:35:20



Title: Problema con l'alberello di huffman
Post by: peppe89ct on 09-11-2010, 18:35:20
"La mamma lava" questo è il testo.......ho molti dubbi sull'albero della codifica...qulacuno che l'ha fatto?


Title: Re:Problema con l'alberello di huffman
Post by: KingDavid on 10-11-2010, 08:07:55
"La mamma lava" questo è il testo.......ho molti dubbi sull'albero della codifica...qulacuno che l'ha fatto?

la mamma lava

Frequenze:

f(l) = 2
f(_) = 2 (Nota: con _ denoto lo spazio)
f(a) = 5
f(m) = 3
f(v) = 1

Secondo l'algoritmo di Huffman, si prendono i "nodi" con frequenza minore e si fondono (v ed uno a scelta tra l ed _) scelgo l nel nostro caso

      vl(3)
     /      \
   v(1)  l(2)


Adesso hai:


f(vl) = 3
f(_) = 2
f(a) = 5
f(m) = 3

Ripeti l'algoritmo a questo nuovo insieme, quindi scegli _ ed uno a scelta tra m ed vl , scelgo vl
 
            vl_(5)
         /          \
      vl(3)       _(2)
     /      \
   v(1)  l(2)


Adesso hai:


f(vl_) = 5
f(a) = 5
f(m) = 3

Quindi:
                 vl_m( 8 )
               /            \
           vl_(5)       m(3)
         /          \
      vl(3)       _(2)
     /      \
   v(1)  l(2)

Adesso hai:


f(vl_m) = 8
f(a) = 5


Infine:
                         vl_ma(13)
                        /                \
                 vl_m( 8 )          a(5)
               /            \
           vl_(5)       m(3)
         /          \
      vl(3)       _(2)
     /      \
   v(1)  l(2)


Ora puoi assegnare i codici, se per convenzione assegni 0 ai rami di sinistra e 1 a quelli di destra avrai:
                        vl_ma(13)
                      /0               \1
                 vl_m( 8 )          a(5)
              /0            \1
           vl_(5)       m(3)
         /0         \1
      vl(3)       _(2)
     / 0    \1
   v(1)  l(2)


Quindi:
v = 0000
l = 0001
_ = 001
m = 01
a = 1


 :-ciao


Title: Re:Problema con l'alberello di huffman
Post by: peppe89ct on 12-11-2010, 17:42:18
Anche a me risulta così... ma dalla soluzione del prof risulta in modo diverso.....


Title: Re:Problema con l'alberello di huffman
Post by: dani89 on 12-11-2010, 18:31:41
forse la prima "L" va considerata maiuscola e quindi doversa dalla seconda "l" minuscola! prova così


Title: Re:Problema con l'alberello di huffman
Post by: KingDavid on 12-11-2010, 21:07:59
Il codice di Huffman, per un dato insieme di simboli, non è unico!! Infatti, come visto sopra, durante la costruzione dei codici molte scelte vengono determinate arbitrariamente.
In particolare il numero di alberi di huffman che si possono formare per l' insieme in questione (che è composto da 5 simboli) è 25 (cioè il numero di "etichette" differenti, in questo caso 0 e 1, elevato al numero di nodi interni).

Perchè ho detto tutto questo?

Perchè magari facendo qualche scelta diversa, durante il processo di costruzione dell'albero, otterrai lo stesso albero del prof.
Inoltre, anche se crei un albero differente, per capire se hai fatto bene puoi calcolare la lunghezza media del codice. Questa è come una prova del nove. Infatti i codici risultanti da alberi di huffman differenti, per lo stesso insieme, devono avere la stessa lunghezza media.

La lunghezza media del codice si calcola come la sommatoria delle frequenze dei simboli moltiplicate per la lunghezza del codice assegnato al simbolo.
Nell'albero che abbiamo costruito abbiamo:

f(v) = 1/13   =  0,08    e  lunghezza (v = 0000) = 4
f(l) = 2 /13   = 0,15   e   lunghezza ( l = 0001 ) = 4
f(_) =2/13    = 0,15  e  lunghezza (  _ = 001) =3
f(m) = 3/13   =0,23  e lunghezza (m = 01) = 2
f(a) = 5/13    = 0,39 e  lunghezza (a = 1) = 1

Quindi la lunghezza media del nostro codice è:
(0,08 * 4) + (0,15 * 4) + (0,15 * 3) + (0,23 * 2) + (0,39 * 1 ) = 2,22 (bit per simbolo)

Confrontala con quella del prof.


Title: Re:Problema con l'alberello di huffman
Post by: Filippo Stanco on 01-12-2010, 23:25:20
Non esiste solo un albero, ma se ne possono fare molti diversi.
Forse sono giusti pure quelli. Venite a ricevimento e ne parliamo.
Ovviamente la prima L è maiuscola e quindi è diversa dalla l minuscola.


Title: Re:Problema con l'alberello di huffman
Post by: Nova on 26-01-2011, 18:10:17
Se abbiamo la stringa 
Quote
San Valentino!
da codificare con Huffman voi come la codifichereste?


Title: Re:Problema con l'alberello di huffman
Post by: Daréios89 on 26-01-2011, 18:17:20
Anche per me è un problema...ma loro ad esempio nelle occorrenze hanno messo valori interi, non dovrebbero essere divisi per il numero di simboli?


Title: Re:Problema con l'alberello di huffman
Post by: Nova on 26-01-2011, 18:27:36
No, è corretto che la frequenza si calcoli come f = n° id volte che occorre il simbolo/ lunghezza della stringa (per intenderci).

Per il resto mi piacerebbe capire come codificare questa stringa e capire quanto valga il limite di shannon (N*E) per questa stringa dato che il log(1/14) (per esempio) è un numero negativo.

Ora probabilmente ho detto una boiata ma sono stanchissimo  .leggo


Title: Re:Problema con l'alberello di huffman
Post by: Daréios89 on 26-01-2011, 18:41:44
Il logaritmo varrà sempre un valore negativo, se ci fai caso infatti nella formula della sommatoria c' è un meno davanti proprio per questo motivo. Sto provando a fare la codifica, devo ricominciare perchè ho sbagliato.. :-)|


Title: Re:Problema con l'alberello di huffman
Post by: turì on 26-01-2011, 19:06:40
ho provato a fare la codifica di "A Natale si è buoni".

credo che l'albero sia giusto però il calcolo della verifica dei bit, il valore di N*E, mi viene enorme.

adesso non penso che per codificare una stringa ci vogliano più di 1000 bit, che è il risultato di N*E.

il numero di bit invece che conteggio per i caratteri è 72, quindi mi sembra che l'albero sia fatto bene.

o sto dicendo boiate? :boh


Title: Re:Problema con l'alberello di huffman
Post by: Daréios89 on 26-01-2011, 19:12:49
Non mi quadra.....il tuo risultato, io ho finito con la stringa di San Valentino(maledizione agli innamorati)  :-OK
Però il tuo calcolo non mi convince, tra gli appunti è spiegato che per ottenere una codifica ottimale bisogna avere un numero di bit PARI ALMENO al teorema di Shannon.
Quindi dovresti avere, se fosse corretto, alla fine un binario di 1000 bit per non perdere informazioni, deduco che ci sia qualcosa che non va, verifica il teorema e dimmi se ho sbagliato qualcosa.


Title: Re:Problema con l'alberello di huffman
Post by: turì on 26-01-2011, 19:17:12
si ma il fatto è: è possibile che servono N*E = 1000 bit circa(forse di più) per rappresentare questa semplice stringa?

significherebbe allora avere un albero enorme, almeno con ogni lettere codificata con più di 10 bit e oltre .penso


Title: Re:Problema con l'alberello di huffman
Post by: Daréios89 on 26-01-2011, 19:34:24
E' un pò strano.....proverei a codificarla, anche se il fatto di avere 78 caratteri alla fine mi spaventa......


Title: Re:Problema con l'alberello di huffman
Post by: turì on 26-01-2011, 19:40:07
ti posto i caratteri con i relativi bit

spazio 110
i 1111
A 1110
N 1011
t 1010
e 1000
l 1001
s 0111
è 0110
b 0101
u 0100
o 0010
n 0011

tutti i caratteri hanno frequenza 1, tranne lo spazio(4 volte), la a(2) e la i(2)

in totale sono 72 bit

poi quando calcolo N*E mi viene un valore enorme, più di 1000 bit .penso


Title: Re:Problema con l'alberello di huffman
Post by: Daréios89 on 26-01-2011, 19:45:53
Provoa farlo, se rimarrò sano di mente rispondo, altrimenti rimando a domani... :-)OLD


Title: Re:Problema con l'alberello di huffman
Post by: turì on 27-01-2011, 12:32:33
una cortesia qualcuno mi potrebbe postare la formula N*E, in particolare la E.

domanda: la N è il numero totale dei caratteri(quindi anche quelli ripetuti) dell'intera frase(es. "ciao mamma" sarebbe N=10?) oppure N è il numero dei caratteri senza ripetizione, quindi nell'esempio sarebbe N=6)

thanks


Title: Re:Problema con l'alberello di huffman
Post by: Daréios89 on 27-01-2011, 14:39:00
Per quanto riguarda N è il numero di caratteri totale, quindi contato anche i ripetuti, insomma la lunghezza della stringa per intenderci.
Per quanto riguarda E nelle slide trovi la formula, si definisce entropia di un segnale.
Supponendo di avere un segnale S definiamo l' entropia di S come:

E=-\sum f(i)\log_2(f(i)) per ogni i appartenente ad S. Se non ricordo male.
Quindi il teorema di Shannon vuole, attenendoci alla stringa inserita da te che fai:

10(.........................)

Cioè moltiplichi 10 per tutti gli elementi della sommatoria.


Title: Re:Problema con l'alberello di huffman
Post by: turì on 27-01-2011, 14:47:58
ho rivisto l'esercizio e mi sono reso conto che l'errore stava nel calcolo del logaritmo perchè io per calcolare il log in base 2 di f(i) nella formula del cambiamento di base usava la base e invece della base 10

usando la base 10 il risultato di N*E= 76 che è vicino a 72


Title: Re:Problema con l'alberello di huffman
Post by: turì on 27-01-2011, 15:10:14
ho ricontrollato tutto e adesso ci siamo:

il conteggio dei bit viene 70 mentre il valore di N*E viene 68,4 quindi direi che è tutto apposto.
la discrepanza sicuramente sta nelle approssimazioni

i feel happy :yoh


Title: Re:Problema con l'alberello di huffman
Post by: Nova on 27-01-2011, 15:15:32
Ma alla fine i simboli della stringa "San Valentino!"  come vengono codificati?

Se per esempio poniamo come primi due simboli lo spazio ed il ! essi avranno una decina di bit come codeword, esatto?


Title: Re:Problema con l'alberello di huffman
Post by: Daréios89 on 27-01-2011, 15:20:48
Voi avete fatto la prova in itinere? Non so se avete letto ma l' esame completo è stato posticipato al 16 febbraio.
Comunque per San valentino! se vuoi prendere come caratteri lo spazio e il punto escalamativo hanno frequenza 1, oppure 1/14 quindi avresti:


          _!(2)

        /          \

   _(1)          !(1)


Title: Re:Problema con l'alberello di huffman
Post by: turì on 27-01-2011, 15:21:23
aspetta che provo a codificarla


Title: Re:Problema con l'alberello di huffman
Post by: turì on 27-01-2011, 15:57:48
ho codificato la stringa "San Valentino!"

il numero di bit viene 47, N*E = 46

dovrebbe essere giusto?


Title: Re:Problema con l'alberello di huffman
Post by: Nova on 27-01-2011, 16:04:45
ma come fa ad essere 46 se un solo simbolo viene codificato da una decina di bit? Non capisco questo! Se hai fatto al codifica la posti compresa di albero per favore?


Title: Re:Problema con l'alberello di huffman
Post by: turì on 27-01-2011, 16:18:21
una decina di bit? .penso

molto strano

                                                      14
                                               /              \
                                             6                 8
                                            /  \             /    \
                                          n    3          4        4
                                               /  \        / \         / \
                                              !   a      2    2     2   2
                                                          /\    /\    /\   /\
                                                         S _  V l  e t  i o

a me viene cosi


Title: Re:Problema con l'alberello di huffman
Post by: Nova on 27-01-2011, 19:12:37
ah perfetto! mi veniva una decina di bit poiché nel mio albero le foglie all'ultimo livello sono solo due! Non sapevo di poter accoppiare i 4 simboli meno frequenti quando inizio a mettere su l'albero!