elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Guía rápida para descarga de herramientas gratuitas de seguridad y desinfección


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Java
| | | |-+  [SRC] Compresor de Archivos Huffman
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [SRC] Compresor de Archivos Huffman  (Leído 12,002 veces)
Amerikano|Cls


Desconectado Desconectado

Mensajes: 789


[Beyond This Life]


Ver Perfil WWW
[SRC] Compresor de Archivos Huffman
« en: 11 Junio 2009, 05:21 am »

Hola a todos esta vez quiero compartir una de las tareas que nos han puesto este semstre en la universidad:

Se trata de implementar el algoritmo de compresion Huffman, para quien no sepa de que se trata, en este link se explica que es esto, pero para ahondar un poco les cuento que se trata primero de generar una lista enlazada con los bytes del archivo y sus frecuencias ordenada de menor a mayor y luego con esta se procede a formar un arbol binario de frecuencias donde los bytes que tengan mayor aparicion en el archivo o texto a comprimir (en este caso solo es para archivos y no tan largos :P) se encontraran a mayor altura.

Para generar la lista se parte del primer nodo (menor) y luego se formara otro nodo entre la suma de las frecuencias del nodo actual y el que se encuentra a su derecha, tomando como raiz el nodo que se a creado y que posee la frecuencia resultante de los 2 nodos. A la izquierda se situara el nodo menor y a la derecha el nodo mayor. Cabe decir que el nodo raiz formado con los 2 nodos anteriores hace parte todavia de la lista enlazada, es decir se ira trabajando con los resultados que se vayan obteniendo, y luego de esto el nodo resultante es puesto en la posicion que le consierna respetando el orden, asi:



Al finalizar el proceso el arbol para estas 3 letras "ABC" con sus respectivas frecuencias seria algo como esto:


Y con este arbol se procede a generar los codigos huffman, que son explicados en el link que puse ;).

Pues bien solo falta decir que la tabla de codigos huffman se le añade al archivo resultante sin tratarla en lo mas minimo, es decir primero se escribe el byte que representa la longitud de la tabla, y luego el byte de la letra con mas frecuencia seguido de su frecuencia y asi sucesivamente hasta la ultima. Tambien se le añadieron 3 o 4 bytes para coordinar el tamaño y extension del archivo original sin comprimir estos bytes, por lo cual, el que quiera ocuparse de insertar la tabla de codigos con el menor tamaño posible de bytes bienvenido sea :D.

Por ultimo debo decir que el programa no es util para archivos de gran tamaño, ya que como bien el algoritmo huffman es eficiente cuando se poseen frecuencias mayores de un mismo byte y hay gran diferencia entre las frecuencias de otros bytes, por eso no quiero que se enloquescan probandolo con archivos de mas de 1 Mb :D, sepan que es solo mostrar como funciona este algoritmo, por lo cual lo pueden probar con archivos de 100kb o algo así, que posea textos con caracteres repetitivos :D.

Lo que falto eso si fue invertirle mas tiempo a la GUI que esta muy tosca, a falta de una barra de prgreso y cosas asi :P.

El fuente trae su respectiva documentacion así como el diagrama de clases del mismo.


Link: http://www.mediafire.com/?dbfzqjzm4mz

Espero les sirva de algo el fuente ya cualquier duda no duden en comentarla :D.

Salu2

EDITADO


« Última modificación: 11 Junio 2009, 23:34 pm por AmeRiK@nO » En línea





Mi blog:
http://amerikanocls.blogspot.com
~~
Ex-Staff
*
Desconectado Desconectado

Mensajes: 2.981


Ver Perfil WWW
Re: [SRC] Compresor de Archivos Huffman
« Respuesta #1 en: 12 Junio 2009, 16:45 pm »

Muy útil AmeRiK@nO, quería implementarlo para probar su efectividad con imágenes bmp y bueno... no es muy útil (rebaja unos pocos kb, con png engorda xD), pero por lo menos no lo he implementado para nada, muchas gracias, le echaré un ojo al source ;)


En línea

MazarD
Colaborador
***
Desconectado Desconectado

Mensajes: 885


mazard.info


Ver Perfil WWW
Re: [SRC] Compresor de Archivos Huffman
« Respuesta #2 en: 12 Junio 2009, 22:49 pm »

Muy interesante, gracias AmeRiK@nO.

Algunos detalles tontos que creo podrías mejorar del código hechandole un vistazo rápido:

-La función bin2dec no es necesaria, puedes usar Integer.parseInt(cadena,base); que para tu caso sería base 2.
-En getExtension podrías hacer return ruta.substring(lastIndexOf('.')); que quizás sería más cómodo y rápido.
-Usar BufferedInputStream y BufferedOutputStream te darían algo de velocidad, que en algoritmos de compresión siempre se agradece.
-Es otra tonteria pero en la clase nodo si defines getters y setters usalos también en la propia clase así solo sería necesario cambiar el código en un sitio, y otra es que una de dos, o privadas con -getters y setters o publicas sin ellos.
-En todo tu código usando StringBuffer creo que se podría notar bastante en un benchmarking.
-Para la función reverse java te dá StringBuffer.reverse() aunque la recursiva que has montado es muy curiosa no lo había visto nunca y no se me habría ocurrido.

Por lo demás lo que es en realidad el motor sin tener en cuenta estas tonterias me parece genial y muy interesante, voy a tener que mirarlo con más calma.

Gracias!!
Saludos!!




En línea

-Learn as if you were to live forever, live as if you were to die tomorrow-

http://www.mazard.info
http://twitter.com/MazarD
irc://irc.freenode.org/elhacker.net
Amerikano|Cls


Desconectado Desconectado

Mensajes: 789


[Beyond This Life]


Ver Perfil WWW
Re: [SRC] Compresor de Archivos Huffman
« Respuesta #3 en: 14 Junio 2009, 00:10 am »

Si tienes razon MazarD, el problema era que en clase nos exigian utilizar en lo minimo metodos ya echos en java, con el fin de practicar todo, lógica, manejo de cadenas, etc  :xD. Gracias por echarle un ojo al source  ;).

salu2
En línea





Mi blog:
http://amerikanocls.blogspot.com
vVegeta

Desconectado Desconectado

Mensajes: 4



Ver Perfil WWW
Re: [SRC] Compresor de Archivos Huffman
« Respuesta #4 en: 14 Junio 2009, 06:08 am »

Hola que tal ?!?!...

De primera instancia, felicitarte por el código... ;-)...

Segundo, no crees que sería mucho mejor y más ordenado utilizar algún Layout para triangular mejor la aplicación ?...

Algunas mejoras, bueno más que todo para el usuario final, sería la de tener el opCompress, ya seleccionado ?... o no permitir escribir el texto, tanto en el rutaOrigen, como en rutaDestino...

Enviar mensajes más explicativos, si se valida que todo esté en orden... pero no muy explicativo...

Más que todo eso...

Saludos cordiales...
vVegeta
En línea

SOLO LOS QUE DEJAN DE INTENTAR, FRACASARÁN...

Si no fuera por C, existiría Obol, Pasal, ++, #...

WinJaNet, abre sus puertas, para todos los programadores e interesados en programación!!


Amerikano|Cls


Desconectado Desconectado

Mensajes: 789


[Beyond This Life]


Ver Perfil WWW
Re: [SRC] Compresor de Archivos Huffman
« Respuesta #5 en: 14 Junio 2009, 06:23 am »

Tienes razon, la verdad yo no me preocupo tanto por las interfaces, de echo me quedan horribles, como muestra de un boton esta  ;D, pero si tendre en cuenta tus consejos. Gracias por fijarte en ello  :)

salu2
En línea





Mi blog:
http://amerikanocls.blogspot.com
juancho77


Desconectado Desconectado

Mensajes: 455


rie con demencia


Ver Perfil
Re: [SRC] Compresor de Archivos Huffman
« Respuesta #6 en: 24 Junio 2009, 17:40 pm »

Justo estamos viendo lo mismo pero con Strings (un poco mas basico ja). Despues lo miro y te cuento
En línea

Amerikano|Cls


Desconectado Desconectado

Mensajes: 789


[Beyond This Life]


Ver Perfil WWW
Re: [SRC] Compresor de Archivos Huffman
« Respuesta #7 en: 24 Junio 2009, 18:39 pm »

Te refieres a tratar todo con Strings?
En línea





Mi blog:
http://amerikanocls.blogspot.com
juancho77


Desconectado Desconectado

Mensajes: 455


rie con demencia


Ver Perfil
Re: [SRC] Compresor de Archivos Huffman
« Respuesta #8 en: 26 Junio 2009, 20:01 pm »

Nono, no me referia al compresor sino al algoritmo. A partir de un texto, codificarlo utilizando Huffman, de modo que los codigos obtenidos sean optimos en relacion a la frecuencia. Y te queda, si la "a" tiene frecuencia 1000, a=01, y si la "b" tiene frecuencia 2, b=00010111, por ejemplo.
Despues lo implemento y lo muestro.
En línea

Amerikano|Cls


Desconectado Desconectado

Mensajes: 789


[Beyond This Life]


Ver Perfil WWW
Re: [SRC] Compresor de Archivos Huffman
« Respuesta #9 en: 26 Junio 2009, 23:08 pm »

Ok, entonces lo esperamos  ;D
En línea





Mi blog:
http://amerikanocls.blogspot.com
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
PeaZip 3.6.2: compresor y descompresor de archivos gratuito
Noticias
wolfbcn 0 1,076 Último mensaje 28 Febrero 2011, 18:13 pm
por wolfbcn
Codigos de huffman
Programación C/C++
spyller 0 857 Último mensaje 8 Junio 2012, 06:28 am
por spyller
cifrando con huffman - duda
Hacking Ético
ryan parker 0 1,445 Último mensaje 9 Julio 2012, 01:55 am
por ryan parker
compresor/descompresor de archivos
Programación C/C++
m@o_614 8 2,723 Último mensaje 7 Octubre 2013, 19:32 pm
por rir3760
CompactGUI: el compresor de archivos mágico que triplica el tamaño de tu disco..
Noticias
wolfbcn 3 1,306 Último mensaje 15 Noviembre 2017, 10:57 am
por Bad Heaven
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines