Siguiente: Primeras listas Arriba: Códigos de Huffman Anterior: Códigos de Huffman terciarios,

Estimativo probabilista de la longitud de código

Dada una palabra $\sigma\in A^*$, la frecuencia $f(a) = \frac{c_{\sigma}(a)}{\mbox{\rm\scriptsize long}(\sigma)}$ de un símbolo $a\in A$ puede identificarse como la probabilidad de que ocurra $a$. Si $\ell_a\in\mathbb{N}$ es la longitud del código de $a\in A$ entonces la longitud esperada del código de Huffman es

$$E(\ell) = \sum_{a\in A}\ell_af(a) = \frac{1}{\mbox{\rm\scriptsize long}(\sigma)}\sum_{a\in A}\ell_ac_{\sigma}(a).$$

Escribamos $p_a=f(a)$.

La función de entropía $H:\mathbb{R}^*\to\mathbb{R}$ se define de manera que cumpla con las propiedades siguientes:

Positiva.

$\forall p_1,\ldots,p_n$: $H\left(p_1,\ldots,p_n\right)\geq 0$.

Contínua.

$\left(p_1,\ldots,p_n\right)\mapsto H\left(p_1,\ldots,p_n\right)$ es contínua.

Simétrica.

$\forall p_1,\ldots,p_n$, $\forall \pi\in S_n$ : $H\left(p_1,\ldots,p_n\right) = H\left(p_{\pi(1)},\ldots,p_{\pi(n)}\right)$.

Coherente.

$\forall p_1,p_2,\ldots,p_n$: $H\left(p_1,p_2,\ldots,p_n\right) = H\left(p_1+p_2,\ldots,p_n\right) + \left(p_1+p_2\right)H\left(\frac{p_1}{p_1+p_2},\frac{p_2}{p_1+p_2},\ldots,p_n\right)$.

Para esto se debe tener que existe $C>0$ tal que

$$\forall p_1,\ldots,p_n: \ \ H\left(p_1,\ldots,p_n\right) = C \sum_{i=1}^n p_i \log \frac{1}{p_i}$$

donde se ha de entender: $\left[p=0\ \Rightarrow\ p \log \frac{1}{p}=0.\right]$. Al expresar $C=\left(\log c\right)^{-1}$, se ha de tener

$$H\left(p_1,\ldots,p_n\right) = \sum_{i=1}^n p_i \log_c \frac{1}{p_i} = -\sum_{i=1}^n p_i \log_c p_i.$$ (6)

Esta última expresión define la llamada entropía de Shannon, considerando $c=2$. Para el caso $n=2$, la relación (6) queda

$$\forall p\in[0,1]:\ H(p,1-p) = -p\log_2p-(1-p)\log_2(1-p).$$

Esta función es tal que $H([0,1]) = [0,1]$, posee sus valores mínimos en $p=0,1$ (que una frecuencia sea 1 significa que en la cadena original sólo ha de aparecer un símbolo) y su valor máximo en $p=\frac{1}{2}$ (los símbolos que aparecen en la cadena original son equiprobables).

Sea ${\bf e}_i=\left(\delta_{ij}\right)_{j=1}^n$ el $i$-ésimo vector canónico que tiene el valor 1 en la $i$-ésima coordenada y el valor 0 en las otras. Este corresponde a la distribución de probabilidad en la que sólo aparece el $i$-ésimo símbolo y ninguno otro. Pues bien, de la relación (6) se ve que $H({\bf e}_i)=0$, lo que da una mínima entropía. Si se considera ${\bf f} = \frac{1}{n}\sum_{i=1}^n{\bf e}_i$, que corresponde a la distribución uniforme de probabilidad, se tiene $H({\bf f})=\log_2(n)$, lo que da una máxima entropía.

En la figura 1 presentamos las gráficas de $H$ para alfabetos de dos y de tres símbolos respectivamente.

Figura 1: Gráfica de la función de entropía de Shannon.

Dos símbolos
Tres símbolos

Supongamos que ${\bf p}=\left(p_j\right)_{j=1}^n$ es la distribución de probabilidad de un alfabeto $A$ de $n$ símbolos, y que ${\bf l}=\left(\ell_j\right)_{j=1}^n$ es la lista de longitudes de un código instantáneo de $A$. Entonces la longitud esperada ha de ser $E({\bf l}) = \sum_{j=1}^n \ell_jp_j = \sum_{j=1}^n p_j\log_2\left[2^{\ell_j}\right]$ y, en consecuencia

$$H({\bf p}) - E({\bf l}) = \sum_{j=1}^n p_j\log_2\left[\frac{1... ...\log 2}\sum_{j=1}^n p_j\log\left[\frac{1}{2^{\ell_j}p_j}\right]$$

de donde

$$H({\bf p}) - E({\bf l}) \leq \frac{1}{\log 2}\sum_{j=1}^n p_j... ...\frac{1}{\log 2}\left[\sum_{j=1}^n 2^{-\ell_j} -1\right] \leq 0$$

(donde la última es precisamente la desigualdad de Kraft). Así pues, $H({\bf p}) \leq E({\bf l})$, es decir la longitud esperada de cualquier código instantáneo es mayor o igual que la entropía de la distribución de probabilidad de los símbolos.

Para una distribución ${\bf p}=\left(p_j\right)_{j=1}^n$ de un alfabeto $A$ de $n$ símbolos y un entero positivo $k\in N$, se define la distribución ${\bf p}^k$ sobre el alfabeto $A^k$, que consiste de las palabras de longitud $k$, haciendo

$$\forall {\bf a}=a_{i_0}\cdots a_{i_{k-1}}\in A^k:\ \ p_{i_0\cdots i_{k-1}} = \prod_{\kappa=1}^k p_{i_{\kappa}}.$$

${\bf p}^k$ se dice ser la $k$-ésima extensión de ${\bf p}$.

Se tendrá entonces que vale el

Teorema 3.1 (de Shannon de Códigos sin Ruido)   Para cualquier distribución de probabilidad ${\bf p}$, sea $\ell_H({\bf p})$ la longitud esperada de una codificación de Huffman. Entonces

$$H({\bf p}) \leq \ell_H({\bf p}) \leq H({\bf p}) +1.$$

Y para extensiones sucesivas,

$$\lim_{k\to+\infty} \frac{1}{k}\ell_H({\bf p}^k) = H({\bf p}).$$

Planteemos un caso de estudio que se resolvería de manera directa utilizando el teorema de Shannon 3.1.

Ejemplo 3.2   Supongamos que se quiere transmitir un croquis. Este está conformado prácticamente por unas cuantas líneas sobre fondo blanco. Al digitalizar la imagen, la probabilidad de que aparezca un $1$ (pixel negro) es a lo sumo $p$ y de que aparezca $0$ (pixel blanco) es al menos $1-p$, con $p<10^{-2}$, digamos. El alfabeto original $A=\{0,1\}$ consta de dos símbolos. Para $k=10$, se divide la imagen en bloques de $k$ pixeles consecutivos. El alfabeto actual es entonces $A^k$. A toda cadena de ceros, $0^{(k)}$, se la codifica con un solo $0$, y a cualquier otra cadena $\sigma\in A^k$ con la cadena $1\sigma \in A^{k+1}$. ¿Cuál es la esperanza de la longitud del código?

La longitud esperada del código de una cadena $\tau\in A^k$ es

$$\begin{eqnarray*} E(\ell) &=& 1\cdot\,\mbox{\rm Prob}\,(\tau=0^{(k)}) + (1+k)\,\... ... &=& 1\cdot (1-p)^k + (1+k)(1-(1-p)^k) \\ &=& 1+k -k(1-p)^k, \end{eqnarray*}$$

así esta longitud será más cercana a 1 conforme $p$ sea más pequeño, o sea la compresión será mayor (de $k$ a 1). El teorema de Shannon 3.1 da la misma estimación de manera más directa y general.

Siguiente: Primeras listas Arriba: Códigos de Huffman Anterior: Códigos de Huffman terciarios,