Taller 11: Algoritmos de compresión

Objetivos

  • Analizar y comprender el rol importante de las estructuras de datos en contexto de compresión
  • Implementar un algoritmo de compresión
  • Entender la importancia de la compresión de datos para la infraestructura computacional y dimensionar la cantidad de espacio ahorrado.

    Descripción general

Hoy en día contamos con una gran cantidad de información por todas partes y aunque ahora los costos de almacenamiento son mucho más bajos, los volúmenes de la información que manejamos hoy en día son tan grandes que no es suficiente. Además de eso, solemos estar conectados a Internet enviando y recibiendo información pero en ciertos casos no contamos con las mejores velocidades de transferencia para realizar esto.

Los archivos suelen tener mucha redundancia y esto es una característica que nos permite ahorrar espacio con el uso de diferentes algoritmos.

En este taller usaremos el algoritmo de Huffman para comprimir archivos (sobre todo de texto) y revisaremos que tan efectiva es esta compresión.

La aplicación cuenta con la funcionalidad de comprimir o descomprimir un archivo. En la carpeta data se guarda el archivo compressed cuando un archivo ha sido comprimido y expanded cuando este ha sido descomprimido.

Instrucciones de desarrollo

Nota: Antes de iniciar, lea la sección 0. Envío de talleres: Términos y Condiciones, en esta sección se encuentran enumeradas las reglas y recomendaciones de desarrollo y envío de proyectos establecidas a lo largo del curso.

  1. Por favor, descargue el esqueleto del ejercicio
  2. Adapte su archivo MaxHeapPQ.java del taller de colas de prioridad para que ahora sea una cola de prioridad en orden ascendente (el del taller 5 es de orden descendente). Nombre este nuevo archivo MinHeapPQ.java y úselo para reemplazar el archivo del mismo nombre en el directorio estructuras de este taller.
  3. Complete los TODO's de la clase Huffman en el directorio estructuras
  4. Verificar el funcionamiento completo de la aplicación con varios archivos de tipos distintos. En caso de que algún inconveniente sea detectado, por favor realizar las correcciones pertintentes y adecuadas.

Preguntas

  1. Comprima diferentes tipos de archivo. Entre ellos por lo menos incluya uno de imagen, otro de texto, y uno se sonido
  2. Compare las tasas de compresión para cada tipo de archivo ¿En qué casos es más efectivo el algoritmo de Huffman? ¿Por qué?

Reto (Opcional)

  • Investigue sobre el método de compresión LZW
  • Implement dicho método y compárelo con el de Huffman

Entrega para bonificación

Fecha límite de entrega: Ver

  1. Verifique que su aplicación cumple con las condiciones descritas en Envío talleres.
  2. Realice pruebas unitarias para el funcionamiento de la aplicación. Estas deben encontrarse en el paquete taller.test.
  3. Responda las preguntas presentadas en este enunciado en el archivo README.md.
  4. Cargue el taller a su repositorio en Bitbucket. No olvide crear el archivo calificacion.txt