Compresión de Huffman 0. Archivos
Last updated Mar 24, 2023
by
sr_labs Admin
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
* Contar cuantas veces aparece cada carácter en el fichero a comprimir. Y crear una lista enlazada con la información de caracteres y frecuencias.
* Ordenar la lista de menor a mayor en función de la frecuencia.
* Convertir cada elemento de la lista en un árbol.
* Fusionar todos estos árboles en uno único, para hacerlo se sigue el siguiente proceso, mientras la lista de árboles contenga más de un elemento:
* Con los dos primeros árboles formar un nuevo árbol, cada uno de los árboles originales en una rama.
* Sumar las frecuencias de cada rama en el nuevo elemento árbol.
* Insertar el nuevo árbol en el lugar adecuado de la lista según la suma de frecuencias obtenida.
* Para asignar el nuevo código binario de cada carácter sólo hay que seguir el camino adecuado a través del árbol. Si se toma una rama cero, se añade un cero al código, si se toma una rama uno, se añade un uno.
* Se recodifica el fichero según los nuevos códigos.
## 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.
# Ejemplo

# Enlaces de interés
Algoritmo de compresión de Huffman, Con Clase, [https://conclase.net/blog/item/huffman#gsc.tab=0](https://conclase.net/blog/item/huffman#gsc.tab=0)
Codificación Huffman, Wikipedia, [https://es.wikipedia.org/wiki/Codificaci%C3%B3n_Huffman](https://es.wikipedia.org/wiki/Codificaci%C3%B3n_Huffman)
sr_labs Admin Mar 27, 2023