Benvenuto!
Accedi
o
registrati
.
16-12-2019, 00:24:13
Home
CDL Informatica
UniCT
CEA
Prof
Help
Search
Calendar
Login
Register
Forum Informatica Unict
»
LAUREA TRIENNALE (D.M. 270/04)
»
II anno
»
Interazione e Multimedia, 9 CFU
(Moderator:
Filippo Stanco
) »
Problema con l'alberello di huffman
Pages: [
1
]
2
Go Down
« precedente
successivo »
Print
Author
Topic: Problema con l'alberello di huffman (Read 4131 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
peppe89ct
Apprendista Forumista
Offline
Gender:
Posts: 288
very normal people
Problema con l'alberello di huffman
«
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?
Logged
"Real programmers always confuse Halloween and Christmas 'cause 31oct = 25dec"
KingDavid
Forumista
Offline
Posts: 788
Alla fine [...] tutta la realtà è binaria.
Re:Problema con l'alberello di huffman
«
Reply #1 on:
10-11-2010, 08:07:55 »
Quote from: 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?
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
«
Last Edit: 13-11-2010, 12:58:42 by KingDavid
»
Logged
Basti pensare che un ipotetico quadrato di specchi, lungo 200 chilometri per ogni lato, potrebbe produrre tutta l'energia necessaria all'intero pianeta.
(Carlo Rubbia)
peppe89ct
Apprendista Forumista
Offline
Gender:
Posts: 288
very normal people
Re:Problema con l'alberello di huffman
«
Reply #2 on:
12-11-2010, 17:42:18 »
Anche a me risulta così... ma dalla soluzione del prof risulta in modo diverso.....
Logged
"Real programmers always confuse Halloween and Christmas 'cause 31oct = 25dec"
dani89
Apprendista Forumista
Offline
Posts: 254
Re:Problema con l'alberello di huffman
«
Reply #3 on:
12-11-2010, 18:31:41 »
forse la prima "L" va considerata maiuscola e quindi doversa dalla seconda "l" minuscola! prova così
Logged
KingDavid
Forumista
Offline
Posts: 788
Alla fine [...] tutta la realtà è binaria.
Re:Problema con l'alberello di huffman
«
Reply #4 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) è 2
5
(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.
«
Last Edit: 13-11-2010, 12:55:03 by KingDavid
»
Logged
Basti pensare che un ipotetico quadrato di specchi, lungo 200 chilometri per ogni lato, potrebbe produrre tutta l'energia necessaria all'intero pianeta.
(Carlo Rubbia)
Filippo Stanco
Moderator
Apprendista Forumista
Offline
Gender:
Posts: 369
Re:Problema con l'alberello di huffman
«
Reply #5 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.
Logged
Nova
Forumista
Offline
Gender:
Posts: 567
-.-"
Re:Problema con l'alberello di huffman
«
Reply #6 on:
26-01-2011, 18:10:17 »
Se abbiamo la stringa
Quote
San Valentino!
da codificare con Huffman voi come la codifichereste?
Logged
Ubuntu user:
#29872
Daréios89
Forumista Eroico
Offline
Gender:
Posts: 2.679
La musica è la forma d'arte suprema.
Re:Problema con l'alberello di huffman
«
Reply #7 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?
Logged
"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Nova
Forumista
Offline
Gender:
Posts: 567
-.-"
Re:Problema con l'alberello di huffman
«
Reply #8 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
«
Last Edit: 26-01-2011, 18:30:18 by Nova
»
Logged
Ubuntu user:
#29872
Daréios89
Forumista Eroico
Offline
Gender:
Posts: 2.679
La musica è la forma d'arte suprema.
Re:Problema con l'alberello di huffman
«
Reply #9 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..
Logged
"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
turì
Apprendista Forumista
Offline
Posts: 275
Re:Problema con l'alberello di huffman
«
Reply #10 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?
Logged
Daréios89
Forumista Eroico
Offline
Gender:
Posts: 2.679
La musica è la forma d'arte suprema.
Re:Problema con l'alberello di huffman
«
Reply #11 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)
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.
Logged
"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
turì
Apprendista Forumista
Offline
Posts: 275
Re:Problema con l'alberello di huffman
«
Reply #12 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
Logged
Daréios89
Forumista Eroico
Offline
Gender:
Posts: 2.679
La musica è la forma d'arte suprema.
Re:Problema con l'alberello di huffman
«
Reply #13 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......
Logged
"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
turì
Apprendista Forumista
Offline
Posts: 275
Re:Problema con l'alberello di huffman
«
Reply #14 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
Logged
Pages: [
1
]
2
Go Up
Print
« precedente
successivo »
Jump to:
Please select a destination:
-----------------------------
Area Ufficiale
-----------------------------
=> Annunci Ufficiali
=> Segreteria Didattica
=> Aiuto, proposte e commenti
=> Stages e progetti finali
=> C.O.F. Centro Orientamento e Formazione
=> Messaggi (d)agli amministratori del forum
-----------------------------
LAUREA TRIENNALE (D.M. 270/04)
-----------------------------
=> I anno
===> Architettura degli Elaboratori, 9 CFU
===> Elementi di Analisi Matematica, 12 CFU
===> Fondamenti di Informatica, 9 CFU
===> Matematica Discreta, 12 CFU
===> Programmazione 1, 9 CFU
===> Programmazione 2, 9 CFU
=> II anno
===> Algoritmi, 9 CFU
===> Basi di Dati, 9 CFU
===> Fisica, 9 CFU
===> Ingegneria del Software, 9 CFU
===> Inglese, 3 e 6 CFU
===> Interazione e Multimedia, 9 CFU
===> Sistemi Operativi, 9 CFU
=> III anno
===> Calcolo Numerico, 6 CFU
===> Formazione Numerica, 6 CFU
===> Introduzione all'Analisi dei Dati, 9 CFU
===> Metodi Matematici e Statistici, 6 CFU
===> Reti di Calcolatori, 9 CFU
===> Tecniche di Programmazione Concorrente e Distribuita, 9 CFU
===> Teoria dell'Informazione e Crittografia, 9 CFU
=> III anno - Materie a scelta (crediti liberi)
===> Computer Forensics, 6 CFU
===> Computer Graphics, 9 CFU
===> Digital Game Development, 6 CFU
===> GPGPU/CUDA, 6 CFU
===> Informatica Musicale, 6 CFU
===> LAP 1: programmazione C/C++ 6 CFU
===> LAP 2: Programmazione Android, 6 CFU
===> Sistemi Centrali, 6 CFU
===> Startup d'impresa e Modelli di Business, 6 CFU
===> Internet Security 9 CFU
===> Social Media Management, 6 CFU
=> Corsi disattivati - Vecchio curriculum
===> E-Commerce, 6 CFU
===> Legislazione Informatica, 6 CFU
===> Teoria della Computabilità, 9 CFU
-----------------------------
LAUREA MAGISTRALE
-----------------------------
=> I ANNO
===> Intelligenza Artificiale e Lab, 9 CFU
===> Algoritmi e Complessità, 9 CFU
===> Computer Vision, 9 CFU
===> Crittografia, 9 CFU
===> Fondamenti e Linguaggi per la Programmazione Distribuita
===> Inglese Scientifico, 3 CFU
===> Metodi analitici per l'informatica, 6 CFU
===> Metodi Matematici per l'Ottimizzazione (Corso Integrato), 12 CFU
===> Multimedia, 9 CFU
===> Sicurezza dei Sistemi Informatici 9 CFU
===> Computer Security, 9 CFU
=> II ANNO
===> Machine Learning 6 CFU
===> Teoria della Computabilità, 9 CFU
===> Analisi e Gestione dei Dati, 9 CFU
===> Compilatori, 9 CFU
===> Computazione Naturale e BioIspirata, 6 CFU
===> Introduzione alla Bioinformatica, 9 CFU
===> Linguaggi Formali e Applicazioni, 9 CFU
===> Logica Computazionale, 9 CFU
===> P2P & Wireless Networks, 9 CFU
===> Pattern Recognition, 9 CFU
===> Sistemi Distribuiti, 9 CFU
===> Sistemi dedicati e laboratorio, 9 CFU
===> Web Reasoning
=> Corsi disattivati - Vecchio curriculum
===> Fisica moderna per l'informatica, 6 CFU
===> Linguaggi di Programmazione, 9 CFU
===> Protocolli di Rete
===> Teoria dei Codici, 6 CFU
-----------------------------
Vecchi ordinamenti ad esaurimento
-----------------------------
=> Laurea Triennale (D.M. 509/00)
===> Algoritmi 1
===> Algoritmi 2
===> Basi Teoriche dell'Informatica
===> Economia Aziendale
===> Fisica 1, 6 CFU
===> Fisica 2, 6 CFU
===> Fisica 3
===> Formazione Analitica 1
===> Formazione Analitica 2
===> Formazione Discreta 1
===> Formazione Discreta 2
===> J2ME
===> Lab. Amministrazione di Sistemi
===> Laboratorio di Interazione
===> Modelli Matematici
===> Multimedia per Dispositivi Mobile
===> Progetto Software
===> Reti 1, 6 CFU
===> Sicurezza dei Sistemi Informatici 1
===> Sistemi Distribuiti 1
===> Teoria dei Grafi
===> Usabilità ed Estetica del Web
===> Web Programming
=> Laurea Specialistica (D.M. 509/00)
===> Algoritmi 3
===> Analisi Numerica
===> Complessità
===> Computabilità
===> Data analysis e management
===> Ingegneria del software 2
===> Linguaggi Formali
===> Metodi algoritmici per l'ottimizzazione combinatoria
===> Programmazione Funzionale
===> Reti di Calcolatori 2
===> Ricerca Operativa
===> Sistemi Distribuiti 2
-----------------------------
Dottorandi
-----------------------------
=> Wall
=> Events
-----------------------------
Area Studenti
-----------------------------
=> Agorà
=> L'angolo del tecnico
=> Il Mercatino degli studenti
=> Software
===> -vecchia catalogazione [sarà rimossa a breve]-
=====> Proprietario
=====> Free Software
=====> Open Source
===> Approfondimenti
===> News
===> Studio
===> Videogiochi
===> Networking e telecomunicazioni
===> Sviluppo
===> Ufficio e produttività
===> Sistemi Operativi
=====> Microsoft Windows
=====> GNU/Linux, Unix e BSD
=====> Mac OS X
=====> Windows Phone
=====> Android
=====> iOS
=====> Altri
===> Eventi, conferenze, concorsi
=> Microsoft Student Partner - Avvisi e informazioni
=> ERASMUS/borse di studio internazionali
Caricamento in corso...