Cadena de caràcters incompresible

Una cadena de caràcters incompresible és una cadena de caràcters en la qual la complexitat de Kolmogórov és igual a la seua llongitut, de modo que no té una codificació més curta.

Eixemple

Supongam que tenim la següent cadena de llongitut 20: 12349999123499991234, i estem utilisant un método de compressió que funciona en un caràcter especial (digam ) seguit d'un número d'entrada d'una taula o diccionari de térmens que es repetixen. Supongam que tenim un algoritme que llig la cadena de quatre caràcters. Mirant en la nostra cadena, el nostre algoritme podria elegir els valors 1234 i 9999 per a colocar a en el diccionari. Llavors 1234 seria l'entrada 0 i 9999 l'entrada 1. Ara la cadena es pot expressar com:

01010

Evidentment esta és molt més talla que la cadena original, a pesar de que almagasenar el diccionari també costarà espai. Aixina i tot, quant més es repetixquen eixos patrons en una cadena més llarga, tant millor serà el nivell de compressió.

El nostre algoritme pot millorar encara, al vore la cadena en grups de més de 4 caràcters. En eixe cas pot posar 12349999 i 1234 en el diccionari, resultant en una cadena encara més curta:

001

Supongam ara la següent cadena:

1234999988884321

Esta cadena és incompresible pel nostre algoritme. Els únics patrons que es repetixen són 88 i 99. Si guardem eixos dos valors en el nostre diccionari el resultat de la compressió seria:

123411004321

Desafortunadament la llongitut d'este resultat és tan llarga com lo és la cadena original, perque les nostres entrades per als elements del diccionari tenen una llongitut de 2, i els elements pels quals es reemplacen també. D'ahí, esta cadena és incompresible pel nostre algoritme.