Codifica di Huffman

[Downloader]

Stavo leggendo un attimo come eseguire la codifica di Huffman ma mi sono bloccato in un punto e non riesco ad andare avanti.



Praticamente io sommo la prima coppia di valori, il risultato della somma è 0.063 (e fin qui ok), poi dovrei effettuare la somme della altre coppie che hanno probabilità inferiore (quindi che hanno un valore inferiore a 0.063), ma non ce ne stanno! E poi la somma tra la coppia successiva non è inferiore a 0.063 ma quasi il doppio, quindi perchè fa la somma?


tnx!

[Robbi]

Ciao Scarrricatore!! !!
ma sei matto con ste formule !??

Qua ci vuole Dav o Manu!!
io ho gia' il mal di testa

Io al massimo ti posso dire alla Toto' che la somma non fa il totale!!

[BlackJack84]

Forse qui è spiegato un po' meglio, ma non mi chiedere di farti un riassunto

[Astro]

Originariamente inviato da Downloader
Stavo leggendo un attimo come eseguire la codifica di Huffman ma mi sono bloccato in un punto e non riesco ad andare avanti.



Praticamente io sommo la prima coppia di valori, il risultato della somma è 0.063 (e fin qui ok), poi dovrei effettuare la somme della altre coppie che hanno probabilità inferiore (quindi che hanno un valore inferiore a 0.063), ma non ce ne stanno! E poi la somma tra la coppia successiva non è inferiore a 0.063 ma quasi il doppio, quindi perchè fa la somma?


tnx!

Se ho capito la domanda e il codice quello che chiedi tu è molto semplice.


Tu trovi il 63 tramite somma dell'ultima coppia di numeri, poi trovi la somma della penultima somma di numeri che è 122.

Ora devi "abbassare" le altre cifre che sono più piccole della prima somma...

Infatti nella seconda colonna trovi il 62 e il 64...

Il 63 va posto tra il 62 e il 64, per ovvie ragioni...

Dopodiché si rifà la formula prima descritta e si arriva al risultato...



Spero di essermi spiegato...

[Downloader]

Il problema è che non riesco a collegare il grafico con la parte scritta.

[nikzeno]

Originariamente inviato da Downloader
cut

Praticamente io sommo la prima coppia di valori, il risultato della somma è 0.063 (e fin qui ok), poi dovrei effettuare la somme della altre coppie che hanno probabilità inferiore (quindi che hanno un valore inferiore a 0.063), ma non ce ne stanno!

Non importa il valore della somma, ma il valore delle probabilità prima di sommarle. Per cui 60 e 62 sono entrambe minori di 63, per cui li sommi e il risultato lo riporti nella seconda colonna.
C'è poi un altro 62, ma rimane spaiato, perchè non lo puoi sommare con il 64 che gli sta sopra in quanto 64 > 63. Quindi, come dice nel testo, se un valore non può essere accoppiato, lo riporti nella seconda colonna, ed eccolo lì infatti.

A questo punto, per far le cose fatte bene, potresti riportare anche tutti gli altri numeri nella seconda colonna in modo ordinato e ricominciare il procedimento.

Per cui sommi gli ultimi due, e fa 125, quindi puoi sommare anche quelli appena sopra, cioè 64 e 122 entrambi minori di 125. Riporti le somme ordinate nella terza colonna e via di nuovo...

[Dav82]

Esattamente (Y)

Ad ogni passaggio, con la prima somma dei due elementi con valore minore crei un bound, che determina gli elementi che possono essere "accoppiati" durante il passaggio stesso, ovvero quelli che hanno un valore inferiore a quel bound.
Accoppiati tutti gli elementi possibili, a due a due in ordine crescente di valore (frequenza, probabilità che dir si voglia), prosegui col passo successivo, prendendo in esame questa volta - assieme ai valori generati con le somme al passo precedente - anche tutti i valori che non sono stati accoppiati; considerandoli in ordine crescente ripeti la procedura.

Nel caso tuo, il bound del primo passaggio è, come ha spiegato benissimo nikzeno, 0.063, per cui non puoi sommare il secondo 0.062, perchè sarebbe da accoppiare con 0.064 che è oltre il bound; nel secondo passaggio il bound è 0.125 (0.062 + 0.063) per cui non puoi accoppiare 0.125 e 0.252, perchè prenderesti nodi oltre il bound; nel terzo passaggio il bound è 0.250 (0.125 + 0.125) e così via.


E mo?
Mo ottieni, sdraiato sulla destra e non all'impiedi e rovesciato come al solito, un albero binario: ogni nodo ha due figli, tranne i nodi foglia (i "rami" sono le frecce che indicano la somma di due nodi [valori] in un nodo [valore] nella colonna immediatamente sulla destra: i due nodi figli si sommano per formare il nodo padre).

Tu devi assegnare dei codici binari ad ogni simbolo (che è contenuto in un nodo foglia) e procedi così: parti dal nodo radice (quello più a destra, che non è disegnato, e che sarebbe il padre di 0.546 e 0.436) e, scorrendo l'albero verso le sue foglie, se prendi un ramo che va verso sinistra (in alto in questo caso, per il fatto che l'albero è sdraiato a destra) aggiungi uno 0, andando a destra (in basso in questo caso) aggiungi un 1; scorrendo l'albero di livello in livello aggiungi mano a mano dei bit al codice: quando arrivi a un nodo foglia ti fermi, e il codice che hai ottenuto è quello da assegnare al simbolo contenuto nel nodo foglia.


Mi verrebbe quasi da buttar giù un'implementazione in Java, ma so che poi mi perderei come un baluba dietro alla grafica e allora lascio perdere

[wilhelm]

Stanco adesso, molto stanco...


In ogni caso: a cosa serve?

[Dav82]

E' un algoritmo di codifica, che serve appunto per assegnare una codifica binaria (*) ad un gruppo di simboli.

Se si conosce (in via probabilistica, non con certezza: in questo secondo caso altre codifiche più semplici sono di buon valore) la frequenza relativa con cui i simboli appaiono nel documento (testo, immagine, quello che è) che si deve codificare, si può assegnare - mediante Huffman - la codifica più breve al simbolo che appare con frequenza maggiore e via via codifiche più lunghe a quelli che appaiono con frequenza minore: in questo modo si ottiene una codifica che, in media, è quella più breve (e quindi meno pesante da trasmettere e/o memorizzare) per il documento (o l'insieme di documenti) per il quale si è effettuato lo studio di frequenza.

Per esempio, nell'immagine di sopra, si vede che l'algoritmo assegna codifiche via via più lunghe scendendo verso il basso, e quindi diminuendo la frequenza dei simboli stessi.



(*) la codifica è priva di prefissi, ovvero la codifica assegnata ad un determinato simbolo non è l'inizio di una codifica assegnata ad un qualsiasi altro simbolo preso in esame: questa proprietà è ottenuta mediante l'algoritmo di assegnazione del codice binario di codifica dei simboli, che ad ogni biforcazione assegna uno "0" al ramo di sinistra e un "1" al ramo di destra, generando quindi per ogni simbolo una codifica basata sulle "scelte di direzione" prese ordinatamente a partire dal nodo radice: evidentemente una codifica di un simbolo non è l'inizio di un'altra, poichè altrimenti tale codifica, dovendo avere lo stesso "percorso iniziale" dell'altra, non sarebbe in un nodo foglia ma in un nodo interno, e quindi non sarebbe associata ad un simbolo.
Grazie a questa proprietà, i simboli codificati possono essere messi uno dopo l'altro senza bisogno di elementi separatori che facciano capire dove termina un simbolo codificato (e dove quindi inizia il successivo).
Per esempio con la codifica (0, 1, 01), se ricevi uno 0 non sai se hai ricevuto la prima codifica o se invece hai ricevuto la prima parte della terza codifica: questo perchè la prima codifica è inizio della terza; con un codice come (10, 11, 01, 001) questo problema non c'è



Tropp cumplicàa per l'una di notte, concordo