heh! nº1:(0x002):06/01/2000 << Back To heh! nº 1
Compresion de Datos. No se si te pasa como a mi, me encanta saber como funcionan las cosas que uso por eso intento aprender como trabajan. Con este proposito, vamos a ver que procesos utiliza una forma de las tantas formas de comprimir informacion, muy efectiva con texto. Recuerdo que mi primer intento de compresor fue un metodo que consistia en tomar de un archivo, cadenas de caracteres que se repetian por todo el archivo y sustituirlos por un caracter que no esta en el archivo sustituyendo 3 o 4 caracteres por 1. Claro esta, cuando el archivo es de texto es facil, los espacios en blanco abundan, pero los archivos con un formato diferente es mas dificil de encontrar una cadena adecuada y un caracter que la sustituya. Todo esto sin comentar las veces que al descomprimir estos archivos quedaban inservibles. Pasemos al metodo de Huffman. Cuando comienzas a entender como aplicar arboles binarios, este metodo lo reinventa cada estudiante, pero resulta que al amigo Huffman se le ocurrio primero. El metodo consiste en construir un codigo de prefijos optimo, y ustedes diran que carajo es esto?. (cuanto mas optimo quede este codigo el resultado de la compresion sera mejor). Bueno comencemos Daremos un ejemplo que mostrara el funcionamiento del proceso Elijo una frase cualquiera: MI MAMA ME AMA A MI Esta cadena de caracteres tiene 18 bytes contando los espacios en blanco. (Simbolizaremos estos como: " ") El primer paso debera ser tomar cada caracter y ver cuantas veces se repite en la cadena. En este caso : M = 6 , I = 2, A = 5, E = 2, " " = 5. Ordenamos de menor a mayor. Si los valores se repiten es valido poner cualquier caracter antes. á I E A " " M * * * * * 2 2 5 5 6 á Sumo los dos mas chicos 4 / \ * * * * * 2 2 5 5 6 Reordeno y repito el proceso 9 / \ á*á * * * 4 5 5 6 / \ * * 2 2 Repito el proceso. Sumo los 2 mas chicos 11 / \ * * * 5 6 9 / \ á*á * 4 5 / \ * * 2 2 Reordeno Sumo los 2 mas chicos. 20á / \ * * 9 11 / \ / \ á*á * * * 4 5 5 6 / \ * * 2 2 Se habran dado cuenta que se ha formado un arbol binario. Las hojas de este arbol son los valores de frecuencia de cada caracter. Ahora cuando la rama va hacia la derecha coloco valor 1, a la izquierda 0. Quedando el valor de I llendo desde la raiz 000 I = 000 E = 001 A = 01 M = 11 " " = 10 Se ha generado un codigo de prefijos optimo. El siguiente paso es con la igualdad del codigo de prefijos transformar la frase a binario. á Raφz 20á 0/ \1 / \ * * * * 0/ \1 0/ \1 9 11 á*á = = = / \ / \ 0/ \1 A " " M á*á = = = = = 4 5 5 6 I E / \ = = 2 2 Ahora tomando de ocho estos 0 y 1 podemos transformar a un numero entre 0 y 255 con un equivalente en ASCII. Como veran hemos reducido de 18 bytes a 6 bytes. M I " " M A M A " " M E " " A M A " " A " " M I 11 000 10 11 01 11 01 10 11 001 10 01 11 01 10 01 10 11 000 11000101 10111011 01100110 01110110 01101100 0 197 187 102 118 108 0 Cambiando estos valores por sus correspondientes en ASCII, tendran el texto comprimido de 6 bytes. Muy bonito. Observaciones Este es una compresion optima porque el arbol es optimo si cambiamos de lugar la M por la I en el arbol, el codigo de la M pasa a tener 3 caracteres entonces la frase quedara mas larga y ocupara mas de 6 bytes. Considerando que tambien hay que guardar el codigo de prefijos en este caso el resultado final sera mayor que 18 bytes, ( prueba comprimir un archivo que ocupe 1 byte con pkzip ), pero cuando comprimes un volumen de informacion mayor esto no sucede y la compresion es muy buena. Despedida Espero que este articulo les agrade, y toda esta teoria les ense#e algo, en el proximo numero veremos la TAD (tipos abstractos de datos) y su implementacion para la codificacion de este algoritmo. Joe joe_joe@i.com.uy