¿Hay un límite práctico para el tamaño de un pedazo de datos con redundancia estadística 0?

Question

Me estaba preguntando, simplemente porque tiendo a preguntarme acerca de este tipo de cosas en mi tiempo libre, si hay datos de piezas que son 1Gig+ 0 Estadística de Redundancia? (es decir, incompresibles con compresión sin pérdida.)
Es incluso posible que un archivo de más de unos pocos bytes de tener ese rasgo? Es que la propiedad sea posible en absoluto, o es meramente teórica?

De todos modos, por favor, hágamelo saber si tal cosa sería posible, y, si es factible, por favor enlace a un lugar donde yo podía ver una pieza de datos. Google no me dio nada.

Así se podría incluir la página de la Wikipedia sobre la estadística de la redundancia: en.wikipedia.org/wiki/Redundancy (la teoría de la información)

Answer 1

Voy a mejorar en breve en mi comentario anterior: Si un algoritmo de compresión es fijo, un arbitrario grandes no compresibles (con este algoritmo) pieza de información puede ser obtenida sólo por iteración del algoritmo. Si un ciclo de aparecer antes de alcanzar el tamaño deseado, elegir algún punto de partida de este ciclo, e inténtelo de nuevo.

$\def\N\{\mathbb N^*}$Detalles. Teniendo en cuenta que los datos son cadenas de 0 y 1, un archivo es (después de anteponiendo con un 1) nada más que un (distinto de cero) entero. La longitud de un archivo $n\in \N*$$\log(n)$. Un algoritmo de compresión es una función inyectiva de a $\N$ $\N$(tiene que ser inyectiva para garantizar la descompresión es posible). Decimos que $n$ no es compresible si $\log(n) < \log(f(n))$.

Voy distintas, dos de los casos (no es absolutamente necesario bits el primer caso es más bonito) en Primer lugar, asumir $f$ no es surjective y usted sabe algunos de los $n \notin f(\N)$ (esto es bastante razonable para ejemplos prácticos). Como $f$ es inyectiva, si la órbita $f^{(k)}(n)$ es en última instancia, cíclico, tiene que ir a través de $n$ nuevo. Como $n \notin f(\N)$, esto es imposible: así que la órbita es, en definitiva, no cíclica, y tiene que ir a través de arbitraria de los grandes números. Más precisamente, la longitud de los sucesivos números tienen dos aumento de tiempo en tiempo, por lo que esta secuencia contiene una cantidad infinita de no compresibles números. Algunos tienen que ser de mayor tamaño que el señalado tamaño.

En el caso general, bien, recoger un número $n$, e iterar. Si usted conoce a un no compresibles número del tamaño deseado antes de golpear $n$ nuevo, de que se hacen. En el otro caso, recoja el punto de partida de un ciclo, e inténtelo de nuevo. Que recorrer en este, cada vez con exclusión de todos los ciclos descritos anteriormente. La secuencia generada también contiene una cantidad infinita de no compresibles números.

Answer 2

Voy a ty para responder a la pregunta en términos de la complejidad de Kolmogorov, que es la longitud de la más pequeña descripción de una secuencia finita, dado un fijo lenguaje de descripción. Una secuencia es llamada prueba de Kolmogorov al azar, si el test de Kolmogorov complejidad es al menos tan grande como la longitud de la secuencia (es decir, la secuencia es incompresible).

Para su problema, se utiliza el conjunto de programas fijos máquina de Turing universal como el lenguaje de descripción. Sin pérdida de generalidad, podemos suponer que la máquina de Turing universal utiliza un alfabeto binario. Para cada número natural $n>0$, existe una prueba de Kolmogorov secuencia aleatoria. La prueba es simple: Hay $2^n$ secuencias de longitud $n$, pero sólo $2^{n-1}$ % de programas de la longitud de menos de $n$. Así que por el principio del palomar, debe haber algunas secuencias-de hecho, al menos $2^n - 2^{n-1} = 2^{n-1}$ secuencias -- de longitud $n$ que son incompresibles.

Esta prueba es, por supuesto, no son constructivas. Además, no es computable si la secuencia es la prueba de Kolmogorov al azar.

Actualización

Para realizar una conexión a una estadística de la redundancia: Si se genera una secuencia aleatoria de proceso, la complejidad de Kolmogorov dividido por la longitud de la secuencia converge a la entropía de la generación de proceso (como la longitud de la secuencia tiende a infinito). Por lo tanto, una secuencia generada por un proceso de Bernoulli con p=0.5 será "la prueba de Kolmogorov al azar en el límite".