Pages: [1]   Go Down
Print
Author Topic: Huffman: "ottobre andiamo!"  (Read 2825 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« on: 05-02-2011, 16:44:18 »

Salve ragazzi,
stavo provando a fare il punto 3 dell'ultima domanda (http://www.dmi.unict.it/fstanco/lezioni_IEM_2007_2008/scritto_05102010.pdf), dove chiede di codificare con Huffman la stringa "ottobre andiamo!". La tabella dei simboli e delle frequenze mi viene
SimboloFreq.
O3
T2
B1
R1
E1
_1
A2
N1
D1
I1
M1
!1

L'albero di Huffman mi viene così:
http://localhostr.com/files/t9Pj8Me/albero.jpg

Per costruirlo ho usato il solito criterio, ossia quello di aggregare i simboli con minor frequenza.
All'inizio unisco tutti i nodi avente 1 come frequenza, ma poichè sono in numero dispari, mi resta il '!'.
Scelgo di unire il '!' con la 'A' formando un nodo da 3.
A questo punto unisco la T con un 2 formando un nodo da 4, unisco gli altri nodi da 2 e mi resta un nodo da tre, un nodo da due e la lettera O (che ha frequenza 3). Invece di unire i nodi da 2 e da 3 unisco il nodo da 2 con la O ottenendo sempre un nodo da 5 e così via.
Creando l'albero con un'applet (http://people.cis.ksu.edu/~rhowell/viewer/huffman.html) viene un albero diverso, dove la O (che è il carattere più frequente),  si trova più in alto e viene codificato con due soli bit.
Ho visto che la differenza col mio sta nel fatto che la lettera O non viene unita subito con un nodo da 2, ma piuttosto preferisce unire i nodi da 2 e da 3.

Con un'altro applet (http://huffman.ooz.ie/?text=OTTOBRE%20ANDIAMOK) viene un albero ancora diverso (addirittura alcuni simboli vengono codificati con 5 bit!).
Qual'è esattamente il criterio da seguire? Come avete costruito l'albero?

Grazie in anticipo
Logged
ilpuglio
Apprendista Forumista
**
Offline Offline

Posts: 300



« Reply #1 on: 05-02-2011, 16:50:43 »

Codifica di Huffman non ne esiste una sola ma dipende dalle scelte che fai. Come dice il professore in una soluzione (http://www.dmi.unict.it/fstanco/lezioni_IEM_2007_2008/scritto_120608_soluz.pdf)
"Una delle possibili codifiche è..."
Logged
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #2 on: 06-02-2011, 12:07:04 »

Ok ho capito, grazie!  ciao
Logged
turì
Apprendista Forumista
**
Offline Offline

Posts: 275



« Reply #3 on: 06-02-2011, 12:44:53 »

in effetti la codifica non è unica, in base a come vai a comporre i nodi ci possono essere differenze, cmq rimane il fatto che il numero di bit deve essere sempre lo stesso
Logged
SixArt
Matricola
*
Offline Offline

Gender: Male
Posts: 51



« Reply #4 on: 06-02-2011, 13:11:47 »

in effetti la codifica non è unica, in base a come vai a comporre i nodi ci possono essere differenze, cmq rimane il fatto che il numero di bit deve essere sempre lo stesso

ma non mi sembra che questo sia corretto, applicando la codifica di huffman alla stessa stringa io e altri 2 colleghi abbiamo ottenuto risultati diversi, anche questo può cambiare...
Logged
turì
Apprendista Forumista
**
Offline Offline

Posts: 275



« Reply #5 on: 06-02-2011, 13:19:31 »

davvero? ma è strano che usando la codifica huffman sulla stessa frase possa variare anche il numero di bit
Logged
Dario Z
Matricola
*
Offline Offline

Gender: Male
Posts: 22



« Reply #6 on: 06-02-2011, 13:33:48 »

  Infatti il numero di caratteri deve essere sempre lo stesso, la dimostrazione si trova su vari libri di algoritmi!
Logged

"Un giorno qualcuno mi batterà, ma non sarà oggi, e non sarai tu."
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #7 on: 06-02-2011, 13:39:35 »

Invece una cosa, io ho provato a codificare:
"Buone Feste a Tutti!".
Praticamente sono 20 caratteri, a ma nella codifica fatto l' albero, dalla somma delle frequenze, ottengo somma 19 nella radice. Commetterò qualche errore vero?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #8 on: 06-02-2011, 14:10:41 »

ma non mi sembra che questo sia corretto, applicando la codifica di huffman alla stessa stringa io e altri 2 colleghi abbiamo ottenuto risultati diversi, anche questo può cambiare...
davvero? ma è strano che usando la codifica huffman sulla stessa frase possa variare anche il numero di bit
Infatti il numero di caratteri deve essere sempre lo stesso, la dimostrazione si trova su vari libri di algoritmi!
in effetti la codifica non è unica, in base a come vai a comporre i nodi ci possono essere differenze, cmq rimane il fatto che il numero di bit deve essere sempre lo stesso

Ok, se prima credevo di aver capito, adesso sono confuso  testate
Ho fatto qualche errore secondo voi nel costruire il mio albero?
Logged
turì
Apprendista Forumista
**
Offline Offline

Posts: 275



« Reply #9 on: 06-02-2011, 14:35:21 »

Infatti il numero di caratteri deve essere sempre lo stesso, la dimostrazione si trova su vari libri di algoritmi!

appunto!

in effetti la codifica non è unica, in base a come vai a comporre i nodi ci possono essere differenze, cmq rimane il fatto che il numero di bit deve essere sempre lo stesso


ma non mi sembra che questo sia corretto, applicando la codifica di huffman alla stessa stringa io e altri 2 colleghi abbiamo ottenuto risultati diversi, anche questo può cambiare...

forse qualcuno ha commesso qualche errore? considera che io e un mio collega abbiamo usato huffman in maniera diversa, nel senso che abbiamo sommato i nodi in maniera uno differente all'altro ma il risultato cmq dava a entrambi lo stesso numero di bit
Logged
Dario Z
Matricola
*
Offline Offline

Gender: Male
Posts: 22



« Reply #10 on: 06-02-2011, 16:36:31 »

Qual'è esattamente il criterio da seguire? Come avete costruito l'albero?

Allora il criterio da seguire è quello che hai seguito tu! Qua parliamo di un algoritmo greedy che ci da sempre una soluzione ottima, una tra tante, ma tutte legate dal fatto di essere ottime! L' algoritmo di Huffman per codificare "OTTOBRE ANDIAMO!" consiglia 56 bit, a prescindere da come costruiamo l'albero! Possiamo scegliere di assegnare 0 al ramo destro ed 1 al sinistro, o viceversa! Quando abbiamo più di due nodi con frequenza minima uguale scegliamo quale coppia prendere! Queste scelte soggettive portano alla costruzione di alberi diversi, ma tutti questi saranno alberi che descrivono una codifica ottima, a lunghezza variabile e prefissa, in poche parole non influenzano il risultato che in effetti cerchiamo, cioè il numero di bit! 56 nel nostro caso.
« Last Edit: 06-02-2011, 17:02:47 by Dario Z » Logged

"Un giorno qualcuno mi batterà, ma non sarà oggi, e non sarai tu."
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #11 on: 06-02-2011, 16:51:00 »

Quindi il fatto che io abbia appena ottenuto 56 bit implicac he sia SCORRETTO oppure che è accetabile solo che non è il metodo più efficiente?
Mi correggo scusate, 54.
« Last Edit: 06-02-2011, 16:54:54 by Daréios » Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
turì
Apprendista Forumista
**
Offline Offline

Posts: 275



« Reply #12 on: 06-02-2011, 16:57:48 »

Quindi il fatto che io abbia appena ottenuto 56 bit implicac he sia SCORRETTO oppure che è accetabile solo che non è il metodo più efficiente?
Mi correggo scusate, 54.

beh N*E ti dà il valore ottimale per la codifica, se il numero di bit che è venuto fuori dalla tua codifica è di poco superiore significa che non hai scelto una codifica ottimale, ma non significa che questa sia errata.
Logged
Dario Z
Matricola
*
Offline Offline

Gender: Male
Posts: 22



« Reply #13 on: 06-02-2011, 17:02:27 »

Quindi il fatto che io abbia appena ottenuto 56 bit implicac he sia SCORRETTO oppure che è accetabile solo che non è il metodo più efficiente?
Mi correggo scusate, 54.

Diciamo che se due persone applicando l'algoritmo di Huffman danno risultati diversi, almeno una delle due ha sbagliato! Mi scuso io, ho contato male, sono 56! Correggo!
« Last Edit: 06-02-2011, 17:10:47 by Dario Z » Logged

"Un giorno qualcuno mi batterà, ma non sarà oggi, e non sarai tu."
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #14 on: 06-02-2011, 17:19:55 »

A me vengono 56, ho ricontato pure io 
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1]   Go Up
Print
Jump to: