Codificación de Shannon-Fano

En el campo de la compresión de datos, la codificación Shannon-Fano, llamada así por Claude Shannon y Robert Fano, es un nombre dado a dos técnicas diferentes pero relacionadas para construir un código de prefijo basado en un conjunto de símbolos y sus probabilidades (estimadas o medidas).

• El método de Shannon elige un código prefijo donde un símbolo fuente ${displaystyle i}$ se da la longitud de la palabra clave ${displaystyle l_{i}=lceil -log ¿Qué?$. Una forma común de elegir las palabras clave utiliza la expansión binaria de las probabilidades acumulativas. Este método fue propuesto en la "Teoría Matemática de Comunicación" de Shannon (1948), su artículo introduciendo el campo de la teoría de la información.
• Método de Fano divide los símbolos fuente en dos sets ("0" y "1") con probabilidades lo más cercanas a 1/2 posible. Entonces esos conjuntos están divididos en dos, y así sucesivamente, hasta que cada conjunto contiene sólo un símbolo. La palabra clave para ese símbolo es la cadena de "0"s y "1"s que registra la mitad de las divisiones que cayó. Este método fue propuesto en un informe técnico posterior por Fano (1949).

Los códigos de Shannon-Fano son subóptimos en el sentido de que no siempre logran la longitud de palabra de código esperada más baja posible, como lo hace la codificación de Huffman. Sin embargo, los códigos de Shannon-Fano tienen una longitud de palabra de código esperada dentro de 1 bit del óptimo. El método de Fano generalmente produce codificación con longitudes esperadas más cortas que el método de Shannon. Sin embargo, el método de Shannon es más fácil de analizar teóricamente.

La codificación Shannon-Fano no debe confundirse con la codificación Shannon-Fano-Elias (también conocida como codificación Elias), la precursora de la codificación aritmética.

Nombramiento

Con respecto a la confusión en los dos códigos diferentes a los que se hace referencia con el mismo nombre, Krajči et al escriben:

Alrededor de 1948, tanto Claude E. Shannon (1948) como Robert M. Fano (1949) propusieron independientemente dos algoritmos de codificación de fuentes diferentes para una descripción eficiente de una fuente discreta sin memoria. Lamentablemente, a pesar de ser diferente, ambos esquemas se hicieron conocidos bajo el mismo nombre Codificación Shannon-Fano.

Hay varias razones para esta mezcla. Por un lado, en la discusión de su esquema de codificación, Shannon menciona el esquema de Fano y lo llama “sustancialmente el mismo” (Shannon, 1948, p. 17). Para otro, los esquemas de codificación de Shannon y Fano son similares en el sentido de que ambos son eficientes, pero suboptimal esquemas de codificación sin prefijo con un rendimiento similar

El método de Shannon (1948), que utiliza longitudes de palabra predefinidas, se denomina codificación Shannon-Fano por Cover y Thomas, Goldie y Pinch, Jones y Jones, y Han y Kobayashi. Yeung lo llama codificación de Shannon.

El método de Fano (1949), que utiliza la división binaria de probabilidades, se denomina codificación de Shannon-Fano por Salomon y Gupta. Se llama codificación Fano por Krajči et al.

Código de Shannon: longitudes de palabra predefinidas

Algoritmo de Shannon

El método de Shannon comienza decidiendo la longitud de todas las palabras clave, luego elige un código de prefijo con esas longitudes de palabra.

Dada una fuente con probabilidades ${displaystyle P_{1},p_{2},dotsp_{n}$ las longitudes de la palabra clave deseadas son ${displaystyle l_{i}=lceil -log ¿Qué?$. Aquí, ${displaystyle lceil xrceil }$ es la función del techo, que significa el entero más pequeño mayor o igual a ${displaystyle x}$.

Una vez que se han determinado las longitudes de las palabras en clave, debemos elegir las propias palabras en clave. Un método consiste en elegir palabras clave en orden desde los símbolos más probables a los menos probables, eligiendo cada palabra clave como la primera palabra lexicográficamente de la longitud correcta que mantiene la propiedad libre de prefijos.

Un segundo método hace uso de probabilidades acumulativas. Primero, las probabilidades están escritas en orden decreciente ${displaystyle p_{1}geq p_{2}geq cdots geq p_{n}$. Entonces, las probabilidades acumulativas se definen como

${displaystyle c_{1}=0,qquad C_{i}=sum - ¿Por qué?$

Así que... ${displaystyle c_{1}=0,c_{2}=p_{1},c_{3}=p_{1}+p_{2}$ y así sucesivamente. La palabra clave para el símbolo ${displaystyle i}$ es elegido para ser el primero ${displaystyle l_{i}$ dígitos binarios en la expansión binaria de ${displaystyle C_{i}$.

Ejemplo

Este ejemplo muestra la construcción de un código Shannon-Fano para un alfabeto pequeño. Hay 5 símbolos de fuente diferentes. Supongamos que se han observado 39 símbolos en total con las siguientes frecuencias, a partir de las cuales podemos estimar las probabilidades de los símbolos.

Signatura	A	B	C	D	E
Conde	15	7	6	6	5
Probabilidad	0,385	0.179	0.154	0.154	0.128

Esta fuente tiene entropía ${displaystyle H(X)=2.186}$ bits.

Para el código Shannon-Fano, necesitamos calcular las longitudes de la palabra deseadas ${displaystyle l_{i}=lceil -log ¿Qué?$.

Signatura	A	B	C	D	E
Probabilidad	0,385	0.179	0.154	0.154	0.128
${displaystyle -log ¿Qué?$	1.379	2.480	2.700	2.700	2.963
Longitudes de palabras ${displaystyle lceil -log ¿Qué?$	2	3	3	3	3

Podemos elegir palabras clave en orden, eligiendo lexicográficamente la primera palabra de la longitud correcta que mantiene la propiedad libre de prefijos. Claramente, A obtiene la palabra clave 00. Para mantener la propiedad libre de prefijos, la palabra clave de B puede no comenzar con 00, por lo que la primera palabra lexicográficamente disponible de longitud 3 es 010. Continuando así, obtenemos el siguiente código:

Signatura	A	B	C	D	E
Probabilidad	0,385	0.179	0.154	0.154	0.128
Longitudes de palabras ${displaystyle lceil -log ¿Qué?$	2	3	3	3	3
Codewords	00	010	011	100	101

Alternativamente, podemos usar el método de probabilidad acumulada.

Signatura	A	B	C	D	E
Probabilidad	0,385	0.179	0.154	0.154	0.128
Probabilidades acumulativas	0,000	0,385	0.564	0,7818	0.872
...en binario	0,00000	0,01100	0.10010	0.10110	0.11011
Longitudes de palabras ${displaystyle lceil -log ¿Qué?$	2	3	3	3	3
Codewords	00	011	100	101	110

Tenga en cuenta que, aunque las palabras clave de los dos métodos son diferentes, la longitud de las palabras es la misma. Tenemos longitudes de 2 bits para A y 3 bits para B, C, D y E, dando una longitud promedio de

${displaystyle {frac {2,{text{bits}cdot (15)+3,{text{bits}cdot (7+6+6+5)}{39,{text{symbols}}}approx 2.62,{text{bits per symbol,}}}}}}}$

que está dentro de un bit de la entropía.

Longitud de palabra esperada

Para el método de Shannon, la longitud de las palabras satisface

${displaystyle l_{i}=lceil -log ¿Por qué? - ¿Qué?$

Por lo tanto, la longitud de palabra esperada satisface

${displaystyle mathbb {E} L=sum ¿Qué? sum ¿Qué? - ¿Qué? ¿Por qué? - ¿Qué? ¿Por qué?$

Aquí, ${displaystyle H(X)=-textstyle sum ¿Por qué? ¿Qué?$ es la entropía, y el teorema de codificación fuente de Shannon dice que cualquier código debe tener una longitud promedio de al menos ${displaystyle H(X)}$. Por lo tanto vemos que el código Shannon-Fano está siempre dentro de un poco de la longitud de palabra óptima esperada.

Código de Fano: división binaria

Esquema del código de Fano

En el método de Fano, los símbolos se ordenan de más probable a menos probable y luego se dividen en dos conjuntos cuyas probabilidades totales son lo más cercanas posible a ser iguales. Todos los símbolos tienen asignados los primeros dígitos de sus códigos; los símbolos en el primer conjunto reciben "0" y los símbolos del segundo conjunto reciben "1". Mientras queden juegos con más de un miembro, se repite el mismo proceso en esos juegos para determinar los dígitos sucesivos de sus códigos. Cuando un conjunto se ha reducido a un símbolo, esto significa que el código del símbolo está completo y no formará el prefijo de ningún otro código de símbolo.

El algoritmo produce codificaciones de longitud variable bastante eficientes; cuando los dos conjuntos más pequeños producidos por una partición tienen, de hecho, la misma probabilidad, el único bit de información utilizado para distinguirlos se utiliza con mayor eficacia. Desafortunadamente, la codificación de Shannon-Fano no siempre produce códigos de prefijo óptimos; el conjunto de probabilidades {0,35, 0,17, 0,17, 0,16, 0,15} es un ejemplo de uno al que se le asignarán códigos no óptimos mediante la codificación de Shannon-Fano.

La versión de Fano de la codificación Shannon-Fano se utiliza en el método de compresión IMPLODE, que forma parte del formato de archivo ZIP.

El árbol Shannon-Fano

Un árbol de Shannon-Fano se crea de acuerdo con una especificación diseñada para definir una tabla de códigos efectiva. El algoritmo real es simple:

1. Para una lista dada de símbolos, desarrollar una lista correspondiente de probabilidades o recuentos de frecuencia para que se conozca la frecuencia relativa de cada símbolo.
2. Clasifique las listas de símbolos según la frecuencia, con los símbolos más frecuentes en la izquierda y el menos común a la derecha.
3. Divide la lista en dos partes, con los recuentos de frecuencia total de la parte izquierda estando tan cerca del total de la derecha como sea posible.
4. La parte izquierda de la lista se asigna el dígito binario 0, y la parte derecha se asigna el dígito 1. Esto significa que los códigos para los símbolos en la primera parte comenzarán con 0, y los códigos en la segunda parte comenzarán con 1.
5. Aplicar Recursivamente los pasos 3 y 4 a cada una de las dos mitades, subdividir grupos y añadir bits a los códigos hasta que cada símbolo se haya convertido en una hoja de código correspondiente en el árbol.

Ejemplo

Shannon–Fano Algorithm

Seguimos con el ejemplo anterior.

Signatura	A	B	C	D	E
Conde	15	7	6	6	5
Probabilidad	0,385	0.179	0.154	0.154	0.128

Todos los símbolos están ordenados por frecuencia, de izquierda a derecha (como se muestra en la Figura a). Poner la línea divisoria entre los símbolos B y C da como resultado un total de 22 en el grupo de la izquierda y un total de 17 en el grupo de la derecha. Esto minimiza la diferencia en los totales entre los dos grupos.

Con esta división, A y B tendrán cada uno un código que comienza con un bit 0, y los códigos C, D y E comenzarán todos con un 1, como se muestra en la Figura b. Posteriormente, la mitad izquierda del árbol obtiene una nueva división entre A y B, lo que coloca A en una hoja con el código 00 y B en una hoja con el código 01.

Después de cuatro procedimientos de división, resulta un árbol de códigos. En el árbol final, a los tres símbolos con las frecuencias más altas se les han asignado códigos de 2 bits, y dos símbolos con recuentos más bajos tienen códigos de 3 bits, como se muestra en la siguiente tabla:

Signatura	A	B	C	D	E
Probabilidad	0,385	0.179	0.154	0.154	0.128
Primera división	0		1
Segunda división	0	1	0	1
Tercera división				0	1
Codewords	00	01	10	110	111

Esto da como resultado longitudes de 2 bits para A, B y C y de 3 bits para D y E, dando una longitud promedio de

${displaystyle {frac {2,{text{bits}cdot (15+7+6)+3,{text{bits}}cdot (6+5)}{39,{text{symbols}}}approx 2.28,{text{bits per symbol.}}}}}}}}}$

Vemos que el método de Fano, con una longitud media de 2,28, ha superado al método de Shannon, con una longitud media de 2,62.

Longitud de palabra esperada

Se muestra por Krajči et al que la longitud esperada del método de Fano ha esperado la longitud ligada arriba por ${displaystyle mathbb Lleq H(X)+1-p_{ min}$, donde ${displaystyle p_{text{min}=textstyle min ¿Qué?$ es la probabilidad del símbolo menos común.

Comparación con otros métodos de codificación

Ni el algoritmo Shannon-Fano está garantizado para generar un código óptimo. Por esta razón, los códigos Shannon–Fano casi nunca se utilizan; la codificación Huffman es casi tan computacionalmente simple y produce códigos prefijos que siempre alcanzan la longitud de palabra de código más baja posible, bajo las restricciones que cada símbolo está representado por un código formado por un número integral de bits. Esta es una limitación que a menudo no es necesaria, ya que los códigos serán empaquetados de extremo a extremo en largas secuencias. Si consideramos grupos de códigos a la vez, la codificación de símbolo por símbolo Huffman sólo es óptima si las probabilidades de los símbolos son independientes y son algo de poder de media, es decir, ${displaystyle textstyle 1/2^{k}$. En la mayoría de las situaciones, la codificación aritmética puede producir mayor compresión general que Huffman o Shannon-Fano, ya que puede codificar en números fraccionados de bits que más cerca aproximan el contenido de información real del símbolo. Sin embargo, la codificación aritmética no superó a Huffman de la manera en que Huffman superó a Shannon–Fano, tanto porque la codificación aritmética es más costosa computacionalmente y porque está cubierta por múltiples patentes.

Codificación Huffman

Unos años más tarde, David A. Huffman (1949) proporcionó un algoritmo diferente que siempre produce un árbol óptimo para las probabilidades de cualquier símbolo dado. Mientras que el árbol Shannon-Fano de Fano se crea dividiendo desde la raíz hasta las hojas, el algoritmo de Huffman funciona en la dirección opuesta, fusionando desde las hojas hasta la raíz.

1. Crear un nodo de hoja para cada símbolo y añadirlo a una cola de prioridad, utilizando su frecuencia de ocurrencia como prioridad.
2. Mientras hay más de un nodo en la cola:
   1. Quitar los dos nodos de menor probabilidad o frecuencia de la cola
   2. Prependiendo 0 y 1 respectivamente a cualquier código ya asignado a estos nodos
   3. Cree un nuevo nodo interno con estos dos nodos como niños y con probabilidad igual a la suma de las probabilidades de los dos nodos.
   4. Añadir el nuevo nodo a la cola.
3. El nodo restante es el nodo raíz y el árbol está completo.

Ejemplo con codificación Huffman

Huffman Algorithm

Usamos las mismas frecuencias que en el ejemplo anterior de Shannon-Fano, a saber:

Signatura	A	B	C	D	E
Conde	15	7	6	6	5
Probabilidad	0,385	0.179	0.154	0.154	0.128

En este caso D & E tiene las frecuencias más bajas, por lo que se les asignan 0 y 1 respectivamente y se agrupan con una probabilidad combinada de 0,282. El par más bajo ahora es B y C, por lo que se asignan 0 y 1 y se agrupan con una probabilidad combinada de 0,333. Esto deja a BC y DE ahora con las probabilidades más bajas, por lo que se anteponen 0 y 1 a sus códigos y se combinan. Esto deja solo A y BCDE, que tienen 0 y 1 antepuestos respectivamente y luego se combinan. Esto nos deja con un solo nodo y nuestro algoritmo está completo.

Las longitudes de código para los diferentes caracteres esta vez son 1 bit para A y 3 bits para todos los demás caracteres.

Signatura	A	B	C	D	E
Codewords	0	100	101	110	111

Esto da como resultado longitudes de 1 bit para A y de 3 bits para B, C, D y E, dando una longitud promedio de

${displaystyle {frac {1,{text{bit}cdot 15+3,{text{bits}cdot (7+6+6+5)}{39,{text{symbols}}}approx 2.23,{text{bits per symbol.}}}}}}}}$

Vemos que el código Huffman ha superado a ambos tipos de código Shannon-Fano, que esperaba longitudes de 2,62 y 2,28.