Algoritmo di Huffman

[Unrue]

Salve ragazzi,
sto scrivendo un programma di compressione basato sull'algoritmo di huffman. Ho un dubbio pero': quale è il metodo migliore per reperire la lista dei simboli presenti in un file da comprimere? Da quella lista poi dovrei costruire l'albero di Huffman, assodiando un codice ad ogni simbolo, ma non so quale sia la via piu' breve. Grazie, ciao.

[Blackat]

Non esiste una via più breve!!!
Devi controllare byte per byte il file e fare una statistica dei caratteri che compaiono più frequentemente.

Ti consiglio di utilizzare un array di interi lunghi con 256 elementi per
contare la frequenza dei caratteri.
A ogni elemento dell'array corrisponde un carattere ascii.
Dunque ogni volta incrementi la posizione dell'array relativa a quel carattere.

Esempio
char c;
long stat[256];
....
while(!feof(FILE)) {
/* leggi il carattere c */
stat[c]++;
}
...
dove se c = 'A' memorizzi la presenza di una A.

Spero di essere stato chiaro.

Ciao Ciao.

[Unrue]

Grazie per la risposta, pero' ho un dubbio: quando apro il file, non viene letto in esadecimale? Quindi i confronti non dovrei farli analizzando il codice esadecimale? Che funzione usi per aprire ed analizzare il file? FOpen? Grazie mille.

[Blackat]

quando apro il file, non viene letto in esadecimale?

Dove sta il problema ?
Tu devi leggere carattere per carattere. Poi se è esadecimale ci penserà il C ( almeno non è il C che ci pensa ) a trasformarlo in decimale.

Quindi i confronti non dovrei farli analizzando il codice esadecimale?

Un carattere della tabella ASCII corrisponde ad un valore esadecimale che a sua volta corrisponde ad una valore decimale.
Esempio :

Carattere 'A' => Esadecimale 41 => Decimale 65
Carattere 'a' => Esadecimale 61 => Decimale 97

Quale funzione usi per aprire ed analizzare il file? FOpen? Grazie mille

Ti consiglio di utilizzare Fopen, FGetc e FClose.

Ciao Ciao

[Unrue]

Ok,capito, grazie mille. PS: se nel fare il programma avro' dubbi di qualsiasi genere potro' ricontattarti? Grazie ciao

[jappilas]

Se può servire, questo è un paragrafo delle mie dispense di Codifica di File:

Codice di Huffman
Il metodo di Huffman e basato sui due seguenti principi:

 Si considera una sorgente con un alfabeto di dimensione a. Combinando i due simboli meno probabili si ottiene una nuova sorgente di dimensione (a-1). Si suppongono note le parole di codice di questa sorgente ridotta e si nota che queste sono uguali alle parole di codice della sorgente originale per i simboli che non sono stati modificati. Così le parole di codice dei due simboli meno probabili si ottengono aggiungendo un uno o uno zero alla parola di codice della sorgente modificata corrispondente alla combinazione dei due simboli.
 Il codice di Huffman di soli due simboli consiste nelle parole di codice 0 ed 1

Per costruire il codice di Huffman per una data sorgente S basta combinare ripetutamente i simboli meno probabili in sorgenti ridotte fino a giungere alla sorgente con soli due simboli (il cui codice è noto). Aggiungendo 1 o 0 alle parole di codice ottenute per composizione si passa dalle sorgenti ridotte a quelle che l'hanno generate (che in generale saranno anch'esse ridotte ...) fino a giungere alla sorgente originale (ed alla sua codifica).

Esempio: sorgente con 5 simboli (H(s) = 2,15 bit/simbolo)

Simboli Probabilità Shannon Fano Huffman
s1 0,4 0 0
s2 0,2 10 100
s3 0,15 110 101
s4 0,15 1110 110
s5 0,1 1111 111
Lunghezza media 2,25 2,2

Huffman modificato
Spesso la maggioranza dei simboli in un ampio alfabeto ha piccole probabilità. Questi simboli potrebbero dunque occupare un quantitativo sproporzionato della memoria destinata alle parole di codice condurre ad un grande innalzamento della memoria necessaria per memorizzare le parole di codice essendo la lunghezza di queste inversamente proporzionale al loro contenuto informativo (cioè all’autoinformazione -log p(si).
Può dunque risultare vantaggioso non codificare proprio i simboli meno probabili e raggrupparli tutti in una entry "ELSE" della tabella di Huffman. Poiché un simbolo appartenente alla categoria ELSE ha in ogni caso bisogno di essere codificato, il codificatore trasmette una parola di codice per il simbolo ELSE, seguita da bit aggiuntivi necessari per identificare il messaggio in assenza della categoria ELSE. Se i simboli raggruppati in questa categoria hanno bassa probabilità, la perdita di efficienza del codice (dipendente dall'aumento di bit rate media) è molto piccolo a fronte di una decisa diminuzione della quantità di memoria richiesta e della complessità in decodifica.

Originariamente inviato da Blackat

Non esiste una via più breve!!!
Devi controllare byte per byte il file e fare una statistica dei caratteri che compaiono più frequentemente.
Ti consiglio di utilizzare un array di interi lunghi con 256 elementi per
contare la frequenza dei caratteri.
A ogni elemento dell'array corrisponde un carattere ascii.
Dunque ogni volta incrementi la posizione dell'array relativa a quel carattere.

questo in fase di costruzione del dizionario, prima di usarlo per generare il nuovo flusso di dati a partire dalla grammatica, e limitandosi al set ascii...
solitamente però, il dizionario non è limitato ai caratteri primari, ma include anche combinazioni di fino a n caratteri :
siccome quello che fai con huffman è usare un codice che ti crei delle assegnazioni le quali mappino un alfabeto di simboli su un altro, il massimo guadagno si ha convertendo , simboli di partenza più complessi e con la massima probabilità possibile, in simboli da pochi bit
soprattutto nei file di grandi dimensioni conviene, anche perchè il dizionario da aggiungere in testa acquista meno "peso" rispetto al codice generato
mentre tenere una symbol table compatta conviene per file piccoli e simboli equiprobabili, per i quali in casi estremi si rischia di andare a crescere invece che comprimere...

[cionci]

Originariamente inviato da Blackat

Non esiste una via più breve!!!

Dipende... Puoi realizzare una distribuzione statistica dei simboli ed iniziare da quella...poi man mano che si legge (e si converte) il simbolo si fa aumentare la frequenza di quel simbolo...
Certo si deve generare l'albero carattere per carattere (ad esempio si potrebbe scegliere di generarlo ogni N caratteri letti)...
In questo modo, posto che la tabella di partenza sia uguale sia per il compressore che per il decompressore, non serve nemmeno salvare la tabella delle frequenze nel file compresso...

Ovviamente con questo metodo decadrebbe la proprietà dell'algoritmo che dice che il risultato dell'algoritmo di Huffman è la rappresentazione ad entropia minima dell'ingresso...

[Blackat]

Il mio "non esiste una via più breve" era riferito alla domanda di Unrue "quale è il metodo migliore per reperire la lista dei simboli presenti in un file da comprimere?"

Tutto qua. Ovviamente devi per forza conoscere il contenuto del file per poter applicare qualsiasi algoritmo di compressione.

Poi l'algoritmo di huffman lo puoi applicare ai singoli caratteri o a sequenze di caratteri utilizzando alberi, tabelle di hash e qualsiasi altre strutture dati.

Ciao Ciao.

[cionci]

Originariamente inviato da Blackat

Il mio "non esiste una via più breve" era riferito alla domanda di Unrue "quale è il metodo migliore per reperire la lista dei simboli presenti in un file da comprimere?"

Appunto...facendo come ho scritto sopra si può generare la tabella delle frequenze a priori... Senza conoscere il contenuto del file...

[Unrue]

Originariamente inviato da jappilas

Se può servire, questo è un paragrafo delle mie dispense di Codifica di File

Grazie! Non è che potresti drmi il link completo delle tue dispense? Credo mi saranno molto utili. Ciao ciao

[jappilas]

Originariamente inviato da Unrue

Grazie! Non è che potresti drmi il link completo delle tue dispense? Credo mi saranno molto utili. Ciao ciao

si trattava della parte di compressione in funzione della trasmissione di immagini, quindi non c'è molto altro dopo quello che ho copiato, dopo huffman passa a
lempel-ziv-welch
codifica aritmetica
codifiche con perdita, predizione e quantizzazione (se stai pensando a jpeg hai indovinato )

si trova il file WORD zippato , ma ho notato un piccolo difetto:
nella prima pagina al posto della X va la formula dell' entropia della sorgente

H(s) = -Σ p(si) log(p(si)) , Σ = sommatoria , p(si) = probabilità del simbolo i-esimo

[Unrue]

Originariamente inviato da jappilas

si trattava della parte di compressione in funzione della trasmissione di immagini, quindi non c'è molto altro dopo quello che ho copiato, dopo huffman passa a
lempel-ziv-welch
codifica aritmetica
codifiche con perdita, predizione e quantizzazione (se stai pensando a jpeg hai indovinato )

si trova il file WORD zippato , ma ho notato un piccolo difetto:
nella prima pagina al posto della X va la formula dell' entropia della sorgente

H(s) = -Σ p(si) log(p(si)) , Σ = sommatoria , p(si) = probabilità del simbolo i-esimo

Grazie infinite, ciao ciao

[Unrue]

Salve ragazzi,
riguardo il programma, stavo dando un'occhiata ad una possibile implementazione di tale algoritmo ad un programma che si trova qui :

http://gameprog.it/hosted/puzzleryu/huflzw.html

Ad un certo punto, c'e' il seguente ciclo:

for (i = 0; i < n-1; i++) {
t1 = SearchTree(TreeArray,NULL,&p1);
t2 = SearchTree(TreeArray,t1,&p2);
// Unisci i due alberi
TreeArray[p1] = new TTree(0,t1->frequency+t2->frequency,t1,t2);
TreeArray[p2] = NULL;
}


Ora, t1 dovrebbe essere l'indirizzo nell'array TreeArray dell'albero riferito al simbolo con minore frequenza, t2 quello con frequenza subito successiva. Quindi p1 dovrebbe essere la posizione nell'array TreeArraydell'albero puntato da t1, analogamente p2 per t2. Ma non capisco una cosa: quando esegue l'istruzione TreeArray[p1] = new TTree(0,t1->frequency+t2->frequency,t1,t2);
crea un nuova albero nella posizione p1 di TreeArray, passa t1 e t2 al costruttore e poi cancella l'albero nella posizione p2. Lo scopo sarebbe quello di avere un'albero con la somma delle frequenze dei due ed un sottoalbero sinistro e destro. Ma facendo cosi, non si perdono i riferimenti ai sottoalberi? quello puntato da t1, viene sovrascritto facendo TreeArray[p1] = new TTree(0,t1->frequency+t2->frequency,t1,t2), mentre quello di t2 facendo TreeArray[p2] = NULL. A meno che, quando passa i puntatori t1 e t2 nell'istruzione TreeArray[p1] = new TTree(0,t1->frequency+t2->frequency,t1,t2);non ne faccia una copia da qualche parte.

[Unrue]

Originariamente inviato da Blackat

Ti consiglio di utilizzare Fopen, FGetc e FClose.

Ciao Ciao

Senti, un'altra domandina. Quando ho reperito tutti i simboli nel file, e costruito i relativi codici, devo prendre il file originale e sostituire ad ogni simbolo letto il suo codice corrispondente. Ma in che modo li trascrivo? Io ho sequenze di bit come codici, li trascrivo uno dietro l'altro tutti in fila? O secondo una logica ben precisa? E per scompattarlo?

[jappilas]

Originariamente inviato da Unrue

Senti, un'altra domandina. Quando ho reperito tutti i simboli nel file, e costruito i relativi codici, devo prendre il file originale e sostituire ad ogni simbolo letto il suo codice corrispondente. Ma in che modo li trascrivo? Io ho sequenze di bit come codici, li trascrivo uno dietro l'altro tutti in fila? O secondo una logica ben precisa? E per scompattarlo?

la corrispondenza temporale (ordinamento) dei simboli va preservata, in qualche modo, per cui...
inoltre devi curare molto bene progetto e implementazione della macchina a stati del ricostruttore: questo perchè in ogni istante lui non avrà nozione a priori su quanti bit comporranno il simbolo successivo
quello che rischi da un errato riesame dell' "albero" dei simboli è, nel caso migliore di sbagliare solo un simbolo, ma se si perde l' allineamento saranno sbagliati anche tutti i successivi, quindi dati praticamente erratici...

una cosa di cui avevo sentito era aggiungere dopo ogni simbolo o gruppo di simboli, una sequenza di bit univoca (cioè che sai non appartenere a nessun simbolo) per verificare la risincronizzazione
più avanti puoi aggiungere ulteriori bit di verifica di consistenza dei dati, tipo crc...

[Unrue]

Originariamente inviato da jappilas

la corrispondenza temporale (ordinamento) dei simboli va preservata, in qualche modo, per cui...
inoltre devi curare molto bene progetto e implementazione della macchina a stati del ricostruttore: questo perchè in ogni istante lui non avrà nozione a priori su quanti bit comporranno il simbolo successivo
quello che rischi da un errato riesame dell' "albero" dei simboli è, nel caso migliore di sbagliare solo un simbolo, ma se si perde l' allineamento saranno sbagliati anche tutti i successivi, quindi dati praticamente erratici...

una cosa di cui avevo sentito era aggiungere dopo ogni simbolo o gruppo di simboli, una sequenza di bit univoca (cioè che sai non appartenere a nessun simbolo) per verificare la risincronizzazione
più avanti puoi aggiungere ulteriori bit di verifica di consistenza dei dati, tipo crc...

Quindi il decompressore deve ricostruirsi l'albero di Huffman? Non capisco perchè pero'. Una volta che ho la tabella di conversione, perchè devo farlo? coiè , io pensavo che leggessi semplicemente ogni codicedal file compresso e cercassi la corrispondenza con il simbolo dalla tabella di conversione. Ma appunto sono due le cose che mi bloccano. La prima è che non so come fare a scrivere sul file che sarà quello compresso ogni singolo bit che compone i vari codici, la seconda, ben piu' importante è come faccio a mantere la struttura originaria del file. Non so la funzione fputc come scrive sul file, se tutti i caratteri uno dietro l'altro o in altro modo.

[cionci]

Originariamente inviato da Unrue

Quindi il decompressore deve ricostruirsi l'albero di Huffman? Non capisco perchè pero'. Una volta che ho la tabella di conversione, perchè devo farlo? coiè , io pensavo che leggessi semplicemente ogni codicedal file compresso e cercassi la corrispondenza con il simbolo dalla tabella di conversione.

Puoi anche salvare la corrispondenza dei carattere-codice, va bene...
In alternativa puoi salvare la sequenza delle frequenze... 256 interi...e poi ricostruirti l'albero...