¿Ningún algoritmo de compresión puede comprimir todos los mensajes de entrada?

Acabo de empezar a leer un libro llamado Introducción a la compresión de datos, por Guy E. Blelloch. En la página uno, dice:

La verdad es que si un mensaje se acorta mediante un algoritmo, entonces se debe alargar algún otro mensaje. Puede verificar esto en la práctica ejecutando GZIP en un archivo GIF. De hecho, es posible ir más allá y mostrar que para un conjunto de mensajes de entrada de longitud fija, si un mensaje está comprimido, la longitud promedio de los mensajes comprimidos sobre todas las entradas posibles siempre será más larga que la original. mensajes de entrada

Considere, por ejemplo, los 8 posibles mensajes de 3 bits. Si uno está comprimido a dos bits, no es difícil convencerse de que dos mensajes tendrán que expandirse a 4 bits, dando un promedio de 3 1/8 bits.

De Verdad? Me resulta muy difícil convencerme de eso. De hecho, aquí hay un contraejemplo. Considere el algoritmo que acepta como entrada cualquier cadena de 3 bits y se asigna a las siguientes salidas:

000 -> 0
001 -> 001
010 -> 010
011 -> 011
100 -> 100 
101 -> 101
110 -> 110
111 -> 111

Así que ahí estás: ninguna entrada se asigna a una salida más larga. Ciertamente no hay "dos mensajes" que se hayan expandido a 4 bits.

Entonces, ¿de qué está hablando exactamente el autor? Sospecho que hay alguna advertencia implícita que simplemente no es obvia para mí, o está usando un lenguaje demasiado amplio.

Descargo de responsabilidad: me doy cuenta de que si mi algoritmo se aplica de forma iterativa, de hecho perderás datos. Intente aplicarlo dos veces a la entrada 110: 110 -> 000 -> 0, y ahora no sabe cuál de 110 y 000 fue la entrada original. Sin embargo, si lo aplica solo una vez, me parece sin pérdidas. ¿Está relacionado con lo que habla el autor?

Lo que falta es que debe considerar todos los bits de tamaño 3 o menos . Es decir: si en un esquema de compresión para bits de tamaño 3 o menos comprimimos una de las cadenas de 3 bits en una cadena de 2 bits, entonces alguna cadena de tamaño 3 o menos tendrá que expandirse a 3 bits o más.

Un esquema de compresión sin pérdida es una función $C$ de cadenas de bits finitas a cadenas de bits finitas que es inyectiva, es decir, si $C(x) = C(y)$ entonces $x = y$es decir, $C(x)$ determina de forma única $x$.

Considere un esquema de compresión arbitrario $C$ y deja $S$Ser un conjunto de cadenas binarias. Podemos expresar qué tan bien$C$ trabaja en $S$ calculando la relación

Si tratamos de comprimir todas las cadenas de longitud como máximo$n$ entonces estamos en problemas:

Teorema: Let$S$ser el conjunto de todas las cadenas de longitud como máximo$n$ y $C$Cualquier esquema de compresión. Entonces$\text{CompressionRatio}(C,S) \geq 1$.

Entonces, el mejor esquema de compresión del mundo es la función de identidad. Bueno, solo si queremos comprimir cadenas aleatorias de bits. Las cadenas de bits que ocurren en la práctica están lejos de ser aleatorias y exhiben mucha regularidad. Es por eso que tiene sentido comprimir datos a pesar del teorema anterior.

Solo una nota adicional a la buena respuesta de Andrej:

También puede echar un vistazo a la complejidad de Kolmogorov :

Definición : dada una cadena$s$, su complejidad Kolmogorov $C(s)$ relativo a un modelo fijo de cómputo es la duración del programa de cortos (por ejemplo, la máquina de Turing) que genera $s$.

Informalmente $C(s)$mide su contenido de información o su grado de redundancia ; una cuerda$s$es incompresible si$C(s) \geq |s|$

Dos teoremas fundamentales son:

1) independientemente del modelo de cálculo hay una constante $c$ tal que para cada cuerda $s$: $C(s) \leq |s| + c$ (informalmente, dada una cadena $s$ puede codificarlo en un programa que simplemente lo genera sin ningún procesamiento o compresión)

2) para todos $n$ existe una cadena $s$ de longitud $n$ eso es incompresible: $C(s) \geq |s|$ (análogo al teorema descrito en la respuesta de Andrej).

La prueba es simple: hay $2^n$ cadenas binarias de longitud $n$, pero menos descripciones (programas) de duración $< n$:

$\sum_{i=0}^{n-1} 2^i = 2^n - 1 < 2^n$.

Su contraejemplo está mal.

Su lista de valores comprimidos tiene información oculta que, de hecho, hace que la longitud promedio sea más larga que 3 bits. La información adicional es la longitud de la cadena de salida.

Con nuestros ojos podemos ver en su tabla que la primera cadena de salida tiene solo 1 bit de largo y las otras son de 3 bits, pero está haciendo trampa si no codifica explícitamente ese hecho. Codifiquemos eso anteponiendo un bit más; 0 significará "longitud = 1" y 1 significará "longitud = 3".

Entonces tu mesa realmente se convierte en:

000 -> 00
001 -> 1001
010 -> 1010
011 -> 1011
100 -> 1100 
101 -> 1101
110 -> 1110
111 -> 1111

... que promedia a 3.75 bits.

EDITAR

Aquí hay una idea de último momento, que ilustra el mismo punto. Es una buena pregunta de prueba:

El código Morse está compuesto solo por puntos y guiones. Llamemos al punto 0 y al guión 1. Todas las letras mayúsculas están codificadas como no más de cuatro bits.

E = . = 0
Q = --.- = 1101

Hay 26 letras mayúsculas. Pero cuatro bits solo deberían poder codificar 16 valores distintos. ¿Que esta pasando?

Contando el caso trivial de longitud cero, hay $2^{n+1}-1$cadenas de bits cuya longitud es como máximo n (si se sabe que las longitudes son múltiplos exactos de ocho, el número es menor pero más difícil de calcular). Por lo tanto, todas las cadenas de longitud$n$ o menos podría representarse utilizando cadenas de longitud fija $n+1$. Sin embargo, si muchas cadenas serán mucho más cortas que la longitud máxima, puede ser útil utilizar esquemas de codificación alternativos que agreguen más de uno a la longitud de las cadenas máximas, pero menos a la longitud de las cadenas más cortas. En consecuencia, la cantidad de información transmitida al conocer la longitud exacta de una cadena depende de cuánto tiempo se suponga que podría ser la cadena, y qué tan dispuesto estaría uno para rellenar cadenas más cortas.

Debido a que tales factores dependen mucho de la aplicación, es útil asumir un modelo de cálculo en el que se supone que las cadenas de entrada contienen información que sería suficiente para que el lector sepa dónde terminan (incluso si se rellenan con cantidades arbitrarias de datos arbitrarios) , y las cadenas de salida deben hacer lo mismo. Tal modelo de cómputo permitirá que cualquier operación que funcione en registros de datos individuales funcione igual de bien en cualquier secuencia concatenada de registros de datos [se puede suponer que el código que sabría cuándo dejar de leer registros completos sin comprimir también sabe cuándo parar leyendo enteros comprimidos].