Codificación Shannon – Fano - Shannon–Fano coding

En el campo de la compresión de datos , la codificación Shannon-Fano , que lleva el nombre de Claude Shannon y Robert Fano , es un nombre que se le da 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 de prefijo donde un símbolo fuente recibe la longitud de la palabra de código . Una forma común de elegir las palabras de código utiliza la expansión binaria de las probabilidades acumuladas. Este método fue propuesto en " A Mathematical Theory of Communication " de Shannon (1948), su artículo que presenta el campo de la teoría de la información .${\ Displaystyle i}$${\ Displaystyle l_ {i} = \ lceil - \ log _ {2} p_ {i} \ rceil}$
• El método de Fano divide los símbolos fuente en dos conjuntos ("0" y "1") con probabilidades lo más cercanas a 1/2 como sea posible. Luego, esos conjuntos se dividen en dos, y así sucesivamente, hasta que cada conjunto contenga solo un símbolo. La palabra clave para ese símbolo es la cadena de "0" sy "1" que registra en qué mitad de las divisiones cayó. Este método fue propuesto en un informe técnico posterior de Fano (1949).

Los códigos de Shannon-Fano son subóptimos en el sentido de que no siempre alcanzan la longitud de palabra de código más baja posible esperada, como lo hace la codificación de Huffman . Sin embargo, los códigos 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 .

Nombrar

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 de forma independiente dos algoritmos de codificación de fuentes diferentes para una descripción eficiente de una fuente discreta sin memoria. Desafortunadamente, a pesar de ser diferentes, ambos esquemas se conocieron con el mismo nombre de codificación Shannon-Fano .

Hay varias razones para esta confusión. 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). Por otro lado, los esquemas de codificación de Shannon y Fano son similares en el sentido de que ambos son esquemas de codificación eficientes, pero subóptimos , sin prefijo y con un rendimiento similar.

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

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

Código de Shannon: longitudes de palabras predefinidas

Algoritmo de Shannon

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

Dada una fuente con probabilidades, las longitudes de palabras de código deseadas son . Aquí, está la función de techo , es decir, el número entero más pequeño mayor o igual a . ${\ Displaystyle p_ {1}, p_ {2}, \ dots, p_ {n}}$${\ Displaystyle l_ {i} = \ lceil - \ log _ {2} p_ {i} \ rceil}$${\ Displaystyle \ lceil x \ rceil}$${\ 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 seleccionar las palabras de código en orden de los símbolos más probables a los menos probables, eligiendo cada palabra de código para que sea lexicográficamente la primera palabra de la longitud correcta que mantiene la propiedad libre de prefijo.

Un segundo método utiliza probabilidades acumuladas. Primero, las probabilidades se escriben en orden decreciente . Entonces, las probabilidades acumuladas se definen como ${\ Displaystyle p_ {1} \ geq p_ {2} \ geq \ cdots \ geq p_ {n}}$

${\ Displaystyle c_ {1} = 0, \ qquad c_ {i} = \ sum _ {j = 1} ^ {i-1} p_ {i} {\ text {for}} i \ geq 2,}$

así y así sucesivamente. La palabra de código para símbolo se elige para que sea el primer dígito binario en la expansión binaria de . ${\ Displaystyle c_ {1} = 0, c_ {2} = p_ {1}, c_ {3} = p_ {1} + p_ {2}}$${\ Displaystyle i}$${\ Displaystyle l_ {i}}$${\ 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. Suponga 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.

Símbolo	A	B	C	D	mi
Contar	15	7	6	6	5
Probabilidades	0.385	0,179	0,154	0,154	0,128

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

Para el código Shannon-Fano, necesitamos calcular las longitudes de palabra deseadas . ${\ Displaystyle l_ {i} = \ lceil - \ log _ {2} p_ {i} \ rceil}$

Símbolo	A	B	C	D	mi
Probabilidades	0.385	0,179	0,154	0,154	0,128
${\ Displaystyle - \ log _ {2} p_ {i}}$	1.379	2.480	2.700	2.700	2.963
Longitudes de palabras ${\ Displaystyle \ lceil - \ log _ {2} p_ {i} \ rceil}$	2	3	3	3	3

Podemos elegir palabras de código en orden, eligiendo la primera palabra lexicográficamente de la longitud correcta que mantiene la propiedad libre de prefijo. Claramente, A obtiene la palabra de código 00. Para mantener la propiedad libre de prefijo, la palabra de código 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:

Símbolo	A	B	C	D	mi
Probabilidades	0.385	0,179	0,154	0,154	0,128
Longitudes de palabras ${\ Displaystyle \ lceil - \ log _ {2} p_ {i} \ rceil}$	2	3	3	3	3
Palabras en clave	00	010	011	100	101

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

Símbolo	A	B	C	D	mi
Probabilidades	0.385	0,179	0,154	0,154	0,128
Probabilidades acumuladas	0.000	0.385	0.564	0,718	0,872
... en binario	0,00000	0.01100	0.10010	0.10110	0.11011
Longitudes de palabras ${\ Displaystyle \ lceil - \ log _ {2} p_ {i} \ rceil}$	2	3	3	3	3
Palabras en clave	00	011	100	101	110

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

${\ Displaystyle {\ frac {2 \, {\ text {bits}} \ cdot (15) +3 \, {\ text {bits}} \ cdot (7 + 6 + 6 + 5)} {39 \, { \ text {símbolos}}}} \ approx 2.62 \, {\ text {bits por símbolo,}}}$

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

Longitud esperada de la palabra

Para el método de Shannon, las longitudes de las palabras satisfacen

${\ Displaystyle l_ {i} = \ lceil - \ log _ {2} p_ {i} \ rceil \ leq - \ log _ {2} p_ {i} +1.}$

Por lo tanto, la longitud esperada de la palabra satisface

${\ Displaystyle \ mathbb {E} L = \ sum _ {i = 1} ^ {n} p_ {i} l_ {i} \ leq \ sum _ {i = 1} ^ {n} p_ {i} (- \ log _ {2} p_ {i} +1) = - \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2} p_ {i} + \ sum _ {i = 1} ^ {n} p_ {i} = H (X) +1.}$

Aquí está 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 . Por lo tanto, vemos que el código Shannon-Fano siempre está dentro de un bit de la longitud de palabra óptima esperada. ${\ Displaystyle H (X) = - \ textstyle \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2} p_ {i}}$${\ Displaystyle H (X)}$

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 están lo más cerca posible de ser iguales. A todos los símbolos se les asignan los primeros dígitos de sus códigos; los símbolos del primer conjunto reciben "0" y los símbolos del segundo conjunto reciben "1". Mientras permanezcan conjuntos con más de un miembro, se repite el mismo proceso en esos conjuntos 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 del código de ningún otro 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 bit de información usado para distinguirlos se usa de manera más eficiente. Desafortunadamente, la codificación 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 Shannon-Fano.

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

El árbol de Shannon-Fano

Un árbol Shannon-Fano se construye 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, desarrolle una lista correspondiente de probabilidades o recuentos de frecuencia para que se conozca la frecuencia relativa de ocurrencia de cada símbolo.
2. Ordene las listas de símbolos según la frecuencia, con los símbolos que aparecen con más frecuencia a la izquierda y los menos comunes a la derecha.
3. Divida la lista en dos partes, con el recuento total de frecuencias de la parte izquierda lo más cercano posible al total de la derecha.
4. A la parte izquierda de la lista se le asigna el dígito binario 0, y a la parte derecha se le 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 empezar con 1.
5. Aplique de manera recursiva los pasos 3 y 4 a cada una de las dos mitades, subdividiendo grupos y agregando bits a los códigos hasta que cada símbolo se convierta en una hoja de código correspondiente en el árbol.

Ejemplo

Continuamos con el ejemplo anterior.

Símbolo	A	B	C	D	mi
Contar	15	7	6	6	5
Probabilidades	0.385	0,179	0,154	0,154	0,128

Todos los símbolos están ordenados por frecuencia, de izquierda a derecha (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 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, que pone A en una hoja con código 00 y B en una hoja con 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 tabla a continuación:

Símbolo	A	B	C	D	mi
Probabilidades	0.385	0,179	0,154	0,154	0,128
Primera Division	0		1
Segunda División	0	1	0	1
Tercera división				0	1
Palabras en clave	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, lo que da una longitud promedio de

${\ Displaystyle {\ frac {2 \, {\ text {bits}} \ cdot (15 + 7 + 6) +3 \, {\ text {bits}} \ cdot (6 + 5)} {39 \, { \ text {símbolos}}}} \ approx 2.28 \, {\ text {bits por símbolo.}}}$

Vemos que el método de Fano, con una longitud promedio de 2.28, ha superado al método de Shannon, con una longitud promedio de 2.62.

Longitud esperada de la palabra

Krajči et al muestran que la longitud esperada del método de Fano tiene la longitud esperada acotada arriba por , donde es la probabilidad del símbolo menos común. ${\ Displaystyle \ mathbb {E} L \ leq H (X) + 1-p _ {\ text {min}}}$${\ Displaystyle p _ {\ text {min}} = \ textstyle \ min _ {i} p_ {i}}$

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

Ninguno de los algoritmos de 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 de Huffman es casi tan simple desde el punto de vista computacional y produce códigos de prefijo que siempre logran la menor longitud de palabra de código esperada posible, bajo las restricciones de que cada símbolo está representado por un código formado por un número entero de bits. Esta es una restricción que a menudo no es necesaria, ya que los códigos se empaquetarán de extremo a extremo en secuencias largas. Si tenemos en cuenta los grupos de códigos a la vez, símbolo a símbolo codificación Huffman sólo es óptima si las probabilidades de los símbolos son independientes y son algo de poder de un medio, es decir, . En la mayoría de las situaciones, la codificación aritmética puede producir una mayor compresión general que Huffman o Shannon-Fano, ya que puede codificar en números fraccionarios de bits que se aproximan más al contenido de información real del símbolo. Sin embargo, la codificación aritmética no ha reemplazado a Huffman de la forma en que Huffman reemplaza a Shannon-Fano, tanto porque la codificación aritmética es más costosa computacionalmente como porque está cubierta por múltiples patentes. ${\ Displaystyle \ textstyle 1/2 ^ {k}}$

Codificación Huffman

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

1. Cree un nodo hoja para cada símbolo y agréguelo a una cola de prioridad , utilizando su frecuencia de aparición como prioridad.
2. Si bien hay más de un nodo en la cola:
   1. Eliminar de la cola los dos nodos de menor probabilidad o frecuencia
   2. Anteponer 0 y 1 respectivamente a cualquier código ya asignado a estos nodos
   3. Cree un nuevo nodo interno con estos dos nodos como hijos y con una probabilidad igual a la suma de las probabilidades de los dos nodos.
   4. Agregue 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

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

Símbolo	A	B	C	D	mi
Contar	15	7	6	6	5
Probabilidades	0.385	0,179	0,154	0,154	0,128

En este caso, D y E tienen las frecuencias más bajas y, por lo tanto, se asignan 0 y 1 respectivamente y se agrupan con una probabilidad combinada de 0,282. El par más bajo ahora son 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 0 y 1 se anteponen 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.

Símbolo	A	B	C	D	mi
Palabras en clave	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, lo que da una longitud promedio de

${\ Displaystyle {\ frac {1 \, {\ text {bit}} \ cdot 15 + 3 \, {\ text {bits}} \ cdot (7 + 6 + 6 + 5)} {39 \, {\ text {símbolos}}}} \ approx 2.23 \, {\ text {bits por símbolo.}}}$

Vemos que el código Huffman ha superado a ambos tipos de código Shannon-Fano, que tenía longitudes esperadas de 2.62 y 2.28.

Notas

Referencias

• Fano, RM (1949). "La transmisión de información" . Informe técnico No. 65 . Cambridge (Mass.), Estados Unidos: Laboratorio de investigación de electrónica del MIT.
• Shannon, CE (julio de 1948). "Una teoría matemática de la comunicación" . Revista técnica de Bell System . 27 : 379–423.