Something went wrong. Try again.
Program that implements different compression methods: LZ-77, LZ-78, and LZW. Created during my student years.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269#include "lz78.h"#include "utils.h"
/** * Constructor. Inicializa las variables necesarias para la compresión * dinámica. */lz78::lz78(){
/** * Se inicializan los atributos de la clase: * * - Índice de compresión. * * - Índice de relación entre el mapa y el vector de la clase. * * - Cuenta del número de bits necesarios para codificar. * */ iComp=-1; iIndice=1; cuentaIndi=1;}
/** * Método para mostrar mensajes de error, y terminar la ejecución * del programa. * * \param[in] msg Mensaje de error para mostrar. */void lz78::error(string msg) { cerr << "[Error] "<< msg << endl; exit(-1);}
/** * Método que lee un byte del vBuffer. * * \param[out] c Byte leido. * \return True en caso de que se haya leido un byte correctamente, y false * false en caso contrario. */bool lz78::readChar(byte &c){ int n = static_cast<int>(vBuffer.size()); iComp++; if(n==0 || iComp >= n || iComp < 0) return false; c=vBuffer[iComp]; return true;}
/** * Convierte de un binario, representado por una cadena de caracteres 0 y 1, * a un entero, con la codificación correspondiente en binario real. * * \param[in] sSecuencia string * \return unsigned char */int lz78::bin2int(string sSecuencia) {
int nLongitud = static_cast<int>(sSecuencia.size()); int nSum = 0;
for (int i = 0; i < nLongitud; i++) { unsigned char c = sSecuencia[i]; int n = 0; if (c == '0') { n = 0; } else if (c == '1'){ n = 1; } nSum += static_cast<int>(n*pow(2.0, (static_cast<double>(nLongitud) - 1) - i)); }
return nSum;}
/** * Convierte de un unsigned int a un binario, representado por una * cadena de 0s y 1s, con la codificación correspondiente en binario real * de tamaño log(cuentaIndi)/log(2) (número de bits * necesarios para codificar el entero). * * \param[in] iData int * \return string */string lz78::int2bin(int iData) { string sBuffer; string sBufferFinal; int nbits = log(cuentaIndi)/log(2); nbits=((nbits/8)+1)*8;
if(iData==0){ for (int i = 0; i < nbits; i++ ) sBufferFinal.push_back('0'); return sBufferFinal; }
else{
for (int i = iData; i > 1; i/=2) { int nResto = i%2; if (nResto == 0) { sBuffer.push_back('0'); } else { sBuffer.push_back('1'); } } sBuffer.push_back('1'); int nLongitud = static_cast<int>(sBuffer.size()); for (int i = 0; i < (nbits - nLongitud); i++ ) sBufferFinal.push_back('0'); for(int i = nLongitud - 1; i >= 0; i-- ) sBufferFinal.push_back(sBuffer[i]); return sBufferFinal; }}
/** * Método que lee el fichero a comprimir, y además contruye el * diccionario inicial. * * \param[in] sFile Dirección donde se encuentra el fichero a comprimir. */void lz78::readFile(string sFile) {
ifstream file(sFile.c_str(), ifstream::binary); if (!file.is_open()) error (string("No se pudo abrir el archivo de origen: ") + sFile);
byte cCaracter; char buffer[1];
while (!file.read(buffer, 1).eof()) { cCaracter = static_cast<byte>(buffer[0]); vBuffer.push_back(cCaracter); }
file.close();
}
/** * Método que implementa el algoritmo de copresión. * * \param[in] sFile Dirección donde se dejará el fichero * comprimido. */void lz78::compress(string sFile){ byte c; list<byte> cadena; ofstream file(sFile.c_str(),ofstream::binary); if (!file.is_open()) error (string("No se pudo abrir el archivo de destino: ") + sFile); while((readChar(c))){ cadena.push_back(c); if(mTablaCod.find(cadena)==mTablaCod.end()){ mTablaCod[cadena]=iIndice; string indi; if(cadena.size()==1) indi = int2bin(0); else{ cadena.pop_back(); indi = int2bin(mTablaCod[cadena]); } int nbits=log(cuentaIndi)/log(2); nbits=((nbits/8)+1)*8; int tambuf=(nbits/8)+1; char *buffer = new char[tambuf]; for(int j=0, n=0; j < tambuf-1; j++, n+=8){ buffer[j]= bin2char(indi.substr(n,8)); } buffer[tambuf-1]=c; file.write(buffer,tambuf); iIndice++; cuentaIndi++; cadena.clear(); delete []buffer; } } file.close();}
/** * Método que lee el fichero con la información comprimida y * rellena la tabla con los elementos codificados en formato LZ78. * * \param[in] sFile Fichero con la informació comprimida. */void lz78::readCom(string sFile) {
ifstream file(sFile.c_str(), ifstream::binary); string indichar; int indi;
while (!file.eof()) { int nbits=log(cuentaIndi)/log(2); nbits=((nbits/8)+1)*8; int tambuf=(nbits/8)+1; char *buffer = new char[tambuf]; file.read(buffer, tambuf); //indi = static_cast<int>(buffer[0]); for(int i=0; i < nbits/8; i++){ byte cara=static_cast<byte>(buffer[i]); indichar.append(char2bin(cara)); } //cerr<<indichar<<endl; indi=bin2int(indichar); indichar.clear(); //cerr<<indi<<endl; vTablaCod.push_back(cod78(indi,buffer[tambuf-1])); cuentaIndi++; delete []buffer; }
file.close(); }
/** * Método que recupera una lista de bytes a partir del vector * donde está almacenada la informació codificada. * * \param[out] cadena Lista de bytes obtenidos. * \param[out] i Índice de acceso al vector de informació. */void lz78::obtainElem(list<byte> &cadena, int &i){ int indi = static_cast<int>(vTablaCod[i].first); if(indi==0){ cadena.push_back(vTablaCod[i].second); return; } else{ int nuevoindi= indi-1; obtainElem(cadena,nuevoindi); cadena.push_back(vTablaCod[i].second); return; }}
/** * Método que implementa el algoritmo de descopresión. * * \param[in] sFile Dirección donde se dejará el fichero * descomprimido. */void lz78::uncompress(string sFile){ list <byte> cadena; ofstream file(sFile.c_str(), ofstream::binary); int tamTabla = static_cast<int>(vTablaCod.size()); for(int i=0; i< tamTabla; i++){ obtainElem(cadena,i); for(list<byte>::iterator it = cadena.begin(); it!=cadena.end(); it++){ char buffer[1]; buffer[0]=static_cast<char>(*it); file.write(buffer,1); } cadena.clear(); }
file.close();}