Codificación Huffman
Hola, a toda la comunidad taringuera. En esta ocasión voy a hablarles (escribirles) sobre un método de compresión sencillísimo: la codificación Huffman. En este post nos ocuparemos sólo de la parte conceptual del algoritmo sin deternos en los detalles rigurosos como la correctitud del algoritmo, prefijos, etc.
El archivo de texto de ejemplo
Empecemos con algo sencillo. Para esta entrada utilizaremos un archivo de texto plano con el siguiente contenido:
[color=#000000]yo compre pocas copas, pocas copas yo compre, como yo compre pocas copas, pocas copas yo pague[/color]
Este texto contiene 94 caracteres (letras) y si damos una mirada al peso del archivo, nos daremos cuenta de que pesa unos 94 bytes más o menos. De lo anterior podemos intuir que cada carácter pesa 1 byte, y si, estamos en lo correcto.
El código ASCII
Cada carácter del archivo de texto pesa 1 byte, que es lo mismo que 8 bits (8 dígitos que sólo pueden ser ceros o unos). ¿Por qué pesan 8 bits? La respuesta se encuentra en el código ASCII. Cada carácter tiene una representación única de 8 bits en el código ASCII. Por ejemplo, el carácter "p" se representa en ASCII como 01110000. Se puede ver una tabla detallada del código ASCII en Wikipedia .
En el texto de ejemplo tenemos 13 caracteres distintos; la codificación ASCII de estos caracteres son dados en la siguiente tabla:
[color=#000000]carácter ASCII
y 01111001
o 01101111
00100000
c 01100011
m 01101101
p 01110000
r 01110010
e 01100101
a 01100001
s 01110011
, 00101100
g 01100111
u 01110101[/color]
Así, por ejemplo, la cadena (palabra) "copas" está compuesta por los caracteres "c" (01100011), "o" (01101111), "p" (01110000), "a" (01100001) y "s" (01110011). Así, la cadena "copas" tiene la siguiente representación binaria ASCII (los colores son sólo para distinguir):
0110001101101111011100000110000101110011
Observa que la cadena "copas" tiene un peso de 40 bits en codificación ASCII.
¿Por qué 8 bits?
En esta sección, básicamente vamos a detallar la respuesta a la pregunta del por qué son necesarios 8 bits para representar a un carácter dando un pequeño repaso de los números binarios.
Recordemos que cualquier numero en base 10 (decimal) puede representarse en base dos (binario) y viceversa. Por ejemplo, el número binario 11001 es 25 en decimal. Para transformar un número binario a decimal basta con sumar potencias de dos de acuerdo a la posición de los dígitos "1". Por ejemplo, para el número binario 11001, los dígitos "1" aparecen en las posiciones cero, tres y cuatro por lo que la suma de potencias de dos es:
por cierto, el número binario 11001 es de 5 bits (cinco dígitos binarios).
El alfabeto ASCII tiene un total de 256 caracteres disponibles como puede verse en la página web AsciiTable . Para poder representar de manera única a cada carácter, el código ASCII asigna a cada carácter un numero desde el 0 hasta el 255. Por ejemplo, el carácter "m" tiene asignado el número 109 que en binario es 1101101 (7 bits).
El número 255 es 11111111 en binario; así, los caracteres ASCII tendrán una representación binario desde el 00000000 hasta el 11111111. Esta es la razón por la cual se necesitan 8 bits para representar a cada carácter de manera única en el código ASCII.
Una primera idea (codificación de ancho fijo)
En esta sección veremos una codificación basándonos en la siguiente observación:
El texto de ejemplo no útiliza todos los caracteres del código ASCII. De hecho sólo utiliza 13 caracteres diferentes.
Como no utilizamos los 256 caracteres ASCII, no necesitamos los 8 bits de representación ASCII. Creemos nuestra propia codificación asignando a cada carácter un número del 0 al 12. La siguiente tabla muestra los códigos de nuestra nueva codificación:
[color=#000000]carácter decimal binario
y 0 0000
o 1 0001
2 0010
c 3 0011
m 4 0100
p 5 0101
r 6 0110
e 7 0111
a 8 1000
s 9 1001
, 10 1010
g 11 1011
u 12 1100[/color]
La palabra "copas" es codificado como (los colores son sólo para distinguir):
00110001010110001001
Observa que la cadena "copas" tiene 20 bits en esta nueva codificación. Así, hemos logrado reducir el peso del texto al 50%. Aunque hemos logrado una compresión del 50%, esta compresión no es la más óptima.
Una mejor idea (codificación de ancho variable)
En la sección anterior hemos logrado comprimir el peso del texto al 50% con una codificación de ancho constante; hemos llegado a esa codificación mediante la observación de que nuestro texto no utiliza todos los caracteres ASCII por lo que no son necesarios 8 bits sino 4 bits para su representación.
Podemos idear otra codificación mediante la siguiente observación:
Hay caracteres que aparecen con mayor frecuencia que otros mientras que hay otros que apenas aparecen en el texto.
La siguiente tabla muestra la frecuencia con la que aparecen los caracteres en el texto:
[color=#000000]carácter frecuencia
y 4
o 17
16
c 12
m 4
p 12
r 3
e 4
a 9
s 8
, 3
g 1
u 1[/color]
La idea está dada: dar a los caracteres de mayor frecuencia una codificación con menor cantidad de bits que los caracteres de menor frecuencia.
Ahora la pregunta es: ¿de qué manera codificamos los caracteres para que tengan una cantidad de bits variable? La respuesta radica en la codificación Huffman, el cual proporciona una codificación óptima con ancho de bits variable.
El núcleo de la codificación Huffman radica en la construcción del árbol de codificación Huffman.
Construcción del árbol de codificación Huffman
El algoritmo para construir el árbol de codificación Huffman es el siguiente:
[color=#000000]1. Crear una lista de N hojas, a cada hoja le corresponde un carácter y su respectiva frecuencia.
2. Repetir hasta que sólo quede un árbol en la lista.
2.1. Buscar los dos árboles cuyas raíces tengan menor valor, sean "Min1" y "Min2".
2.2. Crear un nuevo árbol cuya raíz tiene como valor "Min1 + Min2" y tiene como hijos a los árboles "Min1" y "Min2".
2.3. Eliminar los árboles "Min1" y "Min2" de la lista e insertar en la lista el nuevo árbol creado en el paso anterior.
3. El árbol que queda en la lista es el árbol de codificación Huffman.[/color]
Este algoritmo es algo impreciso (sobre todo por la notación) pero nos servirá para ilustrar la construcción del árbol de codificación Huffman.
Es evidente que "la magia" se produce dentro de las iteraciones (paso 2), por lo que vamos a detallar sólo las iteraciones.
Iteración 1
Paso 1. Buscamos los dos menores árboles en la lista, en este caso se encuentran en las posiciones 12 y 13. La imagen debajo muestra dos flechas apuntando a estos árboles. En este caso min1 = 1 y min2 = 1
Paso 2. Creamos un nuevo árbol cuya raíz tiene un valor igual a min1 + min2 = 2 y cuyos hijos son los árboles min1 y min2.
Paso 3. Eliminamos los árboles de las posiciones 12 y 13 e insertamos el nuevo árbol creado en la lista.
Iteración 2
Paso 1. Buscamos los dos menores árboles en la lista, en este caso se encuentran en las posiciones 11 y 12. La imagen debajo muestra dos flechas apuntando a estos árboles. En este caso min1 = 3 y min2 = 2
Paso 2. Creamos un nuevo árbol cuya raíz tiene un valor igual a min1 + min2 = 5 y cuyos hijos son los árboles min1 y min2.
Paso 3. Eliminamos los árboles de las posiciones 11 y 12 e insertamos el nuevo árbol creado en la lista.
Iteración 3
Paso 1. Buscamos los dos menores árboles en la lista, en este caso se encuentran en las posiciones 7 y 8. La imagen debajo muestra dos flechas apuntando a estos árboles. En este caso min1 = 3 y min2 = 4
Paso 2. Creamos un nuevo árbol cuya raíz tiene un valor igual a min1 + min2 = 7 y cuyos hijos son los árboles min1 y min2.
Paso 3. Eliminamos los árboles de las posiciones 7 y 8 e insertamos el nuevo árbol creado en la lista.
Iteración 4
Paso 1. Buscamos los dos menores árboles en la lista, en este caso se encuentran en las posiciones 1 y 5. La imagen debajo muestra dos flechas apuntando a estos árboles. En este caso min1 = 4 y min2 = 4
Paso 2. Creamos un nuevo árbol cuya raíz tiene un valor igual a min1 + min2 = 8 y cuyos hijos son los árboles min1 y min2.
Paso 3. Eliminamos los árboles de las posiciones 1 y 5 e insertamos el nuevo árbol creado en la lista.
Iteración 5
Paso 1. Buscamos los dos menores árboles en la lista, en este caso se encuentran en las posiciones 7 y 8. La imagen debajo muestra dos flechas apuntando a estos árboles. En este caso min1 = 5 y min2 = 7
Paso 2. Creamos un nuevo árbol cuya raíz tiene un valor igual a min1 + min2 = 12 y cuyos hijos son los árboles min1 y min2.
Paso 3. Eliminamos los árboles de las posiciones 7 y 8 e insertamos el nuevo árbol creado en la lista.
Salida
Al final obtendremos un árbol como el de la siguiente imagen:
Los números intermedios no nos serán útiles por lo que resumimos el grafo con sólo caracteres como en la siguiente imagen:
Observemos que los caracteres que aparecen con mayor frecuencia aparecen más cerca de la raíz que los que tienen menor frecuencia. Por ejemplo, el carácter "o", que tiene la mayor frecuencia, está más cerca de la raíz que los otros caracteres.
Codificación
Una vez creado el árbol de codificación Huffman, la codificación es sencilla. A cada carácter se le asignará un número binario dependiendo de su posición en el árbol. Vamos a mostrar la codificación con un ejemplo para que se entienda mejor. La ruta para llegar de la raíz al carácter "r" es derecha-izquierda-derecha-derecha-izquierda; si concatenamos la ruta y cambiamos izquierda por cero y derecha por uno obtenemos que el código para "r" es 10110 (observa la siguiente imágen).
La siguiente tabla muestra los códigos Huffman para cada carácter del texto de ejemplo:
[color=#000000]carácter Huffman
y 11110
o 00
110
c 100
m 11111
p 010
r 10110
e 10111
a 011
s 1110
, 10100
g 101010
u 101011[/color]
Observa que el caracter que se repite más (o) tiene una menor cantidad de bits, mientras que los caracteres que menos se repiten (u y g) tienen una mayor cantidad de bits. Ahora la cadena "copas" se codifica como
100000100111110
Ahora la cadena "copas" pesa 15 bits. El tamaño total del archivo de ejemplo viene dado por la suma #bits*frecuencia
Ahora el archivo pesa 279/8 = 34.9 bytes; el tamaño original del archivo era 94 bytes por lo que se ha logrado que el archivo se comprima al 34.9/94 = 37.1% del archivo original.
Además del archivo codificado, es necesario tener el árbol de codificación de Huffman para poder decodificarlo, por lo que el peso del archivo final pesará un poco más que 34.9 bytes.
Decodificación
La decodificación es muy sencilla. Sólo necesitaremos leer bit por bit e ir avanzando por el árbol de acuerdo al bit leído: si el bit es un cero, se avanza por la rama izquierda y si el bit es un uno se avanza por el lado derecho hasta encontrar una hoja, en cuyo caso tendremos el carácter decodificado; luego de decodificar un carácter se reinicia la ruta a seguir desde la raíz del árbol.
Por ejemplo para decodificar la secuencia de bits "100001111100" leemos bit por bit de izquierda a derecha:
- Leemos el primer bit (1): avanzamos por la derecha comenzando por la raíz.
- Leemos el segundo bit (0): avanzamos por la izquierda desde el punto anterior.
- Leemos el tercer bit (0): avanzamos por la izquierda desde el punto anterior. Se ha encontrado una hoja por lo que el carácter decodificado es "c" (se reinicia la ruta desde la raíz).
- Leemos el cuarto bit (0): avanzamos por la izquierda comenzando por la raíz.
- Leemos el quinto bit (0): avanzamos por la izquierda desde el punto anterior. Se ha encontrado una hoja por lo que el carácter decodificado es "o" (se reinicia la ruta desde la raíz)
La cadena "100001111100" decodificado es "como".