codice:
#include "Intestazione.h"
void Huffman::set_nome(string x){
nome=x;
}
/* metodo lettura file: il metodo apre il file da comprimere e scrive il contenuto all'interno di un buffer. Infine, chiude il file. */
vector<char>Huffman::lettura_file(string x)
{
ifstream lettura;
lettura.open(x.c_str(),ifstream::in);
if(lettura.is_open())
cout<<"Il file e' stato aperto correttamente!"<<endl;
else{
cout<<"File inesistente!!"<<endl;
system("pause");
exit(1);
}
vector<char> buffer;
char carattere;
while(lettura.get(carattere)) // scrittura del contenuto del file nel buffer
buffer.push_back(carattere);
lettura.close(); // chiusura file
return buffer;
}
/* metodo costruisci_albero: questo metodo è utilizzato per creare l'albero di Huffman */
void Huffman::costruisci_albero(){
for(int j=0;j<256;j++) // ciclo for per inizilizzare il vettore con 0 in tutte le posizioni
occorrenze.push_back(0);
for(unsigned int i=0;i<input.size();i++) // conto le occorrenze dei caratteri nel file e li memorizzo in un vettore di occorrenze
occorrenze[static_cast<int> (input[i])]++;
vector <Nodo*> nodi;
for(unsigned int i=0;i<occorrenze.size();i++) //ciclo for per inserire le occorrenze nel vettore nodi
if(occorrenze[i]>0)
nodi.push_back(new Nodo(occorrenze[i],i));
Coda_priorita *coda = new Coda_priorita(nodi); // creazione coda di priorità con i nodi
while((coda->get_size())>1){
Nodo *nodo=new Nodo(); // creazione e allocazione nodo
Nodo *sinistro,*destro;
sinistro=coda->estrai_min();
destro=coda->estrai_min();
nodo->set_frequenza(sinistro->get_frequenza()+destro->get_frequenza());
nodo->set_sinistro(sinistro);
nodo->set_destro(destro);
coda->inserisci(nodo);
}
radice=coda->estrai_min();
}
/* metodo coding: il metodo scorre la coda dalla radice finchè non trova il carattere i-esimo passato come argomento.Se
il nodo attuale ha il figlio sinistro, scende a sinistra,inserisce 0 e richiama il metodo;se il nodo attuale ha il figlio destro scende
a destra,inserisce 1 e richiama il metodo. Quando viene trovato il carattere, la codifica viene inserita in un vettore */
void Huffman::coding(Nodo *n,char carattere,bool &test){
if(n->get_sinistro()!=0){ //se il nodo ha il figlio sinistro
v.push_back(0); //inserisce 0
coding(n->get_sinistro(),carattere,test); //richiamo metodo
}
if(test==false){
if(n->get_destro()!=0){ //se il nodo da il figlio destrp
v.push_back(1); // inserisce 1
coding(n->get_destro(),carattere,test); // richiamo metodo
}
}
if ((n->get_sinistro() && n->get_destro()) == 0) {
if(carattere == n->get_valore()){
test=true;
}
else {
v.pop_back();
return;
}
}
if (test==false){
v.pop_back();
return;
}
}
/* metodo compressione: a partire dal testo codificato crea un file .aa. Il metodo scrive le occorrenze dei caratteri nel file compresso,
successivamente estrae 8 elementi dal vettore, ciascuno dei quali rappresenta un bit, e li scrive in binario all'interno del file .aa.
Se nell'ultima iterazione ci sono meno di 8 elementi nel vettore, si inseriscono bit sporchi ('0') per completare la sequenza di 8.
Al termine scrivo quanti bit puliti ho nell'ultima iterazione.*/
void Huffman::compressione(){
ofstream scrittura;
string denominazione=nome;
denominazione.erase(denominazione.end() -4,denominazione.end());
denominazione=denominazione+".aa";
scrittura.open(denominazione.c_str(),ios::binary);
if(scrittura.is_open())
cout<<"Compressione........."<<endl;
for(unsigned int i=0;i<occorrenze.size();i++)
scrittura.write((const char*)&occorrenze[i],4);
int contatore=0;
int size1=v.size();
for(int i=0;i<size1;i++){
contatore++;
if(contatore==8){
contatore =0;
char carattere=0;
int j=7;
for(int i=0;i<=7;i++){
carattere+=pow(2,j--)*v[i];
}
scrittura.write(&carattere,sizeof(char));
v.erase(v.begin(),v.begin()+8);
}
}
if(contatore!=0){
while(v.size()<8){
v.push_back(0);
}
char carattere=0;
int j=7;
for(int i=0;i<=7;i++){
carattere+=pow(2,j--)*v[i];
}
scrittura.write(&carattere,sizeof(char));
}
scrittura.write((char*)&contatore,4);
scrittura.close();
cout<<"Codifica terminata!!"<<endl;
}
/* metodo tasso compressione: calcola in byte la differenza tra il file non compresso e il file compresso aprendo i due file, calcolando la lunghezza
e facendone la differenza */
void Huffman::tasso_compressione(){
ifstream noncompresso;
noncompresso.open(this->nome.c_str(),ifstream::in);
noncompresso.seekg(0,noncompresso.end);
int lunghezza1=noncompresso.tellg();
noncompresso.close();
ifstream compresso;
string denominazione=nome;
denominazione.erase(denominazione.end()-4,denominazione.end());
denominazione=denominazione+".aa";
compresso.open(denominazione.c_str(),ifstream::in);
compresso.seekg(0,compresso.end);
int lunghezza2=compresso.tellg();
cout<<"Tasso compressione:"<<100-((lunghezza2*100)/lunghezza1)<<"%"<<endl;
}
/* metodo che richiama i metodi necessari per la codifica */
void Huffman::codifica(string x){
this->nome=x;
input=lettura_file(nome);
costruisci_albero();
for(unsigned int i=0;i<input.size();i++){
bool test=false;
coding(radice,input[i],test);
}
compressione();
tasso_compressione();
}
/* metodo costruisci albero decompressione:ricostruisce l'albero prima della decompressione */
void Huffman::costruisci_albero_decompressione(){
vector<Nodo*>nodi;
for(unsigned int i=0;i<occorrenze.size();i++){
if(occorrenze[i]>0)
nodi.push_back(new Nodo(occorrenze[i],i));
}
Coda_priorita *coda= new Coda_priorita(nodi);
while((coda->get_size())>1){
Nodo *nodo=new Nodo();
Nodo *sinistro,*destro;
sinistro=coda->estrai_min();
destro=coda->estrai_min();
nodo->set_frequenza(sinistro->get_frequenza()+destro->get_frequenza());
nodo->set_sinistro(sinistro);
nodo->set_destro(destro);
coda->inserisci(nodo);
}
radice=coda->estrai_min();
}
/* metodo decompressione: legge il file compresso, conta le occorrenze e ricrea l'albero utilizzando il metodo costruisci_albero_decompressione.
Successivamente salva il numero di bit puliti , scritti nelle ultime 4 posizioni del file, in una variabile e inserisce in una stringa il contenuto di tutto
il file. Attraverso una stringa sequenza si esplora l'albero finchè non trova un carattere che andrà a salvare nel file deompresso */
void Huffman::decompressione(){
ofstream scrittura;
cout<<"Inserire il nome del file da decomprimere:"<<endl;
string testo;
cin>>testo;
testo.erase(testo.end()-3,testo.end());
string denominazione=testo+"dc.txt";
scrittura.open(denominazione.c_str());
if(scrittura.is_open())
cout<<"La creazione del file decompresso e' avvenuta con successo!!"<<endl;
ifstream lettura;
string denominazione2;
denominazione2=testo+".aa";
lettura.open(denominazione2.c_str(),ios::binary);
for(int i=0;i<256;i++)
occorrenze.push_back(0);
for(int j=0;j<256;j++)
lettura.read((char*)&occorrenze[j],4);
costruisci_albero_decompressione();
lettura.seekg(-4,lettura.end);
int bit_puliti;
lettura.read((char*)&bit_puliti,4);
lettura.seekg(0,lettura.beg);
string buffer((std::istreambuf_iterator<char>(lettura)),std::istreambuf_iterator<char>());
lettura.close();
int bit_sporchi=8-bit_puliti;
buffer.erase(buffer.begin(),buffer.begin()+1024);
string sequenza;
bitset<8>*bit;
for(unsigned int i=0;i<buffer.size()-4;i++){
bit=new bitset<8>(buffer[i]);
sequenza=sequenza+bit->to_string();
delete bit;
}
unsigned int i=0;
Nodo* nodo;
while(i<sequenza.size()-bit_sporchi){
nodo=radice;
while(!(nodo->get_sinistro()==0 && nodo->get_destro()==0)){
nodo=sequenza[i]=='0' ? nodo->get_sinistro() : nodo->get_destro();
i++;
}
char carattere=nodo->get_valore();
scrittura.write(&carattere,1);
}
scrittura.close();
}
Huffman::~Huffman(){
delete radice;
}
Rispondi quotando
