Código universal (compresión de datos)

En compresión de datos , un código universal para enteros es un código de prefijo que asigna los enteros positivos a palabras clave binarias, con la propiedad adicional de que, independientemente de la distribución de probabilidad real de los enteros, siempre que la distribución sea monótona (es decir, p ( i )  ≥ p ( i + 1) para todo i positivo ), las longitudes esperadas de las palabras clave se encuentran dentro de un factor constante de las longitudes esperadas que el código óptimo para esa distribución de probabilidad habría asignado. Un código universal es asintóticamente óptimo si la razón entre las longitudes esperadas reales y óptimas está acotada por una función de la entropía de la información del código que, además de estar acotada, tiende a 1 a medida que la entropía tiende a infinito.    

En general, la mayoría de los códigos de prefijo para enteros asignan palabras clave más largas a los enteros de mayor tamaño. Este tipo de código permite comunicar de forma eficiente un mensaje seleccionado de un conjunto de mensajes posibles, simplemente ordenando dicho conjunto por probabilidad decreciente y enviando el índice del mensaje deseado. Los códigos universales no suelen utilizarse para distribuciones de probabilidad conocidas con precisión, y no se conoce ningún código universal que sea óptimo para ninguna distribución utilizada en la práctica.

Un código universal no debe confundirse con la codificación universal de fuentes , en la que el método de compresión de datos no tiene por qué ser un código de prefijo fijo y la relación entre la longitud real y la óptima esperada debe aproximarse a uno. Sin embargo, cabe señalar que un código universal asintóticamente óptimo puede utilizarse en fuentes independientes e idénticamente distribuidas , mediante el uso de bloques cada vez mayores , como método de codificación universal de fuentes.

Estos son algunos códigos universales para números enteros; un asterisco ( * ) indica un código que puede ser reformulado trivialmente en orden lexicográfico , mientras que una doble daga ( ‡ ) indica un código que es asintóticamente óptimo:

• Codificación gamma de Elias *
• Codificación delta de Elias * ‡
• Codificación omega de Elias * ‡
• Codificación Exp-Golomb *, que tiene como caso especial la codificación gamma de Elias. (Utilizada en H.264/MPEG-4 AVC )
• Codificación de Fibonacci
• Codificación de Levenshtein * ‡, la técnica de codificación universal original
• La codificación por bytes utiliza un patrón de bits especial (con al menos dos bits) para marcar el final del código; por ejemplo, si un número entero se codifica como una secuencia de nibbles que representan dígitos en base 15 en lugar de la base 16 , más natural , entonces el valor de nibble más alto (es decir, una secuencia de cuatro unos en binario) se puede utilizar para indicar el final del número entero.
• Cantidad de longitud variable

Estas son no universales:

• Codificación unaria , que se utiliza en los códigos de Elias.
• Codificación Rice , que se utiliza en el códec de audio FLAC y que tiene la codificación unaria como caso especial.
• Codificación de Golomb , que tiene como casos especiales la codificación de Rice y la codificación unaria.

Su no universalidad se puede observar al notar que, si se utiliza cualquiera de ellos para codificar la distribución de Gauss-Kuzmin o la distribución Zeta con parámetro s=2, la longitud esperada de la palabra clave es infinita. Por ejemplo, usar la codificación unaria en la distribución Zeta produce una longitud esperada de

${\displaystyle E(l)={\frac {6}{\pi ^{2}}}\sum _{l=1}^{\infty }{\frac {1}{l}}=\infty .\,}$

Por otro lado, el uso de la codificación gamma universal de Elias para la distribución de Gauss-Kuzmin da como resultado una longitud de palabra clave esperada (aproximadamente 3,51 bits) cercana a la entropía (aproximadamente 3,43 bits).

La codificación Huffman y la codificación aritmética (cuando se pueden utilizar) proporcionan una compresión al menos tan buena, y a menudo mejor, que cualquier código universal.

Sin embargo, los códigos universales resultan útiles cuando no se puede utilizar la codificación de Huffman; por ejemplo, cuando no se conoce la probabilidad exacta de cada mensaje, sino solo la clasificación de sus probabilidades.

Los códigos universales también son útiles cuando los códigos Huffman resultan inconvenientes. Por ejemplo, cuando el transmisor, pero no el receptor, conoce las probabilidades de los mensajes, la codificación Huffman requiere la transmisión de dichas probabilidades al receptor. El uso de un código universal no implica esa sobrecarga.

Cada código universal, al igual que cualquier otro código binario autodelimitante (prefijo), tiene su propia "distribución de probabilidad implícita" dada por P ( i )=2 ^{− l ( i )} , donde l ( i ) es la longitud de la i- ésima palabra clave y P ( i ) es la probabilidad del símbolo correspondiente. Si las probabilidades reales del mensaje son Q ( i ) y la divergencia de Kullback-Leibler${\displaystyle D_{\text{KL}}(Q\|P)}$Si se minimiza mediante el código con l ( i ) , entonces el código Huffman óptimo para ese conjunto de mensajes será equivalente a ese código. De igual manera, qué tan cerca está un código del óptimo se puede medir mediante esta divergencia. Dado que los códigos universales son más simples y rápidos de codificar y decodificar que los códigos Huffman (que, a su vez, son más simples y rápidos que la codificación aritmética ), el código universal sería preferible en los casos en que${\displaystyle D_{\text{KL}}(Q\|P)}$es suficientemente pequeño. Programa de compresión de datos sin pérdidas: Hybrid LZ77 RLE

Para cualquier distribución geométrica (una distribución exponencial en enteros), un código de Golomb es óptimo. Con códigos universales, la distribución implícita es aproximadamente una ley de potencias como${\displaystyle 1/n^{2}}$(más precisamente, una distribución de Zipf ). Para el código de Fibonacci , la distribución implícita es aproximadamente${\displaystyle 1/n^{q}}$, con

${\displaystyle q=1/\log _ {2}(\varphi )\simeq 1.44,}$

dónde${\displaystyle \varphi }$es la proporción áurea . Para el código de coma ternario (es decir, codificación en base 3, representada con 2 bits por símbolo), la distribución implícita es una ley de potencias con${\displaystyle q=1+\log _{3}(4/3)\simeq 1.26}$Estas distribuciones, por lo tanto, tienen códigos casi óptimos con sus respectivas leyes de potencia.

• Compresión de datos , por Debra A. Lelewer y Daniel S. Hirschberg ( Universidad de California, Irvine )
• El libro "Teoría de la información, inferencia y algoritmos de aprendizaje" , de David MacKay , incluye un capítulo sobre códigos para números enteros, con una introducción a los códigos de Elias.
• Кодирование целых чисел tiene principalmente artículos en inglés sobre códigos universales y otros códigos enteros.