| Artículos | 01 MAY 2000

Técnicas de compresión sin pérdida (y II)

Tags: Histórico
Nobu Yamazaki.
Continuamos con el funcionamiento de los algoritmos de compresión que iniciáramos el pasado mes. En esta entrega veremos los mecanismos de las codificaciones Huffman y LZW.

El pasado mes iniciábamos un estudio de las técnicas de compresión, con la descripción de los algoritmos más básicos. Nos centrábamos únicamente en la codificación RLE, analizando sus cuatro esquemas de compresión posibles. Para terminar con las técnicas de compresión sin pérdidas, esto es, las que permiten una recuperación completa de la información al descomprimir, veremos el funcionamiento de las codificaciones Huffman y LZW, mas avanzadas y por tanto ampliamente utilizadas en la práctica.

Codificación Huffman
Este método debe su nombre a la persona que inventó el algoritmo, en el año 1952 y combina unos esquemas de funcionamiento tanto estáticos, (que se repiten siempre) como dinámicos, (que se van amoldando según los datos que estemos comprimiendo).
Este sistema permite utilizar simultáneamente los esquemas estadísticos dinámicos y estáticos. Un esquema estadístico trabaja sobre las ocurrencias de todos los datos. No es como con el algoritmo RLE donde teníamos que considerar la ocurrencia actual de un búffer sino más bien tendríamos que tener una consideración de las ocurrencias globales de todos los datos a comprimir. En este último caso, se puede utilizar cualquier tipo de cadenas que nosotros queramos. Por otro lado, la codificación estática Huffman se utiliza en algún compresor como el ARJ. Con estos esquemas, el codificador debe considerar para todos los datos el mismo valor estadístico.
Evidentemente, los resultados no son tan buenos como si estuviéramos aplicando una codificación dinámica.
La codificación estática es más rápida que la dinámica, pero ésta se adapta en cada caso a la estadística de los bytes de los datos a comprimir, obteniendo de esta manera una salida más optimizada y comprimida que de ninguna otra manera.
La idea principal de la codificación Huffman, es la de recodificar cada byte con respecto a sus ocurrencias. A la hora de comprimir los bytes más frecuentes los sustituiremos por códigos de menos de 8 bits y para comprimir los otros bytes, los que menos se repitan, utilizaremos códigos de más de 8 bits.
Se puede apreciar muy claramente que los códigos asociados a los diferentes bytes no tienen porqué tener un tamaño idéntico. El método de Huffman realmente requiere que los códigos binarios no tengan un tamaño fijo. Nosotros hablamos entonces de códigos de longitud inconstantes.
Los esquemas dinámicos de Huffman necesitan utilizar árboles binarios para la codificación. Esto le permite obtener los códigos más adecuados, optimizado para cada diferente tipo de datos.
Pero no vamos a hacer ninguna demostración todavía. Para ayudar el neófito, explicaremos antes de nada qué es un árbol binario. Se trata de una manera especial de representar datos. Un árbol binario es una estructura con un valor asociado con dos indicadores. El término de binario tiene se dado debido a la presencia de dos indicadores. Debido a algunas convenciones, el primer indicador es el izquierdo y el segundo indicador es el derecho. Puede ver una representación gráfica de un árbol binario en la figura 3.
Un problema con una codificación binaria es el del prefijo. Un prefijo es la primera parte de la representación de un valor, por ejemplo “h” y “ho” son prefijos de “hola” pero no “ol”. para entender el problema, codifiquemos las cartas “A”, “B”, “C”, “D”, y “E” respectivamente como 00b, 01b, 10b, 11b, y 100b. Cuando leamos la secuencia binaria 00100100b, seremos incapaces de decir si viene de “ACBA” o de “AEE”. Para evitar esas situaciones, los códigos deben tener un prefijo, que indique cuándo comienza un carácter.
Y la letra “E” no debe empezar con la secuencia de otro código. Con “A”, “B”, “C”, “D”, y “E” respectivamente codificados como 1b, 01b, 001b, 0001b, y 0000b, la sucesión 1001011b sólo se puede descifrar como “ACBA.”
Como podemos observar en el árbol de la figura 4, una codificación tendrá la propiedad del prefijo si los bytes están al final de cada “rama” y si no tenemos ningún byte en el “nodo.” También podemos ver que si intentamos alcanzar un carácter por el indicador derecho, le agrega un bit a 0 y si lo intentamos por el indicador izquierdo, agregaremos un bit a 1 al actual código. La codificación errónea vista anteriormente, proporcionará el consiguiente árbol erróneo, mostrado en la figura 5.
Como se puede observar, el codificador no debería haber puesto una “C” en el nodo. Los códigos binarios más largos son aquellos que tengan la distancia mayor desde la cima del árbol al carácter que representa. Consecuentemente, los bytes más frecuentes deberán de ser los más altos del árbol para que de esa manera les asignemos las codificaciones más cortas y los bytes menos frecuentes serán los más bajos en el árbol.
Desde un punto de vista del algoritmo, haremos una lista con cada byte que encontremos en el flujo de datos a comprimir. Esta lista habrá que ordenarla siempre. Los bytes con cero ocurrencias serán quitados de esta lista. Entonces tomamos los dos bytes con el menor número de ocurrencias en la lista. Siempre que dos bytes tengan el mismo “peso” (ocurrencias), tomaremos cualquiera de ellos independientemente de su valor ASCII. Entonces los unimos en un nodo. Este nodo va a tener un valor de byte ficticio (256 puede ser un valor bueno para este ejemplo) y su peso será la suma de los dos bytes que hemos unido. A continuación reemplazamos de la lista los dos bytes que hemos unido entonces con el byte ficticio. Y continuamos repitiendo el proceso hasta que sólo tengamos un byte (ficticio o no) en la lista. Por supuesto, este proceso nos habrá servido para determinar los códigos más cortos para el caso que hayamos tratado en concreto. No entraremos en oscuros detalles matemáticos, para explicar porqué el resultado nos da la codificación más corta posible.
Importante: generalmente suele utilizarse como convención que los sub-árboles derechos tengan un peso mayor o iguala al peso de los sub-árboles izquierdos.
Como ejemplo, tomemos un archivo para comprimir, del cual obtenemos las ocurrencias indicadas en la tabla 8.
Empezaremos uniendo los bytes 83 y 222. Esto producirá un nodo ficticio que numeraremos como 1 (1 es un valor que no está siendo usado) con un peso de 20+5=25. (Figura 6 y tabla 9)
Nos tenemos que fijar de que la lista está ordenada. Ahora los valores de las frecuencias más bajas son 21 y 24. Por eso cogemos los bytes 77 y 115 para crear el nodo ficticio 2. (Figura 7 y tabla 10)
Los nodos con menos peso ahora son los ficticios 1 y 2. Estos se juntan para formar el nodo ficticio 3, cuyo peso es 40+25=70. (Figura 8 y tabla 11)
El nodo ficticio 3 se junta con el byte 31. Peso total: 280+70=350. (Figura 9 y tabla 12)
Como se puede observar, el nodo ficticio 4 se ha puesto el primero en la lista. Ahora unimos los bytes 0 y 255 en el nodo ficticio 5, con un peso

Contenidos recomendados...

Comentar
Para comentar, es necesario iniciar sesión
Se muestran 0 comentarios
X

Uso de cookies

Esta web utiliza cookies técnicas, de personalización y análisis, propias y de terceros, para facilitarle la navegación de forma anónima y analizar estadísticas del uso de la web. Consideramos que si continúa navegando, acepta su uso. Obtener más información