Download Compresión de Datos

Compresión de Datos
Método de Huffman
Manipulación y Preservación de Datos
Dpto. Informática
Ing. Mariano D'Agostino
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
Introducción
La compresión de datos es el proceso de convertir una cadena de datos de entrada
(la cadena fuente o los datos originales a tratar), en otra cadena de datos (la salida,
la cadena de bits, o la cadena comprimida), que tenga un tamaño más pequeño.
La compresión de datos es popular por dos razones: En primer lugar, a la gente le
gusta acumular datos y odia tirar cualquier cosa. No importa cuánta capacidad tenga
un dispositivo de almacenamiento, tarde o temprano va a desbordarse. La
compresión de datos, parece útil, ya que retrasa lo inevitable. En segundo lugar la
gente odia esperar mucho tiempo en las transferencias de datos. Cuando se está
sentado frente a una computadora, esperando la carga de una página Web o la
llegada de un archivo, sentimos de forma natural, que cualquier cosa que dure más
que unos pocos segundos, es un largo tiempo de espera.
Hay muchos métodos conocidos para la compresión de datos. Están basados en
ideas diferentes, apropiadas para distintos tipos de datos, y producen diferentes
resultados; pero todos se basan en el mismo principio, comprimen eliminando la
redundancia de los datos originales del archivo de fuente. Cualquier dato no
aleatorio posee alguna estructura, la cual puede ser aprovechada para lograr una
representación más pequeña de los datos; en esta nueva estructura, al parecer no
hay ningún patrón identificable.
En un texto típico en castellano, por ejemplo, la letra E es muy frecuente, mientras
que la K, aparece raramente. Esto se llama redundancia alfabética, y sugiere la
asignación de códigos de tamaño variable a las letras; asociando con E, el código
más corto, y con K, el más largo. Otro tipo de redundancia, la redundancia de
contexto, se ilustra por el hecho de que la letra Q, es casi siempre previa a la letra
U. La redundancia en las imágenes se ilustra por el hecho de que, en una imagen
no aleatoria, píxeles adyacentes tienden a tener colores similares.
La idea de comprimir reduciendo la redundancia, sugiere la ley general de la
compresión de datos, que consiste en “asignar códigos cortos para los eventos
comunes (símbolos o frases) y códigos largos para los eventos raros”. Hay muchas
maneras de aplicar esta ley y un análisis de cualquier método de compresión
muestra que, en el fondo, funciona obedeciendo a la ley general.
El código ASCII para caracteres, es un buen ejemplo de representación de datos
más larga de lo necesario. Utiliza códigos de 7 bits, porque es fácil trabajar con
códigos de tamaño fijo. Un código de tamaño variable, sin embargo, sería más
eficiente, ya que algunos caracteres se usan más que otros, y así, se podrían
asignar códigos más cortos.
El método de huffman
Huffman es un método de codificación ampliamente conocido. La idea de la
codificación Huffman es comprimir el texto asignando códigos más cortos a los
1
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
símbolos más frecuentes. Se ha probado que el algoritmo de Huffman obtiene, para
un texto dado, una codificación optima de prefijo libre.
Una codificación se denomina de prefijo libre (o código instantáneo) si no produce
ningún código que sea prefijo de otro código. Un código de prefijo libre puede ser
decodificado sin necesidad de comprobar códigos futuros, dado que el final de un
código es inmediatamente reconocible. En los últimos años se han desarrollado
nuevas técnicas de compresión especialmente indicadas para su aplicación sobre
textos en lenguaje natural.
La codificación Huffman es un método muy valorado para la compresión de datos.
Sirve como base para varios programas populares que se ejecutan en diversas
plataformas. Algunos de ellos, utilizan sólo el método de Huffman, mientras que en
otros, forma parte de un proceso de compresión de varios pasos.
A continuación veremos un ejemplo completo de como emplear el método huffman
para comprimir un texto. Luego veremos el mecanismo para descomprimirlo y
obtener el texto original.
Comprimir textos usando el método de Huffman
El método de Huffman para comprimir texto se resume en los siguiente pasos.
•
Contar cuantas ocurrencias de cada caracter hay en el texto.
•
Construir un árbol que combine los diferentes caracteres.
•
Utilizando las ramas del árbol generar un nuevo código para cada caracter.
•
Reemplazar cada caracter del texto original por el nuevo código.
Para hacer más claro este procedimiento, utilicemos un ejemplo paso a paso.
Supongamos que tenemos la siguiente frase: ella regresa a casa.
El primer paso del método indica que hay que contar cuantas ocurrencias hay de
cada caracter.
Lo que nos da la siguiente tabla.
2
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
A continuación, se procede a construir un árbol. Para simplificar la construcción, el
árbol se dibujará de abajo invertido, o sea, con la raíz hacia arriba y las hojas hacia
abajo, pero esta elección de ninguna manera impacta en el resultado final.
El primer paso consiste en colocar cada una de los caracteres en la base, junto con
su frecuencia, ordenados de menor a mayor, como indica la siguiente figura:
Luego, se combinan dos de los caracteres que sumen la menor cifra.
En este caso, las dos hojas que sumadas dan el menor resultado son la C y la G
con una unidad cada una.
La suma de las ocurrencias de los dos caracteres da como resultado un nuevo
nodo en el árbol.
3
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
El procedimiento anterior se vuelve a repetir hasta que se lleguen a unificar todos
los caracteres en un único nodo. Para este caso, la siguiente suma puede ser la
letra L con el nodo GC, que da como resultado un nuevo nodo con valor 4.
Después, la menor suma posible que se puede obtener es sumar S y R cada una
con un valor de 2.
4
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
Luego, y aquí hay que tener especial cuidado, la siguiente suma involucra a los
caracteres A y el espacio (representado con un guión bajo), ya que sumar 3 a
cualquiera de los otros dos nodos de valor 4 daría como resultado 7, y sumar 3 + 3
da una suma menor de valor 6.
Como vimos anteriormente los nodos tienen que combinarse para formar nuevos
nodos hasta que solo quede uno solo. El valor del nodo raíz (el nodo superior) debe
ser igual a la cantidad de caracteres del texto original. Esto es una forma simple de
controlar si se hicieron correctamente las sumas de todos los nodos inferiores.
Siguiendo el mismo procedimiento, el árbol terminado queda de esta forma.
5
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
Cada linea que une un nodo con otro nodo se denomina rama del árbol. El siguiente
paso consiste en colocar un cero, en las ramas izquierdas del árbol, y un uno en las
ramas derechas. Y con esto concluye la construcción del árbol.
6
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
El tercer paso del método dice: "Utilizando las ramas del árbol generar un nuevo
código para cada caracter". Esto se logra de la siguiente forma.
Recorriendo el árbol desde el nodo superior (el nodo raíz) hacia cada una de las
hojas, encontraremos una secuencia de unos y ceros que serán los nuevos códigos
de cada caracter.
Por ejemplo, para la letra A, el código se obtiene recorriendo el árbol de esta forma:
7
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
Por lo tanto el código para la letra A es: 00.
Para la letra E el código sería 001
8
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
Y para la letra C el código sería 1110
Recorriendo todos los caminos posibles obtenemos la siguiente tabla de códigos:
9
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
El último paso consiste en reemplazar cada uno de los caracteres del texto original
por su nueva representación. Recordar que si utilizáramos ASCII, ISO-8859-1 o
UTF-8 para codificar el texto anterior, cada caracter tendría un byte de longitud, esto
es 8 bits. Ahora, cada caracter tiene un código más corto, y aquellos caracteres que
más se repiten tienen una longitud menor.
El texto original en ASCII sería el siguiente:
10
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
Reemplazando cada caracter por su nuevo código obtenemos la siguiente cadena
de unos y ceros.
Como puede observarse, hay una reducción notable en la cantidad de bits utilizados
para escribir el mismo mensaje. En esto consiste la compresión utilizando el método
Huffman, en utilizar códigos más cortos, para los caracteres que más
frecuentemente aparecen en el texto.
11
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
Descompresión de textos codificados con el método
Huffman
Conociendo los nuevos códigos para cada caracter, es evidente que la
transformación de binario a su formato original es muy simple. Básicamente se van
leyendo los ceros y uno de derecha a izquierda hasta encontrar un código válido, en
ese momento estamos en condiciones de decodificar un nuevo caracter.
El problema es que se plantea ahora es, de que manera enviar junto con el
mensaje, los códigos nuevos para cada caracter, de esta forma al leer un mensaje
comprimido, tendríamos también tendríamos también los códigos para
descomprimirlo.
Hay que tener en cuenta que una cadena de ceros y unos codificada con el método
de Huffman puede tener distintos significados dependiendo de los códigos que se
utilicen para descomprimirlo, por eso es tan importante adjuntar al mensaje
comprimido la secuencia nueva de códigos, sino, sería imposible determinar el
mensaje original.
Una forma simple de enviar los nuevos códigos junto con el mensaje comprimido es
enviar la estructura del árbol generado en el paso de compresión. Navegando el
árbol es posible deducir los nuevos códigos de cada caracter y por lo tanto obtener
el mensaje original.
Veremos entonces de que manera se puede adjuntar la estructura del árbol al
mensaje comprimido.
Codificar el árbol de Huffman
El método para convertir un árbol de Huffman en una secuencia de ceros y unos
consiste en utilizar una búsqueda llamada primero en profundidad. En este tipo de
búsquedas, un árbol se va navegando primero hasta llegar a una hoja, y luego se
vuelve hacia atrás solo lo suficiente para poder seguir bajando hasta otra hoja.
Veamos este procedimiento con un ejemplo, utilizando el mismo árbol generado
para el texto “ella regresa a casa”
12
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
Comenzando desde la raíz, navegamos el árbol hasta el final. Por cada nodo que
encontremos, colocaremos un cero en una lista. Cuando encontremos una hoja,
colocaremos un uno y a continuación el valor del caracter que encontramos en la
hoja.
Luego, volvemos hacia atrás en nuestro recorrido. Como el nodo superior ya fue
13
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
visitado no escribimos ningún cero, y ahora bajamos hacia la derecha, hacia la la
siguiente hoja, donde escribimos otro uno y el valor del caracter que encontramos
en la hoja.
Habiendo completado toda la rama, volvemos hacia atrás hasta que encontremos
otro nodo que no haya sido procesado.
14
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
El proceso continúa hasta que todas las hojas del árbol hayan sido procesadas. Por
cada nodo que no se haya visitado, se escribe un cero, por cada hoja, se escribe un
uno y el valor del caracter.
El árbol codificado de esta forma tiene la característica que es posible de decodificar
siguiendo la secuencia de ceros y unos y dibujando los nodos y hojas. Además, es
seguro adjuntarlo al mensaje original, ya que queda perfectamente delimitado
cuando finaliza el árbol de cuando comienza el mensaje comprimido (esto se debe a
que el árbol es un árbol binario, en donde cada nodo tiene solo dos ramas, y
visualmente es claro que ya no pueden agregarse más hojas al mismo).
El proceso completo de codificar todo el árbol se ilustra en la siguiente imagen. Los
puntos negros indican la primera vez que se visitó un nodo o una hoja, y el valor que
se imprime al visitarlo. Debajo de la imagen se observa como se codifica todo el
árbol usando una serie de unos y ceros.
15
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
Decodificando un árbol codificado
El proceso de decodificación de una cadena de un árbol codificado consiste en ir
leyendo uno a uno los bits de la cadena y dibujar un nodo o una hoja según
encontremos un uno y un cero.
Primero se completan las ramas de la izquierda, y luego de la derecha. Si leemos la
cadena 001A, dibujaremos un nodo, luego a la izquierda otro nodo y finalmente en
la rama izquierda de este último nodo, dibujamos una hoja con valor A.
16
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
Primero se completan las ramas de la izquierda, y luego de la derecha. Si leemos la
cadena 001A, dibujaremos un nodo, luego a la izquierda otro nodo y finalmente en
la rama izquierda de este último nodo, dibujamos una hoja con valor A.
A continuación, seguimos leyendo la secuencia, completando la rama derecha del
último nodo que hayamos dibujado. La cadena sigue con 01_1E, lo que significa que
debemos dibujar primero un nodo, a su izquierda una hoja con valor espacio en
blanco y a su derecha otra hoja con valor E.
17
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
Cada vez que encontremos una secuencia de 01A1B donde A y B son dos letras
cualquiera, implica dibujar un nodo con dos hojas, A y B.
Como mencionamos varios párrafos atrás, el árbol binario se termina de dibujar sin
ambigüedades. Cuando se llega a dibujar la última hoja no es posible seguir
agregando más elementos al árbol (debido a que las hojas no tienen ramas), y por
lo tanto es posible empezar a decodificar el resto del mensaje comprimido.
18
MANIPULACIÓN Y PRESERVACIÓN DE DATOS
TÉCNICO EN INFORMÁTICA PROFESIONAL Y PERSONAL
El proceso de descompresión completo
Leyendo una cadena de unos y ceros comprimida con el método Huffman implica
construir un árbol con la primera sección, una vez construido el árbol es posible
obtener los patrones de reemplazo de cada carácter. Con estos patrones de
reemplazo se continua leyendo la cadena de unos y ceros para ir detectando cada
carácter codificado y de esta forma obtener el mensaje original.
Bibliografía
•
D. Salomon (2014) Compresión de datos. La referencia completa.
•
N. Brisaboa y otros. Compresión de textos en Bases de Datos Digitales.
19