¿Cuál es la tasa de compresión máxima teóricamente posible?

Esta es una pregunta teórica, por lo que es de esperar que muchos detalles aquí no sean computables en la práctica o incluso en teoría.¿Cuál es la tasa de compresión máxima teóricamente posible?

Digamos que tengo una cadena s que quiero comprimir. El resultado debe ser un binario autoextraíble (puede ser un ensamblador x86, pero también puede ser otro lenguaje de bajo nivel hipotético de Turing completo) que da como resultado s.

Ahora, podemos iterar fácilmente a través de todos los binarios y programas posibles, ordenados por tamaño. Deje B_s ser la sub-lista de estos binarios que producen s (por supuesto B_s es incomputable).

Como cada conjunto de enteros positivos debe tener un mínimo, debe haber un programa más pequeño b_min_s en B_s.

¿Para qué idiomas (es decir, un conjunto de cadenas) sabemos algo sobre el tamaño de b_min_s? Tal vez solo una estimación. (Puedo construir algunos ejemplos triviales donde puedo siempre incluso calcular B_s y también b_min_s, pero estoy interesado en los idiomas más interesantes.)

Fuente

2010-07-16 Albert

Recuerdo algunos programas muy ingeniosos de los viejos tiempos, como los cargadores de arranque que se sobrescribían varias veces. Probablemente, para lograr un tamaño total mínimo del programa autoextraíble, el programa podría usar su propio texto de alguna manera, por ejemplo, como fuente de constantes. –

Ésta es Kolmogorov complexity, y estás en lo correcto que es not computable. Si lo fuera, podría crear un programa paradójico de longitud n que imprimió una cadena con la complejidad de Kolmogorov m> n.

Claramente, puede enlazar b_min_s para entradas dadas. Sin embargo, hasta donde yo sé, la mayoría de los esfuerzos para hacerlo han sido pruebas de existencia. Por ejemplo, hay una competencia en curso para comprimir English Wikipedia.

Fuente

2010-07-16 03:18:19

Sí, exactamente ese premio me llevó a esta pregunta. :) Sin embargo, tales competiciones/tries solo dan indicaciones porque muestran límites más bajos para una cadena de ejemplo en particular. No dan ninguna respuesta sobre un límite duro promedio/real de un idioma dado (por ejemplo, XML con inglés correcto gramaticalmente como contenido). – Albert

He aquí una buena explicación de compresión que recomendaría para una lectura adicional: http://www.mattmahoney.net/dc/dce.html - y en la página de Hutter, hay un enlace a http://cs.fit.edu /~mmahoney/compression/textdata.html que también es agradable de leer. – schnaader

La tasa de compresión máxima (avarage) es de 1: 1.
El número de entradas posibles es igual al número de salidas.
Tiene que ser capaz de asignar la salida a la entrada.
Para poder almacenar la salida, necesita un contenedor del mismo tamaño que el contenedor mínimo para la entrada, con una tasa de compresión 1: 1.

Fuente

2010-07-16 04:02:23 Dani

"La tasa de compresión máxima (posible) es de 1: 1". ¿Qué significa eso realmente? –

Significa que supongamos que tomas todas las cadenas posibles de 100 bytes y comprimes cada una. La duración promedio de su salida de compresión es de al menos 100 bytes, por lo que la compresión promedio es 1: 1 o peor. Por supuesto, los datos del mundo real no son aleatorios, por lo que sería mejor decir que está hablando de una tasa de compresión óptima en el peor de los casos. Pero intenta responder a la pregunta en el título: la tasa de compresión máxima posible depende sobre todo de los datos. Realmente no responde el cuerpo de la pregunta ... – jjrv

Básicamente, necesita suficiente información para reconstruir su información original. Supongo que las otras respuestas son más útiles para su discusión teórica, pero solo téngalo en cuenta.

Fuente

2010-07-16 04:09:13 Chad

Claude Shannon calcula la densidad de información del idioma Inglés a estar en algún lugar entre 0,6 y 1,3 bits por carácter en su artículo de 1951 Prediction and Entropy of Printed English (PDF, 1,6 MB . Campana Sys. Tech. J (3) p. 50- 64).

Fuente

2010-07-16 10:25:44 phreeza

Hm, me pregunto si la complejidad de Kolmogorov es compatible con la densidad de información de Shannons. Desde mi intuición, la información de Shannon es solo una corriente de bits. P.ej. el flujo de píxeles de una imagen fractal tiene todavía una alta densidad de información por definición de Shannon. Entonces bajo estas consideraciones, me pregunto si 0.6 es realmente una buena estimación. Tal vez para texto en inglés que no contenga ninguna información redundante. – Albert

La información de Shannon hace una declaración sobre el caso estadístico general, mientras que la complejidad de Kolmogorov es el contenido de información de un solo objeto. Por lo tanto, en este ejemplo, la información de Shannon dice algo acerca del carácter promedio en un texto en inglés, mientras que la complejidad de Kolmogorov es el contenido de información de un cuerpo específico de texto, por ejemplo, su cadena. – phreeza

Pero Shannon fue una importante figura formativa en la "teoría de la información" y la entropía, y en última instancia, es la cuestión de la entropía. ["La entropía de Shannon representa un límite absoluto para la mejor compresión sin pérdidas posible de cualquier comunicación"] (http://en.wikipedia.org/wiki/Entropy_%28information_theory%29) –

¿Cuál es la tasa de compresión máxima teóricamente posible?

Respuesta

Cuestiones relacionadas