cuerda incompresible

Una cadena incompresible es una cadena con complejidad de Kolmogorov igual a su longitud, de modo que no tiene codificaciones más cortas. ^{[ 1 ]} El principio del palomar 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 utilizando un método de compresión que funciona insertando un carácter especial (por ejemplo, @) 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 examinar 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 quedar así:

@0@1@0@1@0

Esta cadena es mucho más corta, aunque almacenar el diccionario en sí consume algo de espacio. Sin embargo, cuantas más repeticiones tenga la cadena, mejor será la compresión.

Nuestro algoritmo puede mejorar si puede analizar la cadena en fragmentos de más de 4 caracteres. Entonces podrá insertar 12349999 y 1234 en el diccionario, lo que nos dará:

@0@0@1

Esta cadena es aún más corta. Ahora consideremos otra cadena:

1234999988884321

Esta cadena es incompresible para 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

Esta cadena tiene la misma longitud que la original, ya que nuestros marcadores de posición para los elementos del diccionario tienen 2 caracteres de longitud, y los elementos que reemplazan tienen la misma longitud. Por lo tanto, nuestra cadena es incompresible para este algoritmo.