Una cadena incompresible es una cadena con la complejidad de Kolmogorov igual a su longitud, por lo que no tiene codificaciones más cortas. [1]
Ejemplo
Supongamos que tenemos la cadena 12349999123499991234, y estamos usando un método de compresión que funciona poniendo 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
Obviamente, esto es mucho más corto, aunque almacenar el diccionario en sí costará algo de espacio. Sin embargo, cuantas más repeticiones haya en la cadena, 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
Incluso más corto. Ahora considere otra cadena:
1234999988884321
Esta cadena es incompresible por nuestro algoritmo. Las únicas repeticiones que ocurren son 88 y 99. Si tuviéramos que almacenar 88 y 99 en nuestro diccionario, produciríamos:
1234 @ 1 @ 1 @ 0 @ 04321
Desafortunadamente, esta es tan larga 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 tanto, esta cadena es incompresible por nuestro algoritmo.
Referencias
- ^ V. Chandru y MRRao, Manual de algoritmos y teoría de la computación , CRC Press 1999, p29-30.