Intermezzo: Códigos Universales

Hay muchas maneras para codificar enteros, clásicamente se pueden codificar en notación posicional en cierta base \(b > 1\) y se escribe un entero no negativo \(n\) como

\[n = \sum_{k} n_{k} b^k.\]

Donde los \(n_{k}\) son los dígitos en la representación de \(n\) en base \(b\) y pertenecen al rango \(\left[ 0, b \right[\). Estos sistemas son los más usados en la vida cotidiana pues usamos \(b = 10\) para casi todo. Especialmente con las computadoras, se usan otros sistemas posicionales usualmente como el binario, octal y hexadecimal, que tienen \(b = 2,\ 8,\ 16\) respectivamente.

No solamente se pueden representar enteros de esta manera, sino que hay otros sistemas como lo es el unario que discutiremos más adelante. La idea es poder representarlos de "la mejor manera posible" dada cierta información previa. Y ya sabemos que según la teoría de la información de Shannon, como se expuso en el preludio, si se conoce la distribución de probabilidad de los enteros, lo óptimo es la entropía. Los códigos universales son códigos para representar enteros positivos usando ceros y unos que logran esto.

Definición

Formalmente tenemos que un código es universal si es libre de prefijos y que si tenemos una función de masa de probabilidad \(p : \mathbb{N} \to \left[0, 1\right]\) de los enteros a codificar que es monótona decreciente, luego el largo esperado de la codificación debe estar acotado por una función afín de la entropía de la distribución.

Sea \(X\) la variable aleatoria de la fuente de los enteros, y \(| C |\) el largo de la codificación; así que el largo esperado es:

\[\mathbb{E} (| C |) = \sum_{k > 0} p(k) | c(k) |.\]

Donde \(c(k)\) es la codificación de \(k\). Si \(C\) es universal, entonces \(\mathbb{E}(| C |) = O(\mathrm{H} (X))\).

Además decimos que un código universal es asintóticamente óptimo si la razón entre el largo esperado de la codificación y el largo óptimo tiende a 1 a medida que la entropía crece.

Un no ejemplo: codificación unaria

Podemos codificar un entero no negativo \(n\) como una secuencia de \(n + 1\) bits que es \(n\) ceros y un uno al final. Esta codificación la volveremos a ver cuando veamos los códigos de Elias en las siguientes secciones.

Resulta que hay distribuciones para las cuales el largo esperado de la palabra es infinito, así que en estos casos esta codificación falla ser universal. Consideremos la distribución \(\mathrm{Zeta}(s)\) que tiene función de masa de probabilidad

\[p(k) = \frac{k^{-s}}{\zeta (s)}.\]

Donde \(s > 1\) es el parámetro y \(\zeta\) es la función zeta de Riemann, que solamente está ahí como factor de normalización. De hecho, esta es la normalización de la famosa distribución de Zipf, que es importante para saber que los textos en lenguaje natural son compresibles.

Si \(s = 2\), entonces \(\zeta(2) = \frac{\pi^2}{6}\) y tenemos que el largo esperado de la codificación unaria \(U\) es dado por

\[\mathbb{E}(| U |) = \frac{6}{\pi^2} \sum_{k > 0}^\infty \frac{k + 1}{k^2} = \infty.\]

La serie anterior diverge porque está acotada inferiormente por la serie armónica que es el clásico ejemplo de una serie divergente. Esto demuestra que la codificación unaria no es universal. Otros no ejemplos que ya hemos visto son las codificaciones Rice y Golomb.

Ejemplos

A continuación siguen algunas de los códigos universales más importantes:

Estas serán descritas en las siguientes secciones de la Wiki.

Referencias

Knuth, D. (1997). Seminumerical Algorithms. The Art of Computer Programming (3rd ed.). Addison-Wesley Professional.
Hirschberg, D.; Lelewer, D. Data Compression.
MacKay, D. (2003). Information Theory, Inference and Learning Algorithms. Cambridge University Press.
Weisstein, E. Zipf Distribution. Wolfram MathWorld.