Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010

Projects Section Proyecto: descompresor de datos

En este proyecto trabajaremos con un algoritmo sencillo de compresión de datos sin pérdidas. Dados unos datos, un algoritmo de compresión sin pérdidas permite codificarlos, generalmente de forma más compacta (con menos bytes), de tal forma que sea posible posteriormente recuperar dichos datos originales a partir de su versión comprimida. El algoritmo que usaremos es una adaptación de LZ77, en el que se basan muchos compresores conocidos.

En concreto, desarrollaremos un programa para descomprimir datos. El programa tomará como entrada un fichero que contiene la información comprimida. Debe leer dicho fichero, descomprimir la información y generar como salida el fichero con los datos resultantes. Si todo funciona, este fichero debería contener los mismos datos que el fichero original, antes de ser comprimido.

Formato de datos

En este apartado se especifica el formato de codificación de los datos comprimidos, y el procedimiento que debe seguir el descompresor para decodificarlos.

El fichero comprimido se compone de bytes. Estos bytes codifican una secuencia de símbolos, que serán procesados por el descompresor para obtener los datos originales.

Símbolos

Representaremos los datos comprimidos como una secuencia ordenada de símbolos, donde cada símbolo representa:

  • El valor literal de un byte.
  • Una instrucción para replicar una secuencia de bytes decodificada anteriormente. Dicha secuencia se identifica mediante dos números: un desplazamiento y una longitud. El desplazamiento indica cuántos bytes hay que retroceder para llegar al inicio de la secuencia (1 indica que la secuencia se inicia con el último byte decodificado hasta el momento, 2 indica que se inicia con el penúltimo, esto es, el segundo más reciente, y así sucesivamente). La longitud indica de cuántos bytes consta la secuencia. Para simplificar el proceso de decodificación, se puede asumir que la longitud será siempre menor o igual que el desplazamiento.

Los símbolos deben ser decodificados uno a uno y en el orden en que se leen desde el fichero comprimido.

Por ejemplo, supongamos la siguiente secuencia de símbolos: literal (3), literal (4), literal (5), literal (6), literal (7), literal (8), repetición (desplazamiento 4, longitud 3). Los símbolos se van decodificando uno a uno. Hasta el literal de 8, se habrán decodificado los bytes 3, 4, 5, 6, 7 y 8, donde 8 es el más reciente y 3 es el más antiguo. El símbolo de repetición que los sigue representa los bytes 5, 6 y 7 (se retrocede cuatro posiciones en la secuencia de bytes decodificados hasta el momento y se toman tres bytes a partir de este). La secuencia final de bytes decodificados es, por tanto, 3, 4, 5, 6, 7, 8, 5, 6 y 7.

Codificación de los símbolos como bytes

Dado que los ficheros se componen de bytes, los símbolos se encuentran codificados en el fichero comprimido como una secuencia de bytes. Es necesario leer secuencialmente los bytes del fichero para reconstruir la secuencia de símbolos. Cada símbolo se compone de uno o más bytes dependiendo de su tipo:

  • Símbolos literales representando valores entre 0 y 254: se codifican como un byte del mismo valor. Por ejemplo, literal (45) se codifica como un byte de valor 45.
  • Símbolos literales representando el valor 255: se codifican como dos bytes consecutivos, ambos con valor 255.
  • Símbolos de repetición: se codifican como un byte con valor 255 seguido por una secuencia de tres bytes (L, D0, D1). El primero de ellos, L, contiene la longitud menos 5 (esto es, el valor L = 0 representa una repetición de longitud 5, el valor L = 1 representa una repetición de longitud 6, etc.) No se permite el valor 255 para este byte, por lo que la máxima longitud codificable es 254 + 5 = 259. Los dos bytes siguientes, D0 y D1, representan el desplazamiento menos 1, siendo D0 el byte menos significativo. Se decodifican mediante la fórmula 1 + D0 + 256 * D1. Por ejemplo, los valores D0 = 7 y D1 = 3 indican que el desplazamiento es 1 + 7 + 3 * 256 = 776.

Por ejemplo, supongamos información comprimida mediante los siguientes bytes: 1, 2, 3, 4, 5, 255, 255, 6, 7, 254, 253, 255, 0, 5, 0, 255, 5, 9, 0. Esta secuencia da lugar a los siguientes símbolos:

  1. Byte 1: literal (1).
  2. Byte 2: literal (2).
  3. Byte 3: literal (3).
  4. Byte 4: literal (4).
  5. Byte 5: literal (5).
  6. Bytes 255, 255: literal (255).
  7. Byte 6: literal (6).
  8. Byte 7: literal (7).
  9. Byte 254: literal (254).
  10. Byte 253: literal (253).
  11. Bytes 255, 0, 5, 0: repetición (longitud 5, desplazamiento 6).
  12. Bytes 255, 5, 9, 0: repetición (longitud 10, desplazamiento 10).

La descompresión de estos símbolos da como resultado la secuencia: 1, 2, 3, 4, 5, 255, 6, 7, 254, 253, 5, 255, 6, 7, 254, 255, 6, 7, 254, 253, 5, 255, 6, 7, 254.

Buffer de datos

Dado cómo se calcula, el máximo desplazamiento representable es de 65536 (1 + 255 + (256 * 255)). Por tanto, no hace falta recordar todos los datos decodificados, sino sólo los últimos 65536. En consecuencia, el descompresor debe disponer de un buffer de dicho tamaño que almacene los últimos 65536 bytes decodificados. Inicialmente, antes de descomprimir el primer byte, el descompresor debe asumir que los últimos 65536 bytes tienen valor 0.

Qué se pide

Escribe un programa que, dado un fichero comprimido según lo descrito anteriormente, lo descomprima. El programa debe tener una clase llamada Decompressor con un método main. Recibirá dos argumentos de línea de comandos: un nombre de fichero de entrada, que contendrá los datos comprimidos, y un nombre de fichero de salida, donde el programa escribirá los datos descomprimidos. Si el fichero de salida ya existiese, debe ser sobreescrito por tu programa. Un ejemplo de invocación en línea de comandos es: 

java Decompressor compressed.dat uncompressed.dat

Si ocurre algún error de entrada/salida en el proceso, debido a que el fichero de entrada no existe o falla su lectura, o debido a que falla la escritura del fichero de salida, tu programa puede detenerse con la excepción IOException correspondiente. Si no se pueden decodificar los datos de entrada por ser su formato incorrecto (por ejemplo, se lee un byte 255 que inicia un símbolo de varios bytes, pero no hay más bytes disponibles en el fichero), tu programa debe también detenerse con una excepción que lo indique.

Recomendaciones de diseño

Un buen diseño del programa te ayudará a conseguir mejor nota. Por una parte, los profesores valoraremos positivamente en la nota de la entrega un código limpio y organizado, con un buen diseño que utilice adecuadamente la orientación a objetos. Por otra parte, un código de calidad te ayudará a obtener mejor nota en el examen del proyecto, en que tendrás un tiempo limitado para realizar algunas modificaciones a tu programa. En esta sección proponemos algunos consejos para diseñar el programa. No obstante, otros diseños alternativos son posibles y podrían ser igual de buenos o incluso mejores, por lo que no tienes por qué seguir necesariamente nuestras sugerencias.

Organización en clases

En cuanto al diseño general del programa, te recomendamos separar en distintas clases la funcionalidad de la aplicación. Por ejemplo, puedes programar clases separadas para:

  • La lectura del fichero de entrada. Por ejemplo, podría tener un método que lea un nuevo byte y lo devuelva. Una posible forma de señalar al resto del código que se ha alcanzado el final del fichero y no hay más datos disponibles es lanzar una excepción cuando esto ocurra.
  • La obtención de una secuencia de símbolos a partir de una secuencia de bytes. Proporcionaría un método que decodifique y devuelva el siguiente símbolo. Internamente puede leer uno o más bytes utilizando la clase anterior.
  • La obtención de la secuencia de bytes decodificada a partir de la secuencia de símbolos. Podría proporcionar un método que devuelva el resultado de decodificar el siguiente símbolo. Internamente podría utilizar la clase anterior para ir obteniendo los símbolos a medida que sean necesarios.
  • La orquestación de todo el proceso de descompresión, utilizando adecuadamente las clases anteriores.
  • La representación de símbolos. Además, dado que hay dos tipos de símbolos, es probable que te interese que ambos hereden de una superclase común.
  • La implementación del buffer donde se almacenan los últimos bytes decodificados.
  • Excepciones propias de tu programa, si las crees necesarias.

El buffer de datos

Puedes diseñar el buffer que almacena los datos previamente decodificados como una clase que internamente contenga un array de 65536 bytes (datos de tipo byte en Java). En esta clase puedes programar los métodos necesarios para introducir nuevos bytes en el buffer y para leer bytes dado su desplazamiento y longitud.

Puedes gestionar el buffer de forma circular, al igual que se hace para implementar una cola sobre un array. Cuando al introducir nuevos datos se alcance el final del array, se continúa escribiendo por el principio, sobreescribiendo los datos antiguos. Dado que en ningún caso serán necesarios datos más antiguos que los últimos 65536, no pasa nada aunque se sobreescriban.

Es muy importante que compruebes que tu buffer funciona en situaciones en que se sobrepasa el final del array y se vuelve, por tanto, a su inicio. Como 65536 son muchos datos, para facilitar que pruebes este tipo de casos, te recomendamos que proporciones un constructor alternativo que reciba un tamaño de buffer. Esto te permitirá realizar pruebas con tamaños pequeños de buffer (por ejemplo, 8 ó 16 bytes), que facilitan enormemente analizar el comprotamiento de tu código.

Algunos detalles de implementación

El tipo de datos byte en Java

Puedes utilizar el tipo de datos byte de Java en la implementación, pero hay algunos detalles que debes tener en cuenta para utilizarlo correctamente.

En primer lugar, un dato de tipo byte en Java representa valores con signo, entre -128 y 127, codificados mediante complemento a dos. Cuando leas un dato de tipo byte de un fichero, los bytes con valor entre 128 y 255 del fichero se verán en Java como negativos. El 255 se verá como un -1, el 254 como un -2, y así sucesivamente hasta el 128, que se verá como un -128. Los valores entre 0 y 127 se verán normalmente. Por tanto, cuando quieras saber si un byte que has leído de un fichero tiene valor 255, en Java debes comparar el dato con un -1.

Esto afecta también a cómo debes hacer la operación 1 + D0 + 256 * D1. Si la haces directamente, no funcionará como esperas. Una posible forma de hacer la operación en Java es la siguiente: 

byte d0 = ...
byte d1 = ...
int offset = 1 + (d0 & 0xFF) + ((d1 & 0xFF) << 8);

Otro detalle que debes tener en cuenta es que cuando invoques a un método en Java que reciba un byte, y le quieras pasar un valor literal, debes hacer lo siguiente: 

public void method(byte value) {
    (...)
}
(...)
method((byte) 5);

Si no haces explícitamente la conversión a byte, el compilador intentará buscar un método que reciba un entero en vez de un byte.

Ficheros de ejemplo

En la siguiente tabla puedes encontrar algunos ejemplos de ficheros comprimidos, junto con su correspondiente versión descomprimida. Puedes usarlos para detectar posibles errores en tu descompresor. Empieza probando los ficheros más pequeños. Además de usar estos ficheros, te podría venir bien crear tú mismo algunos pequeños ficheros de ejemplo utilizando un editor de ficheros binarios.

Descripción Comprimido Descomprimido
Fichero Tamaño Fichero Tamaño
Only simple literals literals-1.in 6 literals-1.out 6
Only literals including 255 at the beginning literals-2.in 8 literals-2.out 7
Only literals including 255 at the end literals-3.in 8 literals-3.out 7
Only literals including 255 in the middle literals-4.in 8 literals-4.out 7
Only literals including adjacent 255 literals-5.in 10 literals-5.out 8
Only literals 1 literals-6.in 18 literals-6.out 12
Only literals 2 literals-7.in 4 literals-7.out 4
Project example example.in 19 example.out 25
Single repetition 1 repetition-1.in 10 repetition-1.out 12
Double repetition repetition-2.in 14 repetition-2.out 18
Prefetch repetition repetition-3.in 6 repetition-3.out 7
Triple repetition repetition-4.in 18 repetition-4.out 24
Single repetition 2 repetition-5.in 16 repetition-5.out 18
Buffer overflow 1 overflow-1.in 65538 overflow-1.out 65538
Buffer overflow 2 overflow-2.in 196609 overflow-2.out 196609
Buffer overflow + repetition 1 overflow-3.in 65542 overflow-3.out 65543
Buffer overflow + repetition 2 overflow-4.in 65542 overflow-4.out 65543
Incorrect literal incorrect-1.in 3 (error expected) -
Incorrect repetition 1 incorrect-2.in 4 (error expected) -
Incorrect repetition 2 incorrect-3.in 5 (error expected) -
Simple example with all symbols simple.txt.psz 53 simple.txt 58
Don Quijote de La Mancha quijote.txt.psz 2702 quijote.txt 3128
Sample photo (BMP format) photo.bmp.psz 2023506 photo.bmp 2359418

La mayoría de los ficheros son binarios. Para verlos, es mejor que uses un editor de ficheros binarios. Por conveniencia, puedes descargar un fichero ZIP con todas las pruebas en este enlace.

Condiciones generales y procedimiento de entrega

El proyecto debe ser realizado por equipos de dos alumnos, salvo que tu profesor te autorice con antelación la realización en equipos con otro número de personas. Debes comunicar quiénes componen tu equipo a tu profesor de grupo reducido en el plazo que este establezca para ello. Todos los miembros del equipo deben estar matriculados en el mismo grupo.

Un miembro del equipo debe entregar el proyecto en AulaGlobal, en el espacio del grupo reducido correspondiente, a través del enlace que se habilitará al efecto. El plazo de entrega se anunciará a través de Aula Global. No se evaluarán entregas recibidas más tarde de este plazo.

Se entregará un único fichero comprimido con formato ZIP. Sólo debe contener el código fuente de tu programa (ficheros .java) y un fichero de texto plano llamado readme.txt. No debes entregar las clases compiladas (ficheros .class) ni ningún otro fichero.

El fichero readme.txt contendrá el NIA, apellidos y nombre de los integrantes del grupo y (opcionalmente) una breve explicación de no más de 4 párrafos del diseño utilizado en el proyecto. Si hay algún hecho relevante que deba conocer tu profesor, debes indicarlo también en este fichero. Son relevantes, por ejemplo, el hecho de que alguno de los miembros del grupo no haya participado en la realización del proyecto, o el hecho de que tu entrega contenga errores conocidos que no hayas conseguido resolver a tiempo (en este caso, el profesor puede valorar positivamente que describas el error indicando en qué situación ocurre, qué debería hacer el programa en dicha situación, qué hace realmente y cuál podría ser la causa, si tienes alguna sospecha razonable).

El nombre del fichero ZIP debe ser group-XX-YYYYYYYYY-ZZZZZZZZZ.zip, donde XX es el número del grupo en que estás matriculado, YYYYYYYYY el NIA más pequeño de los miembros del equipo y ZZZZZZZZZ el NIA del otro miembro. Por ejemplo: group-71-188888888-199999999.zip.

La autoría del código debe ser exclusivamente de los miembros del equipo que firma la entrega. Si los profesores detectan que la entrega contiene código creado por otras personas (otros alumnos, profesores de academia, etc.), se procederá a aplicar los mecanismos previstos en la normativa vigente para casos de defraudación en pruebas de evaluación, que suponen la calificación de los alumnos implicados con un 0 (SUSPENSO) como nota final de la asignatura. Los profesores de esta asignatura utilizan herramientas de detección de código similar entre todas las entregas recibidas, por lo que existe una probabilidad real de que detecten fragmentos de código copiados, incluso entre equipos de distintos grupos y profesores. Estas herramientas pueden detectar similitudes incluso aunque se cambien comentarios, nombres de variables y métodos, se modifique el orden del código o su espaciado, etc.