Relación de la entropía de compresión sin pérdidas Tasa

Question

Fuente de Shannon teorema de codificación sabemos que la entropía de una cadena comprimida es delimitada por la entropía de la cadena original de este modo:

H(X) <= L < H(X) + 1/N 

donde H (X) es la entropía de la cadena de origen, N es la longitud de la cadena de origen, y L es la longitud esperada de la cadena comprimida.

Esto significa, necesariamente, que hay un límite a la compresión sin pérdidas.

Lo que me gustaría saber es:

• Se puede relacionarse directamente entropía en cierta relación de compresión esperado?

• ¿Se puede utilizar la entropía de encontrar algún límite superior de la relación de compresión?

Answer 1

No se puede relacionar directamente a la entropía relación de compresión sin saber la longitud de la cadena de origen, pero se puede ver el límite teórico a la relación de compresión máxima resolviendo para el menor valor posible de L. Puede utilizar este límite una métrica para la eficiencia de sus algoritmos de compresión, a pesar de una mala métrica no significa que un mejor algoritmo se ha descubierto ni siquiera existe.

Así que, sí. Puede utilizar la entropía para encontrar la relación de compresión sin pérdida máxima teórica, pero no, no se puede utilizar para determinar su relación de compresión esperada para cualquier algoritmo de compresión dada.

Answer 2

El teorema de Shannon se define en términos de datos al azar y probabilidades. Del mismo modo, el entropía de una cadena única se define por cadenas aleatorias - la entropía es una propiedad de la distribución, no de las propias cadenas. Por lo tanto, podemos reformular el teorema de Shannon informalmente como:

  

Si se selecciona al azar una cadena de una distribución de probabilidad dada, entonces la mejor relación de compresión media que podemos conseguir para la cadena viene dada por la tasa de entropía de la distribución de probabilidad.

Dado cualquier cadena aleatoria, puedo escribir fácilmente un algoritmo de compresión que comprime esa cadena hacia abajo en 1 bit, pero mi algoritmo necesariamente aumentará la longitud de algunas otras cadenas. Mi algoritmo de compresión funciona de la siguiente manera:

1. Si la cadena de entrada es igual a alguna cadena aleatoria pre-seleccionado , la salida es la cadena de 1 bit "0"
2. De lo contrario, la salida es la cadena + 1 bits N de "1" seguido de la cadena de entrada

El algoritmo de descompresión correspondiente es:

1. Si la entrada es "0", la salida es nuestra cadena aleatoria pre-elegido anterior
2. En caso contrario, la salida es todo excepto el primer bit de entrada

La clave aquí es que no podemos escribir un algoritmo que, para todas las cadenas de una distribución dada, los comprime todos a una alta velocidad de media. Hay demasiadas cadenas.

Si tenemos una distribución de probabilidad dada de cadenas, podemos calcular la tasa de entropía de la distribución, y luego, si escogerán aleatoriamente una cadena de acuerdo con la distribución y el intento de comprimirlo usando cualquier algoritmo, el tamaño relativo de la cadena comprimida, en promedio, nunca será inferior a la tasa de entropía. Esto es lo que dice el teorema de Shannon.

Answer 3

Sí. El tasa de entropía del idioma Inglés se cita a menudo como 1,5 bits por carácter (más o menos). codificaciones típicas utilizan 8 bits por carácter. Así un texto comprimido al máximo debe ser de 1,5 / 8 (~ 19%) del tamaño de la original. Los resultados reales de una versión de texto sin formato de Orgullo y prejuicio de Jane Austin:. orig = 701K, 178K = bzip2, por ~ 25%

Answer 4

Sí! Creo este documento podría apuntar en la dirección correcta.

ETA Parece que se necesita para ser un miembro de IEEE para leer el periódico real. Si alguien puede encontrar un recurso a disposición del público (o explicar las matemáticas aquí), que sería mucho mejor, por supuesto!