compression - turbo - ¿Cuál es la máxima tasa de compresión teóricamente posible?
motor de compresión variable vc turbo (4)
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 tenga esto en cuenta.
Esta es una pregunta teórica, así que espere que muchos detalles aquí no sean computables en la práctica o incluso en teoría.
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 algún otro lenguaje hipotético de bajo nivel Turing-complete) que produce s .
Ahora, podemos recorrer fácilmente todos los binarios y programas posibles, ordenados por tamaño. Sea B_s la sub-lista de estos binarios que B_s s (por supuesto, B_s es indiscutible).
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, conjunto de cadenas) sabemos algo sobre el tamaño de b_min_s ? Tal vez sólo una estimación. (Puedo construir algunos ejemplos triviales en los que siempre puedo calcular B_s y también b_min_s , pero estoy interesado en lenguajes más interesantes).
Esta es la complejidad de Kolmogorov , y tienes razón en que no es computable . Si lo fuera, podría crear un programa paradójico de longitud n que imprimiera una cadena con la complejidad de Kolmogorov m> n.
Claramente, puede b_min_s para entradas dadas. Sin embargo, hasta donde sé, la mayoría de los esfuerzos para hacerlo han sido pruebas de existencia. Por ejemplo, hay una competencia en curso para comprimir la Wikipedia en inglés .
La tasa de compresión máxima (promedio) posible es 1: 1.
El número de entradas posibles es igual al número de salidas.
Tiene que ser para poder mapear la salida de nuevo a la entrada.
Para poder almacenar la salida, necesita un contenedor del mismo tamaño que el contenedor mínimo para la entrada, lo que da una tasa de compresión 1: 1.
Claude Shannon estimó que la densidad de información del idioma inglés estaba en algún lugar entre 0,6 y 1,3 bits por carácter en su artículo 1951 Predicción y entropía del inglés impreso (PDF, 1,6 MB. Bell Sys. Tech. J (3) p. 50-64 ).