Una cadena incompresible es una cadena con una complejidad de Kolmogorov igual a su longitud, por lo que no tiene codificaciones más cortas. [1] El principio del casillero se puede utilizar para demostrar que para cualquier algoritmo de compresión sin pérdidas , deben existir muchas cadenas incompresibles.
Supongamos que tenemos la cadena 12349999123499991234y estamos usando un método de compresión que funciona colocando un carácter especial en la cadena (digamos @) seguido de un valor que apunta a una entrada en una tabla de búsqueda (o diccionario) de valores repetidos. Imaginemos que tenemos un algoritmo que examina la cadena en fragmentos de 4 caracteres. Al observar nuestra cadena, nuestro algoritmo podría seleccionar los valores 1234 y 9999 para colocarlos en su diccionario. Digamos que 1234 es la entrada 0 y 9999 es la entrada 1. Ahora la cadena puede convertirse en:
@0@1@0@1@0
Esta cadena es mucho más corta, aunque almacenar el diccionario costará algo de espacio. Sin embargo, cuantas más repeticiones haya en la cuerda, mejor será la compresión.
Sin embargo, nuestro algoritmo puede funcionar mejor si puede ver la cadena en fragmentos de más de 4 caracteres. Luego puede poner 12349999 y 1234 en el diccionario, dándonos:
@0@0@1
Esta cuerda es aún más corta. Ahora considere otra cadena:
1234999988884321
Esta cadena es incompresible según nuestro algoritmo. Las únicas repeticiones que ocurren son 88 y 99. Si almacenáramos 88 y 99 en nuestro diccionario, produciríamos:
1234@1@1@0@04321
Esto es tan largo como la cadena original, porque nuestros marcadores de posición para los elementos del diccionario tienen 2 caracteres y los elementos que reemplazan tienen la misma longitud. Por lo tanto, nuestro algoritmo no puede comprimir esta cadena.