Compactador e descompactador de texto

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

compactador/descompactador.cpp
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <stdio.h>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <time.h>
#include <conio.h>
#include "lebit.cpp"
using namespace std;
struct pnodo
{
 struct nodo *ptr;
};
const pnodo null = { 0 };
struct nodo
{
 char caractere;
 int frequencia;
 pnodo esq, dir, pai;
};
bool operator==(const pnodo &n1, const pnodo &n2)
{
	return n1.ptr->caractere == n2.ptr->caractere;
}
bool operator!=(const pnodo &n1, const pnodo &n2)
{
 return n1.ptr != n2.ptr;
}
bool operator>(const pnodo &n1, const pnodo &n2)
{
 return n1.ptr->frequencia > n2.ptr->frequencia;
}
pnodo gera_arvore(priority_queue<pnodo, deque<pnodo>, greater<pnodo> >& fila)
{
 pnodo e1, e2, aux;
 while(!fila.empty())
 {
 e1 = fila.top(); fila.pop();
 if(fila.empty()) break;
 e2 = fila.top(); fila.pop();
 aux.ptr = new nodo;
 (aux.ptr)->frequencia = (e1.ptr)->frequencia + (e2.ptr)->frequencia;
 (aux.ptr)->esq = e1; (aux.ptr)->dir = e2;
 (aux.ptr)->pai = null;
 (e1.ptr)->pai = aux; (e2.ptr)->pai = aux;
 (aux.ptr)->caractere = 0;
 fila.push(aux);
 }
 return e1;
}
int main ()
{
	pnodo raiz;
	FILE *ent, *sai;
	ent = fopen("teste_sai.bin", "rb");
	
	if (ent == NULL)
	{
		cout <<"Nao pude abrir o arquivo";
		exit(1);
	}
	
	sai = fopen("descompactado.txt", "w");
	if (sai == NULL)
	{
		cout <<"Nao pude criar o arquivo de saida.";
		exit(1);
	}
	
	int numPares;
	fread(&numPares, sizeof(int), 1, ent);
	cout << numPares << endl;
	
	priority_queue< pnodo, deque<pnodo>, greater<pnodo> > fila;
	char carac;
	int freq;
	pnodo aux;
	
	for (int x = 0; x < numPares; x++)
	{
		fread(&carac, sizeof(char), 1, ent);
		fread(&freq, sizeof(int), 1, ent);
		cout << carac << " " << freq << endl;
		aux.ptr = new nodo;
		aux.ptr -> caractere = carac;
		aux.ptr -> frequencia = freq;
		aux.ptr -> esq = null;
		aux.ptr -> dir = null;
		fila.push(aux);
	}
	raiz = gera_arvore(fila);
	int numbit;
	fread(&numbit, sizeof(int), 1, ent);
	cout << numbit << endl;
	pnodo aux1 = raiz;
	byte bit;
	
	for (int x = 0;x < numbit; x++)
	{
		//ler bit do arquivo de entrada
		bit = le_bit(ent);
		
		//escreve o bit
		cout<<(int)bit;
		if (bit == 1)
		{
			aux1 = aux1.ptr -> esq;
		}
		else
		{
			aux1 = aux1.ptr -> dir;
		}
		
		//escreve o caractere no arquivo
		if (!(aux1.ptr -> dir != null) && !(aux1.ptr -> esq != null))
		{
			fwrite(&(aux1.ptr->caractere), sizeof(char), 1, sai);
			aux1 = raiz;
		}
	}
	fcloseall();
	cout <<"\nFim da operaçao.";
	getch();
	
	//o texto descompactado so pode ser visto abrindo o arquivo descompactado.txt
}
compactador/descompactado.txt
compactador/teste.txt
abracadabra
compactador/teste_sai.bin
compactador/lebit.cpp
typedef unsigned char byte;
byte le_bit (FILE *f){
 static byte buffer; //Não perde o valor da variável após encerrar a função (static BUFFER)
 static int cont=0; //local com escopo global
 if(cont==0){
 fread(&buffer, sizeof(byte),1,f);
 cont=8;
 }
 byte res=(byte)(buffer<<(8-cont))>>7;
 --cont;
 return res; //simplificando: return (byte)(buffer<<(8-cont--))>>7;
}
compactador/principal.cpp
//
// Compactador Huffman
// Código desenvolvido pelo Prof. Marcos Vinícius da Silva
// baseado no livro "Algorithms in C++" de Robert Sedgewick
//
// Versão para Visual Studio
//
//Comente esta linha para gerar o código sem saída de depuração
#define DEBUG
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <stdio.h>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <conio.h>
#include <time.h>
static char nome_arquivo_entrada[]="teste.txt";
#ifndef DEBUG
using namespace std;
struct pnodo
{
 struct nodo *ptr;
};
const pnodo null = { 0 };
struct nodo
{
 char caractere;
 int frequencia;
 pnodo esq, dir, pai;
};
bool operator==(const pnodo &n1, const pnodo &n2)
{
	return n1.ptr->caractere == n2.ptr->caractere;
}
bool operator!=(const pnodo &n1, const pnodo &n2)
{
 return n1.ptr != n2.ptr;
}
bool operator>(const pnodo &n1, const pnodo &n2)
{
 return n1.ptr->frequencia > n2.ptr->frequencia;
}
list<pnodo> conta_frequencia(ifstream &f)
{
 list<pnodo> l;
 list<pnodo>::iterator pos;
 pnodo aux;
 aux.ptr = new nodo;
 f.get(aux.ptr->caractere);
 while(!f.eof())
 {
 aux.ptr->esq = aux.ptr->dir = null;
 pos = find(l.begin(), l.end(), aux);
 if(pos != l.end())
 {
 (*pos).ptr->frequencia++;
 delete aux.ptr;
 }
 else {
 aux.ptr->frequencia = 1;
 l.insert(l.end(), aux);
 }
	aux.ptr = new nodo;
 f.get(aux.ptr->caractere);
 }
 delete aux.ptr;
 return l;
}
void copia_lista(const list<pnodo>& lista,
 priority_queue<pnodo, deque<pnodo>, greater<pnodo> >& fila)
{
 list<pnodo>::const_iterator i;
 i = lista.begin();
 while(i != lista.end())
 {
 fila.push(*i);
 i++;
 }
}
pnodo gera_arvore(priority_queue<pnodo, deque<pnodo>, greater<pnodo> >& fila)
{
 pnodo e1, e2, aux;
 while(!fila.empty())
 {
 e1 = fila.top(); fila.pop();
 if(fila.empty()) break;
 e2 = fila.top(); fila.pop();
 aux.ptr = new nodo;
 (aux.ptr)->frequencia = (e1.ptr)->frequencia + (e2.ptr)->frequencia;
 (aux.ptr)->esq = e1; (aux.ptr)->dir = e2;
 (aux.ptr)->pai = null;
 (e1.ptr)->pai = aux; (e2.ptr)->pai = aux;
 (aux.ptr)->caractere = 0;
 fila.push(aux);
 }
 return e1;
}
void grava_frequencias(list<pnodo> &freqs, FILE *arq)
{
 list<pnodo>::iterator i = freqs.begin();
 while(i!=freqs.end())
 {
 char c = (*i).ptr->caractere;
 int f = (*i).ptr->frequencia;
 fwrite(&c, sizeof(char), 1, arq);
 fwrite(&f, sizeof(int), 1, arq);
 i++;
 }
}
void escreve_bit(FILE *f, unsigned char bit)
{
 static unsigned char valor=0, cont=1;
 if(cont < sizeof(char)*8)
 {
 valor = (unsigned char) (valor << 1) | bit;
 cont++;
 }
 else
 {
 valor = (unsigned char) (valor << 1) | bit;
 fwrite(&valor, sizeof(char), 1, f);
 cont=1; valor=0;
 }
}
list<unsigned char> obtem_codigo(char c, list<pnodo> &arv)
{
 list<pnodo>::iterator pos;
 list<unsigned char> bits;
 unsigned char bit;
 nodo aux;
 pnodo paux;
 aux.caractere = c;
 paux.ptr = &aux;
 pos = find (arv.begin(), arv.end(), paux);
 paux = *pos;
 bits.clear();
 while((paux.ptr->pai != null))
 {
 if(!(paux != paux.ptr->pai.ptr->esq))
 bit = 1;
 else
 bit = 0;
 bits.insert(bits.begin(), bit);
 paux = paux.ptr->pai;
 }
 return bits;
}
unsigned int codifica_arquivo(list<pnodo> &arv, ifstream &ent, FILE *sai)
{
 list<unsigned char> codigo;
 list<unsigned char>::iterator i;
 unsigned int contabits=0;
 char c;
 ent.close();
 ent.open(nome_arquivo_entrada);
 ent.get(c);
 while( ! ent.eof() ) {
 codigo = obtem_codigo(c, arv);
 i = codigo.begin();
 while(i != codigo.end()) {
 contabits++;
 escreve_bit(sai, *i++);
 }
	ent.get(c);
 }
 for(unsigned int i=0; i<8-(contabits%8); i++) { // completa o ultimo byte
 escreve_bit(sai, 0);
 }
 return contabits;
}
int main()
{
 list<pnodo> freqs;
 priority_queue< pnodo, deque<pnodo>, greater<pnodo> > fp;
 FILE *arq_sai;
 pnodo raiz;
 long tamanho1=0, bits=0;
 int num_nodos;
 clock_t ini, fim;
 ini = clock();
 ifstream arq_ent(nome_arquivo_entrada);
 if (! arq_ent.is_open() ) {
	 cout << "Não pude abrir o arquivo de entrada teste.txt";
	 getch();
	 exit(1);
 }
 arq_sai = fopen("teste_sai.bin", "wb");
 if (arq_sai == NULL) {
	 cout << "Não pude abrir o arquivo de saida teste_sai.bin";
	 getch();
	 exit(1);
 }
 freqs = conta_frequencia(arq_ent);
copia_lista(freqs, fp);
 raiz = gera_arvore(fp);
 num_nodos = freqs.size();
 fwrite(&num_nodos, sizeof(int), 1, arq_sai);
 grava_frequencias(freqs, arq_sai);
 tamanho1 = ftell(arq_sai);
 fwrite(&bits, sizeof(int), 1, arq_sai); // reserva espaço para o número de bits escritos
 bits = codifica_arquivo(freqs, arq_ent, arq_sai);
 fseek(arq_sai, tamanho1, SEEK_SET); // posiciona no local com o numero de bytes da codificacao
 fwrite(&bits, sizeof(int), 1, arq_sai); // grava o tamanho da codificacao (em bits)
 fcloseall();
 fim = clock();
 cout << "Tempo gasto: "<<(fim-ini)/CLOCKS_PER_SEC;
 getch();
 return 0;
}
#endif
//
//
//
#ifdef DEBUG
using namespace std;
struct pnodo
{
 struct nodo *ptr;
};
const pnodo null = { 0 };
struct nodo
{
 char caractere;
 int frequencia;
 pnodo esq, dir, pai;
};
bool operator==(const pnodo &n1, const pnodo &n2)
{
	return n1.ptr->caractere == n2.ptr->caractere;
}
bool operator!=(const pnodo &n1, const pnodo &n2)
{
 return n1.ptr != n2.ptr;
}
bool operator>(const pnodo &n1, const pnodo &n2)
{
 return n1.ptr->frequencia > n2.ptr->frequencia;
}
ostream& operator<<(ostream &o, const list<pnodo> &l)
{
 list<pnodo>::const_iterator i;
 i = l.begin();
 while(i != l.end())
 {
 o << (*i).ptr->caractere << " : " << (*i).ptr->frequencia << endl;
 i++;
 }
 return o;
}
ostream& operator<<(ostream &o, priority_queue<pnodo, deque<pnodo>, greater<pnodo> > pq)
{
 while(!pq.empty())
 {
 o << pq.top().ptr->caractere << "\t";
 pq.pop();
 }
 return o;
}
list<pnodo> conta_frequencia(ifstream &f)
{
 list<pnodo> l;
 list<pnodo>::iterator pos;
 pnodo aux;
 aux.ptr = new nodo;
 f.get(aux.ptr->caractere);
 while(!f.eof())
 {
 aux.ptr->esq = aux.ptr->dir = null;
 pos = find(l.begin(), l.end(), aux);
 if(pos != l.end())
 {
 (*pos).ptr->frequencia++;
 delete aux.ptr;
 }
 else {
 aux.ptr->frequencia = 1;
 l.insert(l.end(), aux);
 }
	aux.ptr = new nodo;
 f.get(aux.ptr->caractere);
 }
 delete aux.ptr;
 return l;
}
void copia_lista(const list<pnodo>& lista,
 priority_queue<pnodo, deque<pnodo>, greater<pnodo> >& fila)
{
 list<pnodo>::const_iterator i;
 i = lista.begin();
 while(i != lista.end())
 {
 fila.push(*i);
 i++;
 }
}
pnodo gera_arvore(priority_queue<pnodo, deque<pnodo>, greater<pnodo> >& fila)
{
 pnodo e1, e2, aux;
 while(!fila.empty())
 {
 e1 = fila.top(); fila.pop();
 if(fila.empty()) break;
 e2 = fila.top(); fila.pop();
 aux.ptr = new nodo;
 (aux.ptr)->frequencia = (e1.ptr)->frequencia + (e2.ptr)->frequencia;
 (aux.ptr)->esq = e1; (aux.ptr)->dir = e2;
 (aux.ptr)->pai = null;
 (e1.ptr)->pai = aux; (e2.ptr)->pai = aux;
 (aux.ptr)->caractere = 0;
 fila.push(aux);
 }
 return e1;
}
void imprime_arvore(pnodo r, int nivel)
{
 if(r.ptr)
 {
 imprime_arvore((r.ptr)->esq, nivel+1);
 for(int i=0; i<nivel; i++) cout << '\t'; // indentação
 if (!(r.ptr->esq != null) && !(r.ptr->dir!=null)) // escreve a raiz
 cout << (r.ptr)->caractere << endl;
 else
 cout << (r.ptr)->frequencia << endl;
 imprime_arvore((r.ptr)->dir, nivel+1);
 }
}
void grava_frequencias(list<pnodo> &freqs, FILE *arq)
{
 list<pnodo>::iterator i = freqs.begin();
 while(i!=freqs.end())
 {
 char c = (*i).ptr->caractere;
 int f = (*i).ptr->frequencia;
 fwrite(&c, sizeof(char), 1, arq);
 fwrite(&f, sizeof(int), 1, arq);
 i++;
 }
}
void escreve_bit(FILE *f, unsigned char bit)
{
 static unsigned char valor=0, cont=1;
 if(cont < sizeof(char)*8)
 {
 valor = (unsigned char) (valor << 1) | bit;
 cont++;
 }
 else
 {
 valor = (unsigned char) (valor << 1) | bit;
 fwrite(&valor, sizeof(char), 1, f);
 cont=1; valor=0;
 }
}
list<unsigned char> obtem_codigo(char c, list<pnodo> &arv)
{
 list<pnodo>::iterator pos;
 list<unsigned char> bits;
 unsigned char bit;
 nodo aux;
 pnodo paux;
 aux.caractere = c;
 paux.ptr = &aux;
 pos = find (arv.begin(), arv.end(), paux);
 paux = *pos;
 bits.clear();
 while((paux.ptr->pai != null))
 {
 if(!(paux != paux.ptr->pai.ptr->esq))
 bit = 1;
 else
 bit = 0;
 bits.insert(bits.begin(), bit);
 paux = paux.ptr->pai;
 }
 return bits;
}
unsigned int codifica_arquivo(list<pnodo> &arv, ifstream &ent, FILE *sai)
{
 list<unsigned char> codigo;
 list<unsigned char>::iterator i;
 unsigned int contabits=0;
 char c;
 ent.close();
 ent.open(nome_arquivo_entrada);
 ent.get(c);
 while( ! ent.eof() ) {
 codigo = obtem_codigo(c, arv);
 i = codigo.begin();
 cout << " ";
 while(i != codigo.end()) {
 contabits++;
 cout<<(int)*i;
 escreve_bit(sai, *i++);
 }
	ent.get(c);
 }
 for(unsigned int i=0; i<8-(contabits%8); i++) { // completa o ultimo byte
 escreve_bit(sai, 0);
 }
 return contabits;
}
int main()
{
 list<pnodo> freqs;
 priority_queue< pnodo, deque<pnodo>, greater<pnodo> > fp;
 FILE *arq_sai;
 pnodo raiz;
 long tamanho1=0, bits=0;
 int num_nodos;
 ifstream arq_ent(nome_arquivo_entrada);
 if (! arq_ent.is_open() ) {
	 cout << "Não pude abrir o arquivo de entrada teste.txt";
	 getch();
	 exit(1);
 }
 arq_sai = fopen("teste_sai.bin", "wb");
 if (arq_sai == NULL) {
	 cout << "Não pude abrir o arquivo de saida teste_sai.bin";
	 getch();
	 exit(1);
 }
 freqs = conta_frequencia(arq_ent);
 cout << freqs; //depuração
 copia_lista(freqs, fp);
 cout << endl << "Fila: \t" << fp << endl << endl; //depuração
 raiz = gera_arvore(fp);
 imprime_arvore(raiz, 0); //depuração
 num_nodos = freqs.size();
 fwrite(&num_nodos, sizeof(int), 1, arq_sai);
 grava_frequencias(freqs, arq_sai);
 tamanho1 = ftell(arq_sai);
 cout << "\nBytes do Código: "<<ftell(arq_sai); //depuração
 cout << endl; // debug
 fwrite(&bits, sizeof(int), 1, arq_sai); // reserva espaço para o número de bits escritos
 bits = codifica_arquivo(freqs, arq_ent, arq_sai);
 cout << "\nNúmero de Bits Codificados: " << bits << endl;
 cout << "\nTamanho total do arquivo compactado: "<<ftell(arq_sai)<<" bytes";
 fseek(arq_sai, tamanho1, SEEK_SET); // posiciona no local com o numero de bytes da codificacao
 fwrite(&bits, sizeof(int), 1, arq_sai); // grava o tamanho da codificacao (em bits)
 fcloseall();
 getch();
 return 0;
}
#endif