Foro de elhacker.net

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 (http://articulos.conclase.net/compresion/huffman.html) 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 (http://www.mediafire.com/?dbfzqjzm4mz)

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

Salu2

EDITADO

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 ;)

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!!

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

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...

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

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

Te refieres a tratar todo con Strings?

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.

Ok, entonces lo esperamos  ;D