Codificación Shannon-Fano
Codificación Shannon-Fano, en el campo de la compresión de datos, la codificación Shannon-Fano es una técnica para construir un código prefijo basado en un conjunto de símbolos y sus probabilidades (estimadas o medidas). No es óptimo en el sentido de que no consigue la menor longitud de palabra código esperada posible como en la codificación Huffman; aunque a diferencia de la codificación Huffman, garantiza que todas las longitudes de palabras de código están a un bit de su ideal teórico – logP(x). La técnica fue propuesta por Claude Elwood Shannon, en “Una Teoría Matemática de la Comunicación”, su artículo de 1948 introduciendo el campo de la teoría de la información. El método fue atribuido a Robert Fano, quien posteriormente lo publicó como un informe técnico. La codificación Shannon-Fano no debe confundirse con la codificación Shannon, método de codificación usado para probar el teorema de Shannon de la codificación sin ruido, ni con la codificación Shannon-Fano-Elias (también conocida como codificación Elias), el precursor de la codificación aritmética.
En la codificación Shannon-Fano, los símbolos se ordenan del más al menos probable, y se dividen en dos subconjuntos cuyas probabilidades totales son tan próximas a ser iguales como sea posible. A continuación todos los símbolos tendrán el primer dígito de sus códigos asignados; los del primer subconjunto recibirán el “0” y los del segundo el “1”. Mientras exista algún subconjunto con más de un término, se repetirá el mismo proceso para determinar los sucesivos dígitos de sus códigos. Cuando uno de los subconjuntos ha sido reducido a un símbolo, esto significa que el código del símbolo es completo y que no formará el prefijo del código de ningún otro símbolo.
El algoritmo funciona, y produce codificaciones de longitud variable bastante eficientes; cuando los dos subconjuntos producidos por una división tienen la misma probabilidad, ya que el bit de información usado para distinguirlos se usa más eficientemente.
Desafortunadamente, Shannon-Fano no produce siempre códigos prefijos óptimos; el conjunto de probabilidades {0.35, 0.17, 0.17, 0.16, 0.15} es un ejemplo de esto.
Por esta razón, Shannon-Fano apenas se usa; la codificación Huffman es casi tan computacionalmente simple y produce códigos prefijos que siempre consiguen la menor longitud esperada de palabra de código, bajo la restricción de que cada símbolo es representado por un código formado por un número integral de bits. Esta es una restricción a menudo innecesaria, ya que los códigos serán empaquetados de un extremo a otro en largas secuencias. I consideramos grupos de códigos en un instante, símbolo a símbolo la codificación Huff solo es óptima si las probabilidades de que los símbolos sean independientes y están elevadas a un medio, p.e., 21/2. En la mayoría de las situaciones, la codificación aritmética puede producir mayor compresión general que Huffman o que Shannon-Fano, ya que puede codificar en números fraccionarios de bits, más cercanos al contenido real de información de cada símbolo. Sin embargo, la codificación aritmética reemplazado a la de Huffman de la manera que esta sobrepasa a Shannon-Fano, ya que la codificación aritmética es más costosa computacionalmente y porque está sujeta a múltiples patentes.
La codificación Shannon-Fano se usa en el método de compresión IMPLODE, que es parte del formato de los archivos ZIP.
El algoritmo Shannon-Fano
Un árbol Shannon-Fano se construye de acuerdo a una especificación diseñada para definir una tabla de códigos efectiva. El algoritmo actual es simple:
- Para una lista de símbolos dada, crear su correspondiente lista de probabilidades o de frecuencias de aparición de manera que se conozca la frecuencia relativa de ocurrencia de cada símbolo.
- Ordenar las listas de símbolos de acuerdo a la frecuencia, con los símbolos de ocurrencia más frecuente a la izquierda y los menos comunes a la derecha.
- Dividir la lista en dos partes, haciendo la frecuencia total de la mitad izquierda lo más próxima posible a la de la mitad derecha.
- Asignar a la mitad izquierda el dígito binario “0”, y a la mitad derecha el dígito “1”. Esto significa que los códigos para los símbolos en la primera mitad empezarán con “0”, y que los códigos de la segunda mitad empezarán por “1”.
- Aplicar recursivamente los pasos 3 y 4 a cada una de las dos mitades, subdividiéndolas en grupos y añadiendo bits a los códigos hasta que cada símbolo se corresponde con una hoja del árbol.
Ejemplo
El ejemplo muestra la construcción de un código Shannon para un pequeño alfabeto. Los cinco símbolos que pueden ser codificados tienen la siguiente frecuencia.
| Símbolo | A | B | C | D | E |
|---|---|---|---|---|---|
| Frecuencia | 15 | 7 | 6 | 6 | 5 |
Todos los símbolos son ordenados por frecuencia, de izquierda a derecha. Dividiendo entre B y C obtenemos un total de 17 en el grupo de la derecha y 22 en el de la izquierda. Esto minimiza la diferencia total entre los dos grupos. Con esta división, A y B tendrán ambas un código que empezará con el bit 0, y C, D y E con el bit 1. Seguidamente, la mitad izquierda del árbol se subdivide en A y B, lo que pone a A en una hoja con el código 00 y a B en otra con el código 01. Tras cuatro divisiones, terminamos el árbol de códigos. Al final, los símbolos del árbol con frecuencias más altas tienen todos códigos de 2 bits, y los otros dos símbolos con menor frecuencia tienen códigos de 3 bits, como se ve en la tabla inferior.
| Símbolo | A | B | C | D | E |
|---|---|---|---|---|---|
| Código | 00 | 01 | 10 | 110 | 111 |
Notas
Este artículo es una traducción parcial de "Shannon-Fano coding", encontrado en Wikipedia English
Referencias
- C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379-423, July 1948.
- R.M. Fano, "The transmission of information", Technical Report No. 65, 1949. Research Laboratory of Electronics, M.I.T., Cambridge (Mass.), USA.