Hablando de barcos, ¿os habéis fij…? Eeeehm. No, no era así.

Hablando de letras, ¿se han fijado en que en cualquier texto escrito en español, o en inglés, ya que estamos, la letra «E» aparece muchas más veces que la letra «Z»?

Quien si se fijó fue el inventor del código Morse, y lo aprovechó para reducir al máximo el número de símbolos que habría que transmitir en cada telegrama.

Lo que hizo Alfred Vail fue asignarle a las letras más comunes un código más corto (por ejemplo, la «E» es un solo punto, «dit») y a las menos comunes dejarles uno más largo (la «Z» tiene dos rayas y dos puntos, «dah dah dit dit»). De este modo, se realizan transmisiones más rápidas que si todas las letras tuvieran códigos de la misma longitud.

Esto se utiliza aún hoy en día en la informática y en las telecomunicaciones; sólo que en lugar de usar el código Morse de puntos y rayas, se utiliza el código binario de unos y ceros.

El asunto consiste en realizar un análisis estadístico de las frecuencias de aparición de los distintos símbolos que se quieren transmitir o almacenar, y a los más frecuentes asignarles códigos más cortos.

El truco para saber dónde empieza y dónde termina la representación de cada símbolo es muy sencillo: un código no puede ser el prefijo de otro código. Es decir, si tenemos un símbolo con código «101», no puede haber otro símbolo con un código que comience por «101». Así no hay dudas :-)

Si multiplicamos la frecuencia de aparición de cada símbolo por la longitud de su código, y sumamos estos productos, el resultado es la longitud media del código. Cuanto más se aproxime esta longitud media del código a la entropía del conjunto de símbolos, mejor. ¿Y qué es la entropía? Es la menor longitud media de símbolo que podemos obtener. La fórmula aparece debajo. ¿Les suena? ;-)

\[H = - \sum\limits_{i} (p_i \log_2 (p_i)) \]

El código Huffman es un código de longitud variable muy útil. Aparte de ser simple conceptualmente, permite hacer de forma sencilla búsquedas sobre textos comprimidos. También se usa en los ficheros JPEG, para almacenar un coeficiente (algunos coeficientes son mucho más comunes que otros…), y seguro que tiene muchas más utilidades…