En la compresión de datos , un código universal para números enteros es un código de prefijo que asigna los números enteros positivos a palabras de código binarias, con la propiedad adicional de que cualquiera que sea la distribución de probabilidad verdadera en números enteros, siempre que la distribución sea monótona (es decir, p ( i ) ≥ p ( i + 1) para todos los i positivos ), las longitudes esperadas de las palabras de código están 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 relación entre las longitudes esperadas reales y óptimas está limitada por una función de la entropía de información del código que, además de estar limitada, se acerca a 1 a medida que la entropía se acerca al infinito.
En general, la mayoría de los códigos de prefijo para números enteros asignan palabras de código más largas a números enteros mayores. Este tipo de código se puede utilizar para comunicar de manera eficiente un mensaje extraído de un conjunto de mensajes posibles, simplemente ordenando el conjunto de mensajes por probabilidad decreciente y luego enviando el índice del mensaje deseado. Los códigos universales generalmente no se utilizan 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.
No debe confundirse un código universal con la codificación de fuente universal, en la que el método de compresión de datos no necesita ser un código de prefijo fijo y la relación entre las longitudes reales y óptimas esperadas debe aproximarse a uno. Sin embargo, tenga en cuenta que un código universal asintóticamente óptimo se puede utilizar en fuentes independientes distribuidas de forma idéntica , mediante el uso de bloques cada vez más grandes , como un método de codificación de fuente universal.
Estos son algunos códigos universales para números enteros; un asterisco ( * ) indica un código que puede reformularse trivialmente en orden lexicográfico , mientras que una doble daga ( ‡ ) indica un código que es asintóticamente óptimo:
Estos no son universales:
Su no universalidad se puede observar al notar que, si cualquiera de estos se utiliza para codificar la distribución de Gauss-Kuzmin o la distribución Zeta con parámetro s=2, la longitud esperada de la palabra de código es infinita. Por ejemplo, al usar codificación unaria en la distribución Zeta se obtiene una longitud esperada de
Por otra parte, el uso de la codificación gamma universal de Elias para la distribución de Gauss-Kuzmin da como resultado una longitud de palabra de código esperada (aproximadamente 3,51 bits) cercana a la entropía (aproximadamente 3,43 bits) - Academia Google.
La codificación de 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 son ú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 de Huffman resultan inconvenientes. Por ejemplo, cuando el transmisor, pero no el receptor, conoce las probabilidades de los mensajes, la codificación de Huffman requiere un gasto adicional para transmitir esas probabilidades al receptor. El uso de un código universal no tiene ese gasto adicional.
Cada código universal, al igual que cualquier otro código binario autodelimitador (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 de código 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 se minimiza mediante el código con l ( i ) , entonces el código de Huffman óptimo para ese conjunto de mensajes será equivalente a ese código. Del mismo modo, se puede medir qué tan cerca está un código del óptimo mediante esta divergencia. Dado que los códigos universales son más simples y rápidos de codificar y decodificar que los códigos de 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 sea suficientemente pequeño. Programa de compresión de datos sin pérdida: Hybrid LZ77 RLE
Para cualquier distribución geométrica (una distribución exponencial de números enteros), un código de Golomb es óptimo. Con códigos universales, la distribución implícita es aproximadamente una ley de potencia como (más precisamente, una distribución Zipf ). Para el código de Fibonacci , la distribución implícita es aproximadamente , con
donde 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 potencia con . Por lo tanto, estas distribuciones tienen códigos casi óptimos con sus respectivas leyes de potencia.
