Cadena de caracteres incompresible

Una cadena de caracteres incompresible es una cadena de caracteres en la cual la complejidad de Kolmogórov es igual a su longitud, de modo que no tiene una codificación más corta.​

Ejemplo

Supongamos que tenemos la siguiente cadena de longitud 20: 12349999123499991234, y estamos utilizando un método de compresión que funciona con un carácter especial (digamos '@') seguido de un número de entrada de una tabla o diccionario de términos que se repiten. Supongamos que tenemos un algoritmo que lee la cadena de a cuatro caracteres. Mirando en nuestra cadena, nuestro algoritmo podría elegir los valores 1234 y 9999 para colocar a en el diccionario. Entonces 1234 sería la entrada 0 y 9999 la entrada 1. Ahora la cadena se puede expresar como:

@0@1@0@1@0

Evidentemente esta es mucho más corta que la cadena original, a pesar de que almacenar el diccionario también costará espacio. Aun así, cuanto más se repitan esos patrones en una cadena más larga, tanto mejor será el nivel de compresión.

Nuestro algoritmo puede mejorar aún, al ver la cadena en grupos de más de 4 caracteres. En ese caso puede poner 12349999 y 1234 en el diccionario, resultando en una cadena aún más corta:

@0@0@1

Supongamos ahora la siguiente cadena:

1234999988884321

Esta cadena es incompresible por nuestro algoritmo. Los únicos patrones que se repiten son 88 y 99. Si guardamos esos dos valores en nuestro diccionario el resultado de la compresión sería:

1234@1@1@0@04321

Desafortunadamente la longitud de este resultado es tan larga como lo es la cadena original, porque nuestras entradas para los elementos del diccionario tienen una longitud de 2, y los elementos por los cuales se reemplazan también. De ahí, esta cadena es incompresible por nuestro algoritmo.

Referencias

• Datos: Q6015188