Algoritmo de compresión de Huffman

[Principal] [Índice de artículos]

Generalidades:

Se trata de un algoritmo que puede ser usado para compresión o encriptación de datos.

Este algoritmo se basa en asignar códigos de distinta longitud de bits a cada uno de los caracteres de un fichero. Si se asignan códigos más cortos a los caracteres que aparecen más a menudo se consigue una compresión del fichero.

Esta compresión es mayor cuando la variedad de caracteres diferentes que aparecen es menor. Por ejemplo: si el texto se compone únicamente de números o mayúsculas, se conseguirá una compresión mayor.

Para recuperar el fichero original es necesario conocer el código asignado a cada carácter, así como su longitud en bits, si ésta información se omite, y el receptor del fichero la conoce, podrá recuperar la información original. De este modo es posible utilizar el algoritmo para encriptar ficheros.

Mecanismo del algoritmo:

Veamos un ejemplo:

Tomemos un texto corto, por ejemplo:

"ata la jaca a la estaca"

1) Contamos las veces que aparece cada carácter y hacemos una lista enlazada:

' '(5), a(9), c(2), e(1), j(1), l(2), s(1), t(2)

2) Ordenamos por frecuencia de menor a mayor

e(1), j(1), s(1), c(2), l(2), t(2), ' '(5), a(9)

3) Consideremos ahora que cada elemento es el nodo raíz de un árbol.

4) Fundimos los dos primeros nodos (árboles) en un nuevo árbol, sumamos sus frecuencias y lo colocamos en el lugar correspondiente:

Y sucesivamente:

El resultado final es:

5) Asignamos los códigos, las ramas a la izquierda son ceros, y a la derecha unos (por ejemplo), es una regla arbitraria.

a
' '
c
l
t
s
e
j
0
10
1100
1101
1110
11110
111110
111111

6) Y traducimos el texto:

a
t
a
' '
l
a
' '
j
a
c
a
' '
a
' '
l
a
' '
e
s
t
a
c
a
0
1110
0
10
1101
0
10
111111
0
1100
0
10
0
10
1101
0
10
111110
11110
1110
0
1100
0

Y sólo queda empaquetar los bits en grupos de ocho, es decir en bytes:

01110010
11010101
11111011
00010010
11010101
11110111
10111001
10000000
0x72
0xD5
0xFB
0x12
0xD5
0xF7
0xb9
0x80

En total ocho bytes, y el texto original tenía 23.

Pero no nos engañemos, también hay que almacenar la información relativa a la codificación, por lo que se puede ver que para textos cortos no obtendremos mucha reducción de tamaño.

Programas en C:

Bueno, y ahora la implementación en C.

Hay dos programas:

  1. El compresor "compres.c" (10060 bytes): (Alternativo: )
  2. El descompresor "decomp.c" (4850 bytes): (Alternativo: )