Eu sempre falhei em dar uma resposta para os desafios da complexidade do kolmogorov, que exigem a compactação de strings, a principal razão é que não sei usar as ferramentas de compactação de strings tão efetivamente quanto deveria .

Por esse motivo, postei esta pergunta. Diferentemente das minhas outras perguntas, este não é um idioma específico, o que significa que, se você puder pensar em alguma dica em seu próprio idioma, poderá publicá-la (desde que especifique o idioma). Dicas gerais também são apreciadas.

Então, como posso usar as ferramentas de compactação de string para obter a máxima eficácia?

Conversão base (CJam)

Uma maneira fácil de codificar seqüências de caracteres ASCII que não iniciam com um byte nulo é converter da base 128 em número inteiro e, em seguida, na base 256:

128b256b:c              e# Prints encoded string.
128b256b:c`"256b128b:c" e# Prints encoded string with decoder.

Isso usa 7 bits para codificar cada caractere ASCII.

Se a string original consistir apenas em, por exemplo, letras minúsculas e não começar com a , podemos começar mapeando "a...z"para [0 ... 25]e proceda da seguinte forma:

'afm26b256b:c               e# Prints encoded string.
'afm26b256b:c`"256b26b'af+" e# Prints encoded string with decoder.

Finalmente, se a string original tiver apenas alguns caracteres únicos (comum na arte ASCII), geralmente é melhor especificar explicitamente o alfabeto.

Por exemplo:

" +-/\|"f#6b256b:c                       e# Prints encoded string.
" +-/\|"f#6b256b:c`"256b6b"" +-/\|"`"f=" e# Prints encoded string with decoder.

Como regra geral, você deseja que o primeiro caractere da string original seja o segundo caractere do alfabeto, o próximo caractere distinto da string original seja o primeiro caractere do alfabeto, o próximo caractere distinto da string original a ser o terceiro caractere do alfabeto, o próximo caractere distinto da string original a ser o quarto caractere do alfabeto, etc.

O codificador do último exemplo funciona da seguinte maneira:

" +-/\|"f# e# Replace each character by its index in that string.
6b256b     e# Convert from base 6 (length of the alphabet) to base 256.
:c         e# Cast each digit to character.

O decodificador do último exemplo funciona da seguinte maneira:

256b6b     e# Convert from base 256 to base 6.
" +-/\|"f= e# Replace each digit by the corresponding character of the alphabet.

Perguntas de complexidade maior de Kolmogorov com alguma estrutura, mas nenhuma fórmula simples (por exemplo, letras de músicas) normalmente se beneficiam de uma abordagem baseada em gramática. Em essência, você extrai substrings repetidos e os codifica de alguma forma. É isso que Lempel-Ziv faz, usando uma classe de gramática bastante restrita; se você usar gramáticas mais gerais, precisará descobrir como codificar as regras. Por exemplo, uma abordagem aqui é a "codificação de deslocamento", em que você desloca cada byte de origem pelo número de regras ( n), atribui bytes 1às nregras, usa o 0byte para separar regras e substitui repetidamente byte ipela regra avaliada i. Finalmente, você desfaz o deslocamento subtraindo nde cada byte.

Na verdade, eu escrevi um programa Java que implementa várias abordagens:

A maioria das abordagens segue um processo de duas fases. Na primeira fase, a cadeia é convertida em uma gramática que a gera; na segunda fase, a gramática é convertida em um programa GolfScript. As implementações da primeira fase são amplamente baseadas em Charikar, Lehman, Liu, Panigrahy, Prabhakaran, Sahai e Shelat (2005). O menor problema gramatical , Teoria da Informação, IEEE Transactions on, 51 (7), 2554-2576.

Ele também inclui uma abordagem Lempel-Ziv, uma abordagem de codificação de base e uma abordagem de codificação de comprimento de execução, e identifica aquela que fornece o programa mais curto.

Stax

Na linguagem de golfe do código Stax , há uma pequena ferramenta útil chamada compressor literal de strings . Eu não sei como ele funciona, exatamente, mas há um outro onde eu não sei como funciona. Ele converte seqüências de caracteres em números e depois na Base 256. É o CP437 , com 0x00 e 0xFF convertidos para cópia. É PackedStax. Você pode converter suas cordas com o compressor literal de cordas e depois compactá-las, para uma boa compactação.

Usando esse processo, a cadeia "Esta cadeia possui trinta e dois bytes" pode ser convertida em v * "A] - | W4]} 3"% (a cadeia compactada geralmente é cercada por reticulares para diferenciar uma cadeia normal no Stax ) e finalmente para üvìë! [┴╩qJu ← ▓α para uma compressão / redução de 18 bytes, mais da metade.