Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Codifica di Huffman
Forum - C/C++ - Codifica di Huffman

Avatar
-tonix (Normal User)
Newbie


Messaggi: 6
Iscritto: 13/05/2011

Segnala al moderatore
Postato alle 9:34
Lunedì, 23/01/2012
Salve a tutti, sto scrivendo un programma valido per l'esame di Algoritmi e Strutture Dati.

In pratica devo creare un codificatore e un decodificatore in grado di comprimere un file (nel mio caso file .txt) tramite la codifica di Huffman.

Sono riuscito a creare l'albero di Huffman correttamente, ma adesso non so come andare avanti.

Conosco la logica della codifica di Huffman, cioè che devo trovare nell'albero carattere per carattere, aggiungendo 0 se mi sposto a sinistra e 1 se mi sposto a destra ma ho dei dubbi.

Il file compresso in output sarà un file binario (.dat)? In questo file devo andarmi a salvare l'albero di Huffman e la stringa di bit validi per la decodifica? La stringa di bit in che tipo di variabile la vado a salvare?

Sono arrivato a questo punto e non so come proseguire.. Grazie per eventuali consigli.

Ultima modifica effettuata da -tonix il 23/01/2012 alle 9:36


Antonio
PM
Avatar
Il Totem (Admin)
Guru^2


Messaggi: 3635
Iscritto: 24/01/2006

Up
1
Down
V
Segnala al moderatore
Postato alle 10:49
Lunedì, 23/01/2012
Dipende da te. Non c'è un formato standard da rispettare...

Detto questo, non puoi evitare di salvare nel file di output l'albero stesso oppure le frequenze degli elementi del messaggio originale. Altrimenti non potresti più risalire ai valore necessari per la decodifica.
Per il salvataggio ti suggerirei di non calcolare preventivamente tutta la stringa di bit. Piuttosto prendi singolarmente ciascun simbolo in ingresso, lo codifichi e se avanzano dei bit per arrivare a 8, ne codifichi un altro. Quando hai accumulato almeno 8 bit, li traduci in un byte e lo scrivi sul file oppure (meglio) in un buffer. Quando il buffer è pieno, lo flushi sul file.

P.S.: io ho l'esame di algoritmi domani :rofl:

Ho capito.. Un'altra domanda.. Esiste un comando che mi blocca il processo delle chiamate ricorsive? Mi spiego meglio, - -tonix - 23/01/12 15:08
void preorder_ric (ELEMENTO *ptr, vector <int> &bit, int rad) //funzione di letura preorder ricorsiva { if(ptr!=NULL) { system("pause"); cout<<ptr->visualizza_char()<<" "<<ptr->visualizza_freq()<<" "<<endl; - -tonix - 23/01/12 15:09
Non me lo mostra tutto il codice.. Vabbè in poche parole mi servirebbe un comando che una volta arrivato alla lettera che sto cercando annulli il processo ricorsivo e restituisca in output quello che si è ricavato fino a quel momento - -tonix - 23/01/12 15:10
Usa return - Il Totem - 24/01/12 09:56


"Infelici sono quelli che hanno tanto cervello da vedere la loro stupidità."
(Fligende Blatter)

"Dubitare di se stessi è il primo segno d'intelligenza."
(Ugo Ojetti)
PM