En la codificación Huffman, ¿cómo se elige la frecuencia para obtener la máxima longitud media de bits?

Question

Primero quiero hacer un pequeño resumen sobre el código Huffmann para evitar malentendidos.

Comienza el resumen

Así que tenemos un alfabeto $A$ con $|A| > 1 $ . Por ejemplo $A$ = { $a,b,c,d,e$ }. Ahora numeramos las letras: $a=1,b=2,c=3,d=4,e=5$ .

Cada letra tiene una frecuencia. Así que tenemos un mapa $f : A \rightarrow [0,1]$ con $\sum_{a \in A} f(a) = 1$ . Por ejemplo $(1|0,2), (2|0,3), (3,|0,1), (4|0,35), (5|0,05)$ . Permítanme explicar mi notación: $(1|0,2)$ significa que la letra $a$ tiene frecuencia $0,2$ .

Así que el código Huffman nos dice que tomamos las dos letras con la menor frecuencia y las combinamos. Así obtenemos $(1|0,2), (2|0,3), (3,|0,15), (4|0,35)$ . Obtenemos :

Si repetimos este proceso obtendremos:

Así podemos calcular la ABL (Average Bit Length ):

$$ ABL(\gamma) = \sum_{a \in A} f(a) \cdot |\gamma(a)| $$

donde $\gamma$ es la longitud de la palabra clave. Por ejemplo $\gamma(e) = 4$ como puedes ver en mi segunda foto.

¿Alguna pregunta?

El resumen termina

Así que quiero obtener la máxima longitud media de bits. ¿Cómo tengo que elegir $f$ para un alfabeto $A$ con $|A| > 1$ ? He intentado muchas cosas como tomar la distribución uniforme $f(a) = \frac{1}{n}$ para todos $a \in A$ con $|A| = n$ . Pero esta y otras de mis ideas no han funcionado. ¿Pueden ayudarme? Actualización: Gracias a los comentarios que he recibido me he dado cuenta de que me he equivocado con la distribución uniforme. Así que podría ser que la distribución uniforme podría ser la solución.

Answer 1

El máximo se alcanza en la distribución uniforme.

Necesitamos el siguiente lema:

Lema . Sea $p_1, \ldots, p_n \in [0, 1]$ y $l_1, \ldots, l_n\in\mathbb{N}$ sea tal que $p_1 + \ldots + p_n = 1, p_1 \ge p_2 \ge \ldots \ge p_n$ y $l_1 \le l_2 \le \ldots \le l_n$ . Entonces $$ \sum\limits_{i = 1}^n p_i l_i \le \sum\limits_{i = 1}^n \frac{1}{n} \cdot l_i.$$

Prueba. Denote $S_{n + 1} = 0$ y $S_i = p_{i} + \ldots + p_n$ para $i = 1, \ldots, n$ . Demostremos que $S_i \le \frac{n - i + 1}{n}$ . De hecho, si no es así, existe $j\in\{i, i + 1, \ldots, n\}$ tal que $p_j > \frac{1}{n}$ . Esto implica que $p_1 \ge p_2 \ge \ldots \ge p_{i - 1} \ge p_j > \frac{1}{n}$ Por lo tanto $p_1 + \ldots + p_n = 1 \ge (i - 1) \cdot \frac{1}{n} + S_i > (i - 1) \frac{1}{n} + \frac{n - i + 1}{n} = 1$ contradicción.

Utilizando este límite en $S_i$ obtenemos: \begin {align*} \sum\limits_ {i = 1}^n p_i l_i &= \sum\limits_ {i = 1}^n (S_i - S_{i + 1}) l_i = \sum\limits_ {i = 1}^n S_i l_i - \sum\limits_ {i = 2}^{n + 1} S_i \cdot l_{i - 1} = \sum\limits_ {i = 1}^n S_i l_i - \sum\limits_ {i = 2}^{n} S_i \cdot l_{i - 1} \\ &= l_1 S_1 + (l_2 - l_1) S_2 + \ldots + (l_n - l_{n - 1}) S_n \\ & \le l_1 \frac {n}{n} + (l_2 - l_1) \frac {n - 1}{n} + \ldots + (l_n - l_{n - 1}) \cdot \frac {1}{n} \\ &= l_1 \left ( \frac {n}{n} - \frac {n - 1}{n} \right ) + l_2 \left ( \frac {n - 1}{n} - \frac {n - 2}{n} \right ) + \ldots + l_n \cdot \frac {1}{n} \\ &= \sum\limits_ {i = 1}^n \frac {1}{n} \cdot l_i. \end {align*} El lema está demostrado.

Ahora, supongamos que el tamaño de un alfabeto es $n$ .

Dejemos que $c_1, \ldots, c_n$ son las palabras clave del código Huffman para la distribución uniforme. Además, dejemos que $l_i$ sea la longitud de $c_i$ y asumir que $l_1 \le l_2 \le \ldots \le l_n$ . Tome cualquier distribución de probabilidad $p_1, \ldots, p_n$ y asumir que $p_1 \ge p_2 \ge \ldots \ge p_n$ .

Podemos utilizar $c_1, \ldots, c_n$ como código de prefijo para las frecuencias $p_1, \ldots, p_n$ . Por lo tanto, la longitud media del código Huffman para $p_1, \ldots, p_n$ es como máximo $\sum\limits_{i = 1}^n p_i l_i$ . Por el lema la última cantidad es como máximo $\sum\limits_{i = 1}^n \frac{1}{n} \cdot l_i$ y esta última es la longitud media del código Huffman para la distribución uniforme.