Algoritmo Huffman

Para compresión no está muy sencillo porque necesitas usar por ejmplo un short para poder guardar un byte sin signo, ya que en Java no hay tipos numéricos sin signo. Cuando dices 110 no sé si es en binario (o sea el 5 decimal) o el número 110 decimal. Suponiendo que sea 110 binario, necesitas solamente tres bits. Como solamente puedes manejar bytes, quiere decir que tienes 5 bits libres. Si los quieres ir escribiendo en el orden en que van (o sea los 3 bits más significativos que sean 1, 1, 0) entonces:

Necesitas conocer los operadores que trabajan sobre bits:

<< shift left
>> shift right
& and
| or
^ xor

entonces si tienes por ejemplo grupos de 3 bits, que no caben justos en un byte, vas a tener que hacer muchos malabares. Suponiendo que usas grupos de 4 bits sería algo asi, teniendo a y b que son 2 bytes separados de los cuales solamente usas los 4 bits menos significativos, para agruparlos en un solo byte sería así:

De ese modo si a = 1010 (en binario) y b = 1001 (en binario), x contendrá 10101001. El and con 0xff es para que si por alguna razón a o b tienen signo negativo, se los quite (siempre y cuando a y b sean tipo byte).

3

No veo los cambios que hiciste al post. En fin. No puedes escribir bits a un archivo. Puedes escribir bytes completos, o sea grupos de 8 bits; simplemente usa un FileOutputStream. Si ya tienes tu arreglo de bytes usas el método write(byte[]) y si tienes un solo byte entonces usas el write(int), que recibe un entero pero solamente usa los 8 bits menos significativos del mismo, para que puedas tener valores de 0 a 255.

Lo que no entiendo es cómo calculaste que la representación óptima de   es 110 y luego cuando lo quieres escribir te lo guarda como cadena. Eso significa que no tienes el número 110 binario, algo raro hiciste. Regreso a lo mismo: revisa los operadores para manejo de bits en Java.

Lo que pasa es que yo estaba equivocado, te explico si por ejemplo aplicando el algoritmo de huffman a un texto obtenia que la representacion binaria optima de a era 0011, y la de b era 1100, luego si queria comprimir un archivo de texto por ejemplo "ab", lo que yo hacia ( muy ingenuo por cierto ) era unir la representacion de a y la de b y la guarda directo en el archivo, osea en el archivo guardaa 00111100 xD, por eso me tome mi tiempito para analizar el problema y descubri que si queria comprimir el texto "ab" el truco era guardar el caracter correspondiente al codigo binario resultaod de unir los codigos optimos de a y b.

Osea si queria guardar el texo "ab", su codigo binario optimo era "00111100", el caracter correspondiente a ese codigo binario es "<", me entiendes? obio sin decuidar que cada cada caracter que guarde tiene que tener solo 8 bits, si sobran bits lo guardo para el siguiente caracter a guardar.

Bueno en fin, te comento que al fin pude terminar el Codigo, ya me funciona, ahora puedo comprimir mis archivos de texto plano, pero me ha surgido una duda,
mira yo guardaba datos tipos bytes en el archivo, para el ejemplo anterior guardaba el codigo ASCCI de "<" cuyo codigo binario es "00111100" en el archivo, luego por ejemplo otro byte cuya representacion binaria es "11110000", y asi sucesivamente, luego cerraba el archivo, Posteriormente cuando llamaba al metodo Descomprimir de mi codigo, y empezaba a leer los bytes que habia guardado en el fichero, los bytes que leia no eran los originales que habia guardado sino uno que se originaba si invertia el codigo binario del byte que guarde.

En resumen si guardaba un byte cuyo codigo binario era 11110000, luego otro cuyo codigo es por ejemplo 11001100, Al momento de leer los bytes del archivo, este leia
un byte cuyo codigo binario era 00001111, el siguiente 00110011, osea el byte que se origina al invertir el codigo binario del byte original que guarde.

Solucione ese problema inviertiendo la representacion binaria de cada byte, pero me he quedado con la duda de porque paso eso , tienes alguna idea?

Solucione ese problema inviertiendo la representacion binaria de cada byte, pero me he quedado con la duda de porque paso eso , tienes alguna idea?

Sin ver el código no tengo manera de saber por qué pasa eso. Pero bueno entonces tenía razón al principio y tenías que escribir los bytes. No sé si estás usando write(byte[]) o write(int) en el stream de salida al archivo, y tampoco sé si estás usando read() o read(byte[]) para leerlos; eso puede afectar la manera en que interpretas los bytes porque el tipo byte va de -128 a 127. Por eso es bueno luego hacerle un bitwise AND con 0xff a cada byte.

Como nota al margen, es ASCII, no ASCCI: American Standard Code for Information Interchange.

write( int ) para escribir y read() para leer

Te sirve esa informacion?

Por cierto necesito una ayudita extra, mira imaginemos el caso donde tengo un archivo, en el cual estoy guardando puros datos tipo Byte,
como puedo hacer para guardar un dato tipo Int en ese archivo de tal manera que despues pueda recuperarlo sin perder informacion ?

te fijaste que el int que escribes esté entre 0 y 255? al leerlo debe darte siempre algo entre 0 y 255. Eso después al convertirlo en byte se cambiará a algo entre -128 y 127. Puede que por ahí venga el problema de que se te invierta.

Un int son 4 bytes; puedes almacenar un int en un byte[4] haciendo esto:

La cosa es cómo saber que tienes que leer un int en cierta posición, en vez de simplemente un byte...

por eso es el problema,
Al principio del archivo voy a escribir un dato tipo byte que contenga la cantidad de datos tipo int que voy a guardar, disculpa la ignorancia pero al leer el ficheromo como puedo ensamblar el dato int a partir de los 4 bytes?

Si tienes tus cuatro bytes en b[] entonces solamente tienes que hacer las operaciones inversas:

Mira lo que yo entendi del codigo que me diste es esto :

sea el numero int 254 cuya representacion en binario es 00000000 0000000 00000000 11111110

Luego de las operaciones que me diste :
b[ 0 ] = 00000000
b[ 1 ] = 00000000
b[ 2 ] = 00000000
b[ 3 ] = 11111110

weno eso es lo que entendi asi que decidi hacer una prueba y al mostrar los datos del vector de bytes en java,

yo pense que me mostraria : 0 0 0 254
Pero Java me muestra lo siguiente : 0 0 0 - 2

Luego por curiosidad me puse a ver el codigo binario de cada byte en java :
 

y java me muestra esto :
0 0 0 11111111111111111111111111111110

Como veras el ultimo codigo binario es el que me inquieta

A que se debo esto? le di una mala inerpretacion al codigo que me diste?

Por tercera vez... el tipo byte va de -128 a 127. No puede valer 254. Si quieres convertirlo a entero positivo tienes que hacerle bitwise AND con 0xff y entonces imprimir  

Hasta que por fin pude terminar completamente el compresor, pero no lo hubiera podido hacer sin tu ayuda Master Ezamudio, en serio me has ayudado muchisiisisisiiiiiiiiisimo.
El compresor funciona de maravillas, comprime el tamano de un archivo hasta casi 50% xD, ademas de que aprendi a manejar los bytes en Java, fue un gran dia donde he aprendido mucho, gracias ah. Hasta luego

Que tal! soy nuevo en java y ando en un curso de Estructura de Datos... ando practicando lo de arboles y huffman quisiera aplicarlo pero como novato no le encuentro donde iniciar, me podiras ayudar.. de antemano gracias.!

Hola! ¿Cómo estás? Mira que he estado investigando en internet sobre Huffman, y mi búsqueda me trajo hasta aquí! Pude ver que te ayudaron a resolver tu problema con la descompresión, y quisiera saber si podrías ayudarme! En mi Universidad me piden como proyecto el Algoritmo Huffman, pero ando perdida :/ ¿Crees que me podrías ayudar? Muchísimas gracias de antemano!

LilibethPF este post fue escrito hace más de 5 años y dudo que el autor original vea tu comentario.

Puedes abrir un nuevo post para preguntar y alguien más podría ayudarte. En que necesitas ayuda? En tu comentario solo dices que andas perdida, pero no aclaras que necesitas hacer, ¿que llevas? ¿en que necesitas ayuda? ¿que cosa no entiendes?

Entre más clara sea tu pregunta, más posibilidades hay de que recibas ayuda.

Saludos

Gracias por responder OscarRyz! Es que estoy llevando la clase de Estructura de Datos y Algoritmos, tengo un Código Huffman con el que puedo comprimir, pero necesito que pueda descomprimir y me devuelva el mensaje original, y no se como hacerlo :/ Lo que necesito es que con el mismo código que ya tengo me descomprima mi mensaje. Gracias de antemano! :D