Codificacion Shannon-Fano

Codificacion Shannon-Fano

Codificacion 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 sólo 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.


Contenido

El algoritmo Shannon-Fano

Archivo:Shannon–Fano-Coding.png
Algoritmo Shannon–Fano.

Un arbol Shannon-Fano se construye de acuerdo a una especificación diseñada para definir una tabla de códigos efectiva. El algoritmo actual es simplo:

1 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.

2 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.

3 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.

4 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”.

5 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

References

  • 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.

Véase también

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Codificación Huffman — Árbol de Huffman generado para las frecuencias de apariciones exactas del texto Esto es un ejemplo de árbol de Huffman . las frecuencias y códigos de cada carácter se muestran abajo. Codificar esta frase usando este código requiere 156 bits, sin… …   Wikipedia Español

  • Código prefijo — Un código prefijo es un código, típicamente un código de longitud variable, con la propiedad de prefijo : ninguna palabra de código es prefijo de cualquier otra palabra de código del conjunto. Un código con las palabras de código… …   Wikipedia Español

  • Formato de compresión ZIP — ZIP Desarrollador Phil Katz, PKWARE Información general …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”