C/C++ - Codifica di Huffman

Forum - C/C++ - Codifica di Huffman

-tonix (Normal User)
Newbie

Messaggi: 6
Iscritto: 13/05/2011

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

Il Totem (Admin)
Guru^2

Messaggi: 3635
Iscritto: 24/01/2006

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