Código universal
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 21 de diciembre de 2018; las comprobaciones requieren 4 ediciones .El código universal para números enteros en la compresión de datos es un código de prefijo que convierte números enteros positivos en palabras binarias, con la propiedad adicional de que para cualquier distribución de probabilidad verdadera en números enteros, siempre que la distribución sea monótona (es decir, para cualquier ), la esperada las longitudes de las palabras binarias están dentro de un factor constante de las longitudes esperadas que el código óptimo asignaría a esa distribución de probabilidad.
Un código universal es asintóticamente óptimo si el coeficiente entre las longitudes esperadas real y óptima está relacionado por la función de entropía de información del código, que tiende a 1 cuando la entropía tiende a infinito.
La mayoría de los códigos de prefijos enteros asignan palabras clave más largas a números enteros más grandes. Tal código puede usarse para codificar eficientemente un mensaje extraído de un conjunto de posibles mensajes simplemente ordenando el conjunto de mensajes en orden descendente de probabilidad y luego reenviando el índice del mensaje deseado. Los códigos universales generalmente no se usan para distribuciones de probabilidad conocidas.
Los códigos universales incluyen:
- Codificación unaria
- código gamma de Elías
- código delta de Elías
- Código Elías Omega
- código delta
- Codificación de Fibonacci
- código Golomb exponencial
Algunos códigos no universales:
- codificación única , utilizada en códigos Elias
- Codificación de arroz
- Codificación Golomb
Su no universalidad se manifiesta en el hecho de que si alguno de ellos se utiliza para codificar la distribución de Gauss-Kuzmin o la distribución zeta con el parámetro s=2, entonces la longitud esperada de la palabra clave es infinita. Por ejemplo, usando la codificación de un lugar por distribución zeta, tenemos la siguiente longitud esperada:
Uso práctico en la compresión de datos
El uso del código Huffman y la codificación aritmética (cuando se pueden usar juntos) da mejores resultados que cualquier otro código universal.
Sin embargo, los códigos universales son útiles cuando no se puede utilizar el código de Huffman; por ejemplo, cuando no es posible determinar la probabilidad exacta de cada mensaje, pero se conoce la clasificación de sus probabilidades.
Los códigos genéricos también son útiles cuando el código de Huffman no funciona correctamente. Por ejemplo, cuando el remitente conoce las probabilidades del mensaje pero el destinatario no, el código Huffman requiere que las probabilidades se transmitan al destinatario. El uso de un código genérico elimina estos inconvenientes.
Cada código universal da su propia "distribución implícita" de probabilidades , donde es la longitud de la i-ésima palabra clave y es la probabilidad del símbolo de transmisión. Si las probabilidades reales del mensaje, y la distancia Kullback-Leibler minimiza un código con , el código Huffman óptimo para este conjunto de mensajes será equivalente a este código. Dado que los códigos universales son más rápidos que el código de Huffman, se prefiere el código universal en los casos en que lo suficientemente pequeño es suficiente.
Para cualquier distribución geométrica , la codificación Golomb es óptima. Para los códigos universales, la distribución implícita obedece aproximadamente a una ley de potencia , por ejemplo , más específicamente, la ley de Zipf . Para el código de Fibonacci, la distribución implícita obedece aproximadamente a la ley de , donde es el cociente de la proporción áurea .
Enlaces
| métodos de compresión | |||||||
|---|---|---|---|---|---|---|---|
| Teoría |
| ||||||
| sin pérdidas |
| ||||||
| Audio |
| ||||||
| Imágenes |
| ||||||
| Video |
| ||||||