En la compresión de datos , un código universal para enteros es un código de prefijo que mapea los enteros positivos en palabras de código binarias, con la propiedad adicional de que cualquiera que sea la verdadera distribución de probabilidad en 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 de código están dentro de un factor constante de las longitudes esperadas que habría asignado el código óptimo para esa distribución de probabilidad. Un código universal es asintóticamente óptimosi 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 cuando 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 más grandes. Dicho 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 disminuyendo la probabilidad 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 sabe que ningún código universal sea óptimo para ninguna distribución utilizada en la práctica.
Un código universal no debe confundirse 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 esperadas reales y óptimas debe acercarse 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 método de codificación de fuente universal.
Códigos universales y no universales
Estos son algunos códigos universales para números enteros; un asterisco ( * ) indica un código que se puede reformular 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 * [ se necesita más explicación ] ‡
- Codificación Exp-Golomb *, que tiene la codificación gamma de Elias como caso especial. (Usado en H.264 / MPEG-4 AVC )
- Codificación de Fibonacci
- Codificación Levenshtein * ‡, la técnica de codificación universal original [1]
- Codificación de bytes donde se 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 se puede usar el valor de nibble más alto (es decir, una secuencia de cuatro en binario) para indicar el final del número entero.
- Cantidad de longitud variable
Estos son los no universales:
- Codificación unaria , que se usa 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 Golomb , que tiene codificación Rice y codificación unaria como casos especiales.
Su no universalidad puede observarse notando que, si alguno de estos se usa para codificar la distribución Gauss-Kuzmin o la distribución Zeta con el parámetro s = 2, la longitud esperada de la palabra de código es infinita. Por ejemplo, el uso de codificación unaria en la distribución Zeta produce una longitud esperada de
Por otro lado, el uso de la codificación gamma universal de Elias para la distribución 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) [2] .
Relación con la compresión práctica
La codificación de Huffman y la codificación aritmética (cuando se pueden usar) brindan al menos una compresión tan buena y, a menudo, mejor que cualquier código universal.
Sin embargo, los códigos universales son útiles cuando no se puede usar la codificación de Huffman, por ejemplo, cuando uno no conoce la probabilidad exacta de cada mensaje, pero solo conoce la clasificación de sus probabilidades.
Los códigos universales también son útiles cuando los códigos de Huffman son inconvenientes. Por ejemplo, cuando el transmisor pero no el receptor conoce las probabilidades de los mensajes, la codificación de Huffman requiere una sobrecarga para transmitir esas probabilidades al receptor. Usar un código universal no tiene esa sobrecarga.
Cada código universal, al igual que los demás códigos binarios autodelimitantes (prefijos), 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 Kullback-Leibler D KL ( q || p ) 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. . Asimismo, esta divergencia puede medir qué tan cerca está un código del óptimo. Dado que los códigos universales son más simples y más rápidos de codificar y decodificar que los códigos de Huffman (que es, a su vez, más simple y más rápido que la codificación aritmética ), el código universal sería preferible en los casos en que D KL ( q || p ) es suficientemente pequeño. [3]
Para cualquier distribución geométrica (una distribución exponencial en números enteros), un código de Golomb es óptimo. Con los 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
dónde 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 tanto, estas distribuciones tienen códigos casi óptimos con sus respectivas leyes de potencia.
enlaces externos
- Compresión de datos , por Debra A. Lelewer y Daniel S. Hirschberg ( Universidad de California, Irvine )
- Teoría de la información, inferencia y algoritmos de aprendizaje , de David MacKay , tiene un capítulo sobre códigos para números enteros, incluida una introducción a los códigos de Elias.
- Кодирование целых чисел tiene principalmente artículos en inglés sobre códigos enteros universales y otros.