Como ya se ha dicho, la codificación consiste en reducir el coste de los elementos que se emplean más a menudo, castigando con un mayor lo más inhabitual.

Por esta razón, lo primero que hay que hacer es ver qué es lo que más aparece. En nuestro caso debido a que lo que hay que transmitir no es muy grande se pueden contabilizar cada uno de los caracteres y ordenarlos según el número de apariciones. En ocasiones normales el orden de aparición estará predefinido por medio de leyes probabilísticas.

Pero a modo de ejemplo e imaginando que queremos transmitir la frase "Transmitir un mensaje", la tabla del número de apariciones por carácter que obtenemos es la siguiente:

Una vez que ya tenemos ordenados los caracteres según la probabilidad de aparición, comienzan las operaciones recursivas.

Como primer paso debemos crear una tabla en cuya primera columna copiaremos la columna "VECES" de la tabla de arriba, tal cual como está.

 

Aunque en todos los casos hay que seguir el mismo proceso, el número de operaciones a efectuar estará determinado por el modo de transmisión que vayamos a emplear ( binario, ternario, cuaternario ...). Aunque el modo de transmisión más habitual es el binario, esto es, a base de "1"s "0"s, para no eternizarnos con la explicación utilizaré un modo de transmisión cuaternario, esto es, empleando 4 estados (0, 1, 2 y 3). Esto se puede conseguir en la realidad empleando, por ejemplo, dos líneas en paralelo sincronizadas, dando valor "2" ó "0" a una de las líneas y "1" ó "0" a la otra.

Aunque ahora no entenderás por qué hacemos el siguiente paso, te adelanto que vamos a seguir un proceso de reducción en el que queremos conseguir que al final del proceso queden un número de elementos igual al número de estados posible del modo de transmisión empleado (en éste caso 4 estados posibles), a los que asignaremos un valor de 0, 1, 2 ó 3. Además, en cada una de las operaciones recursivas de reducción, por cada cuatro elementos que cogemos obtenemos un valor de salida. Por lo tanto, si al final quiero tener cuatro elementos y en cada paso cojo cuatro y obtengo uno, tendré que empezar cogiendo tres elementos, como podrás ver y entender mejor con la siguiente figura.

 

}

Ahora que sabemos por dónde empezar, podemos empezar a reducir.

La reducción consiste en que, empezando por el grupo que menos aparece (el grupito de tres elementos de la parte de abajo de tabla de arriba), sumamos sus valores y, a continuación, ordenamos el valor que obtenemos con el resto de valores que quedan de la columna inmediatamente anterior, ordenándolas por filas de mayor a menor. Este proceso se repetirá recursivamente hasta que terminemos teniendo cuatro elementos  en una columna determinada.

La siguiente figura creo que explicará mejor el proceso.

 

 

A los valores situados en la última columna les asignaremos un determinado estado (en éste caso 0, 1, 2 y 3), y, a partir de ahí, hacemos el camino de vuelta respecto a la tabla anterior. Los valores que asignemos a cada una de las filas en cada paso se conservan en las filas anteriores, y, si una fila está formada por la suma de varias, éstas columnas conservarán lo asignado al sumando añadiéndosele detrás otro carácter más (de la misma forma que se hace en la última columna).

Como ésto así es difícil de explicar, confío en que me ayude el siguiente gráfico. 

 

Y ya está todo hecho. Ahora no tenemos más que asignar a cada carácter, el código que le corresponde según la columna CÓDIGO del paso 1 correspondiente. .

En nuestro caso queda la relación es:

Por lo tanto, la salida "Transmitir un mensaje" quedaría como " 13 00 01 2 02 03 10 30 10 00 11 31 2 11 03 12 2 02 01 32 12 "

¿ He mejorado mucho respecto a emplear código ASCII normal? Pues haciendo cuentas podemos ver que hemos pasado de tener que emplear 147 bits en el caso del código ASCII a tener usar sólo 39 en éste caso.

Otra pregunta que nos podemos hacer es: ¿Es éste un buen algoritmo de compresión? Para justificar la respuesta voy a emplear aquél concepto que nombré antes, la llamada entropía y que definía la longitud media de código mínima necesaria para poder transmitir un mensaje sin perder información y que, éste sí es el momento para decirlo, su fórmula es igual a:

La expresión matemática se puede traducir como:

  - Por cada uno de los tipos de carácter que aparece en el texto, tengo que hallar el logaritmo en base orden del código de la inversa del valor de la probabilidad de que aparezca en el texto ése carácter.

- El valor obtenido de hallar el logaritmo, lo multiplico por la probabilidad de aparición de ése carácter.

- Estos dos pasos los tengo que hacer por cada uno de los tipos de carácter que aparecen en el texto y al final sumo todos los valores obtenidos.

Comparando la longitud media de código obtenida con el algoritmo, respecto la entropía y la longitud media de código ASCII tengo que:

 

LONGITUD MEDIA DE CÓDIGO
ENTROPIA HUFFMAN ASCII
1.74961 1.85714 7

Por lo tanto se ve que el código obtenido que es mucho mejor que el ASCII, y que el margen de mejora no es excesivo.

Y aquí se acaba todo el misterio.

Si quieres comprobar si has entendido el proceso, te puedes bajar un programilla que consiste en introducir un texto, y él calcula el " código óptimo" empleando Huffman, dando ófreciendo también como resultado los valores de entropía y longitud media de código generado.

ó sino, por lo menos espero que la página te haya servido de ayuda ó al menos para satisfacer tu curiosidad.

 

Jon Xabier Arza Olano