PDF de programación - logica - hc Manual de usuario y notas de implementación

Manual de usuario y notas de implementación

hc

F. Javier Gil Chica

2010

Parte I
Manual de usuario

1. Qué es hc

hc es un compresor por códigos de Huffman. La compresión de Huffman
es un ejercicio de programación a la vez sencillo, clásico y vistoso; también
demuestra lo lejos que está este algoritmo, al menos en su versión básica, de
los algoritmos usados en los compresores más populares, como gzip.

2. Uso

El programa puede usarse para comprimir archivos, para descomprimirlos
y finalmente para dar información sobre un archivo, sin comprimirlo. Para
comprimir:

hc C <archivo origen> <archivo destino>

Para descomprimir

hc D <archivo origen> <archivo destino>

Para presentar información sobre el archivo:

hc I <archivo>

1

Esta información incluye el número de bytes del archivo, el número de
bytes que contendría el archivo comprimido, el número de símbolos (bytes)
distintos del archivo y las cadenas de bits que codifican cada uno de los
bytes. Esta última información se muestra como una tabla de tres columnas:
la primera columna contiene los números de los símbolos que aparecen en
el fuente; la segunda, el número de apariciones de cada símbolo; la tercera,
la cadena de bits con que se codifica. Como ejemplo trivial, consideremos el
siguiente archivo, que hemos llamado ejemplo.txt:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbb
cccccccccc
ddddd

La orden hc I ejemplo.txt produce la salida

0000
1
01
001
0001

4
40
20
10
5

10
97
98
99
100
NSIMB: 5
NBYTES: 79
COMPRIMIDO: 19

En efecto, vemos que el carácter más frecuente, la letra ’a’ (97 ascii) se
codifica con la secuencia más corta de un sólo bit (1). El carácter menos
frecuente, nueva línea, (ascii 10), con la secuencia más larga.

Tanto para comprimir como para descomprimir el programa no comprue-
ba si el destino existe o no. Si existe, será sobreescrito. Si no existe el archivo
origen o por alguna razón no puede abrirse el archivo destino para escritura,
se emite un mensaje de error.

Parte II
Notas de implementación

3. La estructura nodo

Omito la discusión sobre el algoritmo de Huffman, ya que puede encon-
trarse en muchos lugares. En esencia, consiste en la construcción de un árbol.

2

Y la idea original de Huffman consiste en construir este árbol desde las ho-
jas hacia la raíz, en lugar del procedimiento propuesto anteriormente por
Shannon, que iba de la raíz a la hojas.

En nuestra implementación, las hojas están representadas por el tipo

struct nodo:

struct nodo
{

struct nodo *der,*izq,*arr;
int cuenta;
char bit;
unsigned char karacter;
char *codigo;
char nbits;

}HOJAS[256],*TELAR[256],*MENOR,*SEGUNDO;

Cada nodo tiene tres punteros, dos hacia ”abajo” y uno hacia ”arriba”.
Siguiendo los punteros hacia ”abajo” se va desde la raíz a las hojas. Siguiendo
el puntero ”arriba” se alcanza la raíz desde cualquier hoja. Cada hoja contiene
además la siguiente información:

cuenta es el número de veces que aparece cada símbolo. Véase que se
ha declarado un vector de 256 nodos llamado HOJAS, de tal forma que
HOJAS[j].cuenta es el número de apariciones del carácter j.

bit es un carácter que puede tomar los valores 0 o 1. Todos los nodos
tienen asignado un valor. Al recorrer el árbol desde una hoja j a la
raíz, la secuencia de 0’s y 1’s determina la codificación del carácter j.
Realmente, se usará la secuencia inversa, que es la que, en el proceso de
descompresión, lleva desde la raíz hasta la hoja j, conociéndose así que
ha de escribirse el carácter j en el archivo de salida.

karacter contiene simplemente en la hoja j el valor j. Esto es necesa-
rio en la descompresión: cuando se alcanza una hoja, es preciso saber
qué hoja se ha alcanzado.

codigo es una cadena. Contiene una secuencia de 0’s y 1’s, y es la que
se empleará en el proceso de compresión. Una vez construido el árbol,
desde cada hoja se ”sube” hasta llegar a la raíz, y los valores del campo
bit de cada nodo se van apilando. Una vez alcanzada la raíz, el tope
de la pila determina la longitud que hay que reservar para codigo.
Finalmente, se recorre la pila hacia abajo transcribiendo en codigo un
0 o un 1. Un 2 indica el final.

3

nbits es el número de bits con que se codifica un carácter. Esta in-
formación, junto con el número de veces que aparece cada carácter,
permite a la opción I calcular el tamaño del archivo resultante si fuese
comprimido (sin contar cabecera)

4. El telar

He acudido aquí a una imagen visual para construir el árbol. Imaginemos
un vector de 256 nodos, representando las hojas, y otro vector de 256 punteros
a nodo. Originalmente, el puntero j apunta a la hoja j. A este vector de
punteros a nodo es al que he llamado TELAR. Pues bien, el proceso de ”tejido”
del árbol es el siguiente:

1. Excluyendo aquellos nodos cuya cuenta es nula, recorremos los ele-
mentos del TELAR y localizamos las dos cuentas más bajas. Es decir,
localizamos los dos punteros que apuntan a las hojas cuyas cuentas son
más bajas.

2. Creamos un nuevo nodo. Los punteros der e izq son apuntados a los
dos nodos, siguiendo algún criterio. El nuestro ha sido que izq apunta
al de menor cuenta, y que der apunta al de mayor cuenta. Al mismo
tiempo, el nodo de menor cuenta es etiquetado con un 0 (campo bit
a cero), y el de mayor cuenta con un 1. En el nuevo nodo creado, su
cuenta se establece como la suma de las cuentas de los dos nodos a los
que apunta mediante izq y der.

3. De los dos punteros originales del TELAR, uno se hace NULL, y el otro se
hace apuntar al nodo recién creado. Por tanto, si NSIMB era el número de
símbolos distintos encontrados en el archivo fuente, ahora hay NSIMB-1
nodos apuntados por TELAR.

4. El proceso se repite de forma recursiva hasta que quede un único pun-
tero en TELAR (descontando los punteros que apuntaban a hojas de
cuenta cero y los punteros que han ido poniéndose a NULL): este pun-
tero apuntará a la raíz del árbol.

5. La codificación

Ahora ya es posible encontrar la secuencia que codifica cada carácter,

usando el artificio de la pila mencionado antes.

4

6. Compresión

Una vez construido el árbol, el proceso de compresión es sencillo, y consta
esencialmente de dos pasos: la escritura de la cabecera, que luego ha de
permitir la descompresión del archivo, y la compresión propiamente dicha.

En cuanto a la cabecera, es muy sencilla: contiene un entero con el número
de bytes del archivo original (que se obtuvo en la pasada primera para contar
el número de apariciones de cada carácter); un carácter con el número de
símbolos diferentes y para cada símbolo que aparece, una pareja con: un
carácter con el número del símbolo y un entero con el número de apariciones:

+---------+---------+---------+
|
+---------+---------+---------+

NSIMB | j | n(j)|*

NBYTES |

En el proceso de descompresión, esto es todo lo que se necesita para

construir el árbol, y a partir de ahí proceder a descomprimir.

En cuanto a la compresión propiamente dicha, se acude al archivo fuente,
y para cada carácter j la cadena HOJAS[j].codigo contiene la cadena que
codifica a ese carácter. Se recorre esa cadena y según se encuentre un 0 o un
1 se establece a 0 o 1 un bit en un buffer. En nuestro caso, el buffer es un
sólo carácter. Cada vez que el buffer se llena, se escribe al archivo destino.
En realidad, hay un contador que hemos llamado nbit que indica al bit que
corresponda en el buffer de carácter, y se incrementa cada vez a medida
que se recorre la cadena de codificación. Si nbit se encuentra que vale 8, se
escribe el buffer en destino, se establece a 0 (todos los bits a 0) y se establece
nbit=0. El proceso se repite mientras hay caracteres que leer del archivo de
origen.

7. Descompresión

El proceso de descompresión también es sencillo. Una vez leída la cabece-
ra, es posible reconstruir el árbol, y para cada hoja su cadena de codificación.
Se procede leyendo la corriente de bits del archivo origen. Originalmente, un
puntero apunta a la raíz del árbol, y se mueve siguiendo los punteros izq o
der según que se lea del archivo fuente un bit 0 o un bit 1. Si se detecta que
se ha alcanzado una hoja (puntero izq o der a NULL), entonces esa hoja se
identifica mediante el campo karacter, que se escribe en el fichero destino.
El puntero se devuelve a la raíz del árbol. Esta operación se repite tantas
veces como se indica en el campo NBYTES que fue leído de la cabecera.

5

Parte III
Pruebas

8. Rendimiento

El rendimiento de este sencillo compresor está muy lejos del conseguido
por los mejores programas. Obtiene unos ratios de compresión (en tanto por
ciento respecto al archivo original), que duplican a los obtenidos por gzip
cuando se trata de código fuente o texto ascii. La razón de compresión es
inferior al doble a la obtenida por gzip cuando se trata de archivos ejecuta-
bles. En cuanto a la velocidad, es comparable. Por dar alguna cifra, un texto
ascii de unos 3MB queda comprimido en poco más de 2MB, mientras que
gzip consigue poco menos de 1MB.

6