Compresión de datos mediante algoritmo de Huffman.
Hace unos años hice como trabajo para la materia de informática II un programita en lenguaje c++ que comprime archivos mediante el algoritmo de huffman.
Para compartirlo, a modo de tutorial, lo dividí en dos partes:
- La explicación del algoritmo de Huffman.
- La implementación del algoritmo de Huffman en c++.
El programa no está optimizado para ejecutarse rápido, sino para que sea fácil de entender el concepto del algoritmo.
Para utilizarlo, una vez compilado, se debe arrastrar un archivo a comprimir y soltarlo sobre el ejecutable. Por ejemplo, si arrastramos uno de los archivos fuentes: "huffman.cpp" (8.702 bytes), se crea un nuevo archivo llamado "huffman.cpp.hfm" (6.191 bytes).
Si en cambio se arrastra y se suelta sobre el ejecutable un archivo con extensión ".hfm", el programa entiende que debe descomprimirlo. Por ejemplo arrastrando el archivo "huffman.cpp.hfm" sobre el ejecutable, éste vuelve a crear el archivo "huffman.cpp" original.
Aún no hay trackbacks.
Buscar en el sitio.
Buscar en la web.
Suscribirme a nuevos posts.
Categorías
- Economía (2)
- Filosofía (1)
- HP 50g (4)
- Ingeniería en Electrónica (1)
- Internet (5)
- LabView (20)
- Problemas y soluciones (10)
- Programación (7)
- Teología (2)
- Uncategorized (1)
Entradas recientes
- Nokia X3: WiFi dice “enlace no disponible” (Solución)
- Cómo migrar contactos de Nokia a Android (en Windows 7)
- Error 80070003 en Windows Update al tratar de instalar KB2539636 KB2533523 KB2468871
- Arreglé el aire acondicionado split
- Rayas verticales en el LCD de la Notebook
- Cartel de Texto Pasante en LabVIEW – Matriz de LEDs
- LabVIEW: InPort.vi y OutPort.vi en Windows Vista y Windows 7
- Consultas y trabajos en LabVIEW
- Huffman en c++.
- El algoritmo de huffman.
- Cambiar nivel crítico de bateria en Windows 7
- Método circuital o de las corrientes de mallas con matlab.
- Método nodal en matlab
- Función de Transferencia con Matlab
- HyperTerminal en Windows 7 o Windows Vista.
22 marzo, 2009 - 00:39
hola,
Andaba checando tu programa, y quisiera sber si puedo modificarlo, por ejemplo me piden que el “2″ sea un codigo constante,que le asgine 100.
Gracias.
22 marzo, 2009 - 04:31
Hola Jose, sí, modificalo a tu gusto y usalo. Saludos.
12 abril, 2009 - 19:17
Una consulta, hay una parte que no me queda clara. Como haces para guardar la frecuencia que tiene un caracter? (esto en el codigo de c). Podrias explicarmelo por favor? Te agradezco de antemano.
13 abril, 2009 - 03:15
Hola Alberto,
Respuesta corta: La frecuencia de los caracteres no se guarda en el archivo.
Respuesta larga: La frecuencia solo se usa para armar el árbol asignando códigos (caminos) mas cortos a los caracteres con mayor frecuencia y códigos (caminos) mas largos a los caracteres con menos frecuencia. Una vez que se armó el árbol (en memoria) ya no necesitamos conocer las frecuencias, pues los códigos (caminos) ya se asignaron correctamente.
En el archivo solamente se guarda la forma del arbol y las posiciones de cada caracter en el árbol, o dicho de otro modo, cual es el camino a cada caracter. Con esto le basta al descompresor para armar los códigos para cada caracter, que es lo que le interesa.
Pensá de esta forma: ¿Para qué guardé el árbol en el archivo, si al programa descompresor solo le interesa los códigos asignados a cada caracter? Podría haber guardado una tabla con cada caracter seguido por el tamaño de su código (ya que es viariable) y su código. O podría haber guardado la frecuencia de cada caracter para que el descompresor arme su propio arbol.
Pero lo hice así simplemente porque me pareció la opción más práctica y que ocuparía menos espacio. Simplemente guardé la estructura del árbol y la ubicación de cada caracter en él (no me importa saber la frecuencia).
Espero no haberte enredado más. Si no te queda claro algo decime. Saludos.
14 abril, 2009 - 20:26
Agradezco tu respuesta. Voy a revisarlo un poco mas a fondo para ver si logro comprenderlo mejor. Si no te molesta cualquier cosa te pregunto Vale?
15 abril, 2009 - 10:47
Cualquier cosa preguntame. Fijate que el código básicamente hace paso por paso lo que hay en la explicación del algoritmo en la página de la explicación.
26 abril, 2009 - 23:17
disculpa, no hay forma de saber cual es el nodo raiz del arbol creado
27 abril, 2009 - 15:29
Hola Angel.
Necesitaría que especificaras un poco más a que te referís para poder ayudarte. Saludos.
24 mayo, 2009 - 10:54
Hola Daniel, soy estudainte de informatica y para acabar para acabr la carrera tengo que hcer una practica de arboles de huffman en c++ con unos requisitos previos marcados por le profesor, por favor me podrias ayudar.
Gracias de antemano y espero ytu respuesta.
P.D; La tengo que tener hecha el 31 de mayo.
Gracias de nuevo y espero tu ayuda
24 mayo, 2009 - 17:05
Hola Maria Jose,
Escribime las dudas que tengas y te voy contestando lo que sepa.
Saludos.
26 mayo, 2009 - 16:15
Mira tengo que comprimri el primer capitulo del quijote con un fichero de fercuencias en binarioque ya me dan usando para implementar el arbol una cola de prioridad que se comporte como un minheap, la debo declarar: typedef arbin Tarbolh;
priority_queue<Tarbolh,vector,greater > cola;
Si quieres te mando a una direccion de correo lo que tengo y si puedes me lo ayudas en lo que puedas. Me va en ello la ultima asignatura de la carrera. Gracias de antemano
26 mayo, 2009 - 19:07
Veo que está muy interesante el proyecto, estoy tentado a decirte que me mandes las cosas pero tengo tan poco tiempo que se que no lo voy a poder ver (tengo que aprender a decir que no).
Lo que te puedo decir es que estuve viendo una implementación del algoritmo de huffman con priority_queue en este sitio (en inglés):
http://marknelson.us/1996/01/01/priority-queues/
Con eso tenés para empezar si manejás un poco de inglés.
27 mayo, 2009 - 16:05
Hola he mirado lo que me has dicho y ahor tengo un problema cuando recorro la coal pra generar el bosque y crear el arbol de huffman. TE copia qaqui lo que tengo y me puedes decir porque me da arbol vacio.
void ConstruirHuffman(fstream &frec,Tarbolh a){
Telem aux,aux1,aux2,aux3;
Tarbolh arbol,arbol1,arbol2,arbol3;
int i=0;
frec.read((char *) &(aux.caracter), sizeof(int));
frec.read((char *) &(aux.frecuencia), sizeof(float));
cola.push(aux);
while (!frec.eof()){
frec.read((char *) &(aux.caracter), sizeof(int));
cout<<(aux.caracter)<<endl;
frec.read((char *) &(aux.frecuencia), sizeof(float));
cout<<aux.frecuencia<<endl;
cout<<”Usado un para (int,float)”<<endl;
i++;
//////?????
// arbol.DatoRaiz()=aux;
// cola.push(arbol);
cola.push(aux);
}
cout<<”Las frecuencias leidas son”<< i;
cout<<”Pasado todo el fichero frecuencias a la cola con prioridad”<<endl;
//mostar(cola);
cout<<”Voy a mostar la cola copiandola par ver que la tengo”<<endl;
cola2=cola;
while(!cola2.empty())
{
//cout<<”Voy a mostar cola 2 “<<endl;
cout<<cola2.top().DatoRaiz().caracter<<”—-”;
cout<<cola2.top().DatoRaiz().frecuencia<<endl;
cola2.pop();
}
cout<<”Las frecuencias leidas son: “<< i<1)
{
cout<<”Entro en la cola para formar el arbol de huffman”<<endl;
arbol.Izquierdo()=cola.top();
// cout<<arbol.Izquierdo().caracter;
cout<<”Elemento de la cola 1″<<endl;
aux1=arbol.Izquierdo().DatoRaiz();
cout<< aux1;
cola.pop();
arbol2=cola.top();
cout<<”Elemento de la cola 2″<<endl;
aux2=arbol2.Derecho().DatoRaiz();
cout<< aux2;
cola.pop();
aux3.frecuencia=aux1.frecuencia+aux2.frecuencia;
aux3.caracter=aux1.caracter+aux2.caracter;
arbol3.DatoRaiz()=aux3;
cout<<”Elemento de la cola los uno”<<endl;
cout<< aux3;
cola.push(aux3);
}
};
Te añado el arbin.h
using namespace std;
template
class arbin {
public:
arbin();
arbin(const T & a, const arbin & arb_izq=arbin(),
const arbin & arb_der=arbin());
void Copiar(const arbin &origen);
arbin & Izquierdo();
const arbin & Izquierdo() const;
arbin & Derecho();
const arbin & Derecho() const;
const T & DatoRaiz() const;
T & DatoRaiz();
bool EsVacio() const;
void Vaciar();
bool EsHoja() const;
private:
class nodo {
public:
T info;
arbin izq;
arbin der;
nodo(const T & e=T(), const arbin &nizq=arbin(), const arbin &nder=arbin()):
info(e), izq(nizq), der(nder) { }
};
typedef nodo * nodoptr;
nodoptr raiz;
};
template
arbin::arbin() {
raiz = NULL;
}
template
arbin::arbin(const T & a, const arbin & arb_izq, const arbin &arb_der) {
raiz = new nodo(a, arb_izq, arb_der);
}
template
void
arbin::Copiar(const arbin &origen) {
if (origen.raiz != NULL) {
raiz = new nodo(origen.DatoRaiz());
raiz->izq.Copiar(origen.Izquierdo());
raiz->der.Copiar(origen.Derecho());
}
else raiz = NULL;
}
template
arbin & arbin::Izquierdo() {
if (raiz != NULL)
return raiz->izq;
else
cerr << “Error. Arbol vacio 1″ << endl;
}
template
const arbin & arbin::Izquierdo() const {
if (raiz != NULL)
return raiz->izq;
else
cerr << “Error. Arbol vacio 2″ << endl;
}
template
arbin & arbin::Derecho() {
if (raiz != NULL)
return raiz->der;
else
cerr << “Error. Arbol vacio 3″ << endl;
}
template
const arbin & arbin::Derecho() const {
if (raiz != NULL)
return raiz->der;
else
cerr << “Error. Arbol vacio 4″ << endl;
}
template
const T & arbin::DatoRaiz() const {
if (raiz != NULL)
return raiz->info;
else
cerr << “Error. Arbol vacio 5″ << endl;
}
template
T & arbin::DatoRaiz() {
if (raiz != NULL)
return raiz->info;
else
cerr << “Error. Arbol vacio 6″ << endl;
}
template
bool arbin::EsVacio() const {
return (raiz == NULL);
}
template
void arbin::Vaciar() {
if (raiz != NULL) {
raiz->izq.Vaciar();
raiz->der.Vaciar();
delete raiz;
}
}
template
bool arbin::EsHoja() const {
return ( !EsVacio() && Izquierdo().EsVacio() && Derecho().EsVacio() );
}
#endif
Gracias
30 mayo, 2009 - 05:30
Hola Daniel, perdona el comentario anterior, por favor me podrias revisar el siguinte codigo: En una funcion que dandole un arbol de huffman codifica un caracter te dice si lo ha encontrado y tambien la codificacion
void codifica(const Tarbolh &a,int c, bool &enc, string &cad){
Telem aux;
bool encon=false;
char letra; //para mostrar el contenido de la hoja
cad=”";// inicializo cad;
if (!a.EsVacio())// es vacio
{
// cout<<”No esta vacio”<<endl;
if(a.EsHoja())// es hoja Condicion de parada
{
// cout<<”Es hoja”<<endl;
// cout<<c; // caracter pedido a mostrar
// letra=a.DatoRaiz().caracter;
// cout<<letra; // caracter en la hoja
if(a.DatoRaiz().caracter==c)
{
// cout<<”Ck compracion de caracteres”<<endl;
enc=true;}
else enc=false;
}
else { // cout<<”No es hoja”<<endl;
codifica(a.Izquierdo(),c,enc,cad);
if(enc)
{
// cout<<”Voy por la izquierda”<<endl;
cad=’0′+cad;
// cout<<endl;
}
else{
//cout<<”Voy por la derecha”<<endl;
codifica(a.Derecho(),c,enc,cad);
if(enc) cad=’1′+cad;
}
}//fin no es hoja
cout<<”Muestro los 1 y 0 de la letra buscsda”;
cout<<c<”<<letra<”<<cad<<endl;
}// FIN DE VACIO
else // si esta vacio
{
cout <<” arbol vacio”;
enc=false;
}
//
};
Gracias pero llevo como 3 horas y no veo el error.
31 mayo, 2009 - 12:36
Hola Maria Jose,
Me da la impresión, por los “cout” que tenés comentados, que estás depurando simplemente de esa manera.
Si es así probá depurar con una herramienta como Visual C++, que podés descargar GRATIS de aquí:
http://www.microsoft.com/Express/vc/
Te pide que lo registres pero lo hacés de forma gratuita.
Voy a crear un post acerca de programación defensiva explicando algunas técnicas para luchar de manera sistemática contra los errores en la programación.
Cuando lo termine te pongo el link acá. Saludos.
31 mayo, 2009 - 15:28
Ahí puse un poco de programación defensiva para ayudar con los errores:
http://www.danielmunoz.com.ar/blog/2009/05/31/programacion-defensiva-en-c/
Eso te va a ayudar tanto en este como en otros programas.
Si te tomás tu tiempo al programar así, lo vas a recuperar a la hora de verificar errores.
1 junio, 2009 - 12:37
Gracias! GRoso! un abrazo!
25 junio, 2009 - 14:15
Hola yo estoy tomando Pascal en la facu. Si te paso un trabajo practico que me dieron para hacer me podes ayudar?
aunque no hagas todo haces una parte y yo despues lo termino
bueno gracias desde ya!!
25 junio, 2009 - 14:51
jaja
25 agosto, 2009 - 11:21
Hola quisiera saver que compilador (vercion) deveria usar para ejecutar este ejemplo. Desde ya muchas gracias
25 agosto, 2009 - 12:02
El ejemplo debería funcionar para cualquier compilador. Una sugerencia es el Visual C++ Express Edition, que es gratuito: http://www.microsoft.com/express/vc/
1 diciembre, 2009 - 23:15
Que tal. Estoy en la misma que alguien que escribió un mensaje más arriba. Me dieron un trabajo práctico en la facultad, un compresor basado en el algoritmo de Huffman, en Pascal. Tengo hechos todos los modulos y está completo, pero no funciona correctamente. Necesito alguien que me ayude a terminarlo nomas. Una mirada fresca.
Agradezco enormemente cualquier aporte, ya que tiene que funcionar para aprobar la materia.
Saludos.
2 diciembre, 2009 - 10:11
Hola Ezequiel. No programo en Pascal. Ojalá que algún lector te de una mano. Saludos.
22 febrero, 2010 - 02:05
Muchas gracias!, andaba buscando una explicacion para el algoritmo y un programa como el tuyo para usarlo de guia.
Me fue muy util
8 febrero, 2011 - 07:49
Hola!a mi tambien me han pedido un proyecto parecido y la verdad es que me ha encantado tu explicacion. Pero cuando intento acceder a la implementacion de tu codigo en c+++ me dice que no existe la pagina. ¿Me lo podrias mandar po email por favor?Me seria de muchisima utilidad
15 diciembre, 2011 - 22:16
jaja, la idea es que les sirva de guia para entender como funciona el sistema de codificacion de huffman y como se implementa, no para que el pobre daniel les haga los trabajos practicos de la facultad XDDD…..para recibirse pidiendo que les hagan los trabajos practicos….dios….que mal se nos viene el futuro de los egresados…(PD: que TP mas choto, solo eso pa recibirse xD)
me sirvio para aclarar algunas dudas tu texto danie, gracias ^^