String incompressível - Incompressible string

Uma string incompressível é uma string com complexidade de Kolmogorov igual ao seu comprimento, de modo que não tem codificações mais curtas.

Exemplo

Suponha que temos a string 12349999123499991234 e estejamos usando um método de compressão que funciona colocando um caractere especial na string (digamos '@') seguido por um valor que aponta para uma entrada em uma tabela de pesquisa (ou dicionário) de valores repetidos . Vamos imaginar que temos um algoritmo que examina a string em blocos de 4 caracteres. Olhando para nossa string, nosso algoritmo pode escolher os valores 1234 e 9999 para colocar em seu dicionário. Digamos que 1234 seja a entrada 0 e 9999 seja a entrada 1. Agora a string pode se tornar:

@ 0 @ 1 @ 0 @ 1 @ 0

Obviamente, isso é muito mais curto, embora armazenar o dicionário em si custará algum espaço. Entretanto, quanto mais repetições houver na string, melhor será a compressão.

Nosso algoritmo pode se sair melhor, porém, se puder visualizar a string em blocos maiores que 4 caracteres. Em seguida, ele pode colocar 12349999 e 1234 no dicionário, fornecendo-nos:

@ 0 @ 0 @ 1

Ainda mais curto. Agora considere outra string:

1234999988884321

Esta string é incompressível pelo nosso algoritmo. As únicas repetições que ocorrem são 88 e 99. Se armazenássemos 88 e 99 em nosso dicionário, produziríamos:

1234 @ 1 @ 1 @ 0 @ 04321

Infelizmente, isso é tão longo quanto a string original, porque nossos marcadores de posição para itens no dicionário têm 2 caracteres e os itens que eles substituem têm o mesmo comprimento. Portanto, essa string é incompressível por nosso algoritmo.

Referências