--------------------------------------------------------------------------- Compresión. Algunos conceptos y el método de Huffman. por Tony Vera Díaz --------------------------------------------------------------------------- + Algunos conceptos anticonceptivos+ ------------------------------------ Información: la representaremos como una variable (X) capaz de tomar ciertos valores. Por ejemplo, si pienso con quien me lo montaría yo ahora, pues podría tomar los siguientes valores: {con tu abuela, con tu prima, con tu novia, con tus hermanas, contigo} Modelo de incertidumbre: la incertidumbre es el grado de desconocimiento que se tiene sobre los valores que puede tomar la variable información. Medimos la incertidumbre mediante la ENTROPÍA. n H(x) = -E Pi*log2(Pi) i=1 Eso de ahí arriba es: menos Sumatorio de pé sub i por logaritmo en base dos de pé sub i desde i igual a uno hasta n. (la Pi no es PI, es la variable P con el subíndice i, que quede claro). 'n' es el número de posibles valores que pueda tomar x. 'Pi' es la posibilidad de que pase el valor n, que va desde 0 (nunca) hasta 1 (siempre). Pi es igual a los casos favorables divididos entre el total de casos. O sea, que si hay diez posibilidades de que me lo monte con tu abuela, cinco con tu prima, cientro veintiocho de que me lo haga con tus hermanas y quinientas contigo, tenemos que en total son seiscientas cuarenta y tres casos, y para saber el Pi de el caso uno, por ejemplo, tendríamos que dividir diez entre seiscientas cuarenta y tres. + Codificación + ---------------- Hay que definir un conjunto de símbolos al que llamaremos alfabeto. Cada uno de los valores que puede tomar X se llamará mensaje. A cada mensaje se le asocia una secuencia de símbolos del alfabeto, a lo que llamaremos palabra. Y al conjunto de palabras, código. Hay diferentes tipos de códigos: Según el número de elementos del alfabeto: Binario, Ternario, Parvulario, etc... Según la longitud de la palabra: Uniforme: Todos tienen la misma longitud (como el ASCII). No uniforme: diferente longitud (como el MORSE). Según su traducción: Única: codificamos: a = 000 e = 001 i = 010 o = 011 u = 100 no única: codificamos: a = 0 e = 01 i = 11 o = 1 u = 10 así que si ponemos 0010 podría interpretarse: aaoa, aea, aau. Se dice que un código es instantáneo cuando ninguna palabra es prefijo de otra. Un código uniforme es instantáneo. Todo código instantáneo es de traducción única. Nos podemos encontrar a la hora de codificar que hay o no información adicional (saber o no qué codificamos). Sin información adicional: Suponemos 'm' el número de mensajes a codificar, 'k' la longitud de palabra y 'd' el número de símbolos del alfabeto. m: lo conocemos, (ej: nuestro alfabeto tiene 28 símbolos) k: (es igual o menor el logaritmo en base 'd' de 'm', o que 'd' elevado a 'k' es mayor o igual a 'm') d: lo conocemos (tipo de código, binario, etc...) Disponemos de información: Nos encontramos con Pi; el sumatorio de todas las Pi debe de ser igual a 1. Definimos la longitud media de palabra como: _ n n = E Pi*ni i=1 ni = longitud de cada una de las palabras. Un código instantáneo es óptimo cuando su longitud media sea la menor posible de todos los códigos instantáneos que se le puedan asociar. + Método de Huffman para encontrar código instantáneo y óptimo + ---------------------------------------------------------------- Ordenamos los mensajes por orden decreciente de probabilidades. Atribuimos como último símbolo el 0 al mensaje Xn-1 y como símbolo 1 al mensaje Xn. Reagrupamos los dos últimos mensaejs en uno nuevo, cuya probabilidad será la sumba de la de ambos. Reordenamos el conjunto por orden de probabilidades. Volvemos al paso segundo hasta que sólo quede un elemento en el conjunto. Ejemplo: X Pi --- --- 0 = 0.05 1 = 0.1 2 = 0.025 3 = 0.025 4 = 0.2 5 = 0.1 6 = 0.1 7 = 0.1 8 = 0.1 9 = 0.2 Reordenamos según Pi, y agrupamos: 4 9 1 5 6 7 8 0 2 3 | | 0\___/1 0\___/1 | | 0\___/1 -> (esto ya vale 0.5) | 0\____/1 | | 0\___/1 -> (vale 0.1) 1\_____/0 | 0\_____/1 -> (vale 0.2) | 0\_______/1 0\_________________/1 | V Ahora seguimos el caminito tomando nota de los 0 y 1 para determinar los códigos: 0 = 1110 1 = 0010 2 = 11110 3 = 11111 4 = 01 etc... Pues eso es todo. Con el nuevo código te encuentras con que usas menos bits para representar lo mismo, así que ocupa menos. Eso sí, habrá que guardar la tabla.