Huffman Tree Compressor

Tecnologías implementadas

Proceso y desafíos

1. Librería para leer/escribir bits: para ello tuve que desarmar cada carácter utilizando los operadores cuya utilidad es moverse. Para escribir bits, hice un array donde se escribía 1s y 0s, y cuando llegaba a la cantidad de 8 lo convertía a un ASCII usando el típico algoritmo de decimal a binario (sumatoria de 2 elevado a esa n posición).

2. Recorrer el archivo: durante la cursada desarrollamos una librería que leía/escribía archivos utilizando fread y fwrite de c++ nativo (stdio.h)..

3. Guardar los bits en un array con su cantidad de ocurrencias, luego ordenar según cantidad.

4. Crear árbol.

5. Escribir encabezado para poder reconstruir el árbol.

6. A medida que se lee el archivo nuevamente, hay que ir generando cada clave de cada carácter con el árbol y en escribirlo en otro archivo..

7. Para descomprimir: reconstruir árbol leyendo el encabezado.

8. Leyendo el contenido, descifrar de qué carácter se trata buscando en el árbol Huffman.

9. Escribir archivo descifrado.

Decisiones Técnicas

• Entrada/salida de bits a medida

  Escribí una librería propia de lectura/escritura de bits usando I/O nativo de C++ (fread/fwrite), empaquetando bits en bytes manualmente con un enfoque de acumulación decimal a binario.

• Reconstrucción del árbol vía encabezado

  Codifiqué la estructura del árbol Huffman en un encabezado del archivo para que el descompresor pudiera reconstruir el mismo árbol exacto antes de decodificar.

Desafíos

• Reconstrucción a nivel de bits

  Lograr una reconstrucción sin pérdida requirió reconstruir cuidadosamente el árbol desde el encabezado y hacer coincidir cada secuencia de bits decodificada con su carácter original.

Estado Actual

Conclusión y mejoras a futuro

Me gustaría en un futuro subir este proyecto a una lambda function y hacer un pequeño sitio para hacer uso de este algoritmo.