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.
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.
Bueno, y ahora la implementación en C.
Hay dos programas:
© Febrero de 2.001, Con Clase, webmaster@conclase.net