Que tipo de codificação posso usar para tornar uma string mais curta?

Estou interessado em codificar uma sequência que possuo e estou curioso para saber se existe um tipo de codificação que possa ser usado que inclua apenas caracteres alfanuméricos e numéricos e, de preferência, reduza o número de caracteres necessários para representar a sequência.

Até agora, observei o uso da codificação Base64 para fazer isso, mas parece aumentar minha string e, às vezes, inclui as ==que eu gostaria de evitar. Exemplo:

nome do teste | 120101

torna-se

dGVzdCBuYW1lfDEyMDEwMQ ==

que varia de 16 a 24 caracteres e inclui caracteres não alfanuméricos.

Alguém sabe de um tipo diferente de codificação que eu poderia usar para atender aos meus requisitos? Pontos de bônus se ele estiver incorporado na estrutura .NET ou se houver uma biblioteca de terceiros que fará a codificação.

O final '=' ou '==' no Base64 está lá apenas para transformar o número de caracteres em um múltiplo de 4. Você pode removê-lo, pois você sempre pode colocá-lo novamente mais tarde. Observe que Base64 é chamado porque usa 64 caracteres distintos. Letras maiúsculas, minúsculas e dígitos, são 62. Portanto, o Base64 também usa '/' e '+', que podem ou não ser adequados à sua conta.

Geralmente, se você deseja codificar seqüências arbitrárias de bytes em caracteres alfanuméricos, há necessariamente alguma extensão de comprimento em algum lugar, porque existem 256 valores possíveis para um byte e apenas 62 caracteres alfanuméricos. Às vezes é chamado de princípio do buraco de pombo . Um esquema de codificação deve ter uma extensão de comprimento médio de um log de fator 256 / log 62 = 1,344 (média em todas as seqüências de bytes); caso contrário, isso significa que alguns pombos estão sendo esmagados até a morte em algum lugar e você não os recuperará sem danos (o que significa: duas seqüências distintas codificadas na mesma, para que a decodificação não funcione de maneira confiável).

Agora, é bem possível que suas seqüências não sejam exatamente "sequências de bytes uniformemente aleatórios"; suas seqüências têm algum significado, o que significa que a maior sequência possível de bytes não ocorrerá, porque não têm sentido. Nessa base, você provavelmente pode criar um esquema de codificação que terá uma extensão de comprimento menor que a Base64 genérica (ou Base62, se você precisar se ater a caracteres alfanuméricos estritos). Isso é compactação de dados sem perdas . Ele trabalha sobre um modelo probabilístico claramente definido do que pode aparecer como entrada.

Resumo: um esquema genérico para codificar cadeias de caracteres em seqüências alfanuméricas, de forma que nenhuma ou pequena extensão de comprimento ocorra, não pode existir; é uma impossibilidade matemática. Provavelmente, pode existir um esquema específico projetado para o tipo de string de entrada que você espera (mas como você não diz que tipo de string pode encontrar, ninguém pode ajudá-lo).

A recodificação de caracteres geralmente é feita quando o sistema receptor não pode processá-los. Por exemplo, BASE64 está representando dados usando 6 bits (2 ⁶ , portanto, 64) de caracteres para representar seqüências de dados mais longas (o "==" que às vezes aparece no final é preenchido para alinhamento). Isso ocorre porque o arquivo de imagem no e-mail pode ter 0xFE nele e o servidor de correio ficará infeliz ao transmitir isso (ou qualquer outro caractere tradicionalmente não imprimível).

Não há codificação que "reduz o tamanho". Codificações são apenas mapeamentos de bits para o caractere que eles representam. Dito isto, o ASCII é um conjunto de caracteres de 7 bits (codificação) que geralmente é armazenado em 8 bits de espaço. Se você limitar os intervalos aceitos, também poderá eliminar os caracteres de controle.

O uso desse método significa que você precisa escrever as coisas no nível do bit, e isso também é um pouco infernal com a velocidade e as instruções da máquina, porque todas as máquinas modernas têm alinhamentos que são múltiplos de 8 bits. É por isso que, por exemplo, o Unicode é UTF-8, UTF-16 e UTF-32.

Se você estiver fazendo isso por segurança (foi por isso que publicou no Security.SE, certo?), Basta filtrar as coisas e armazená-las normalmente. Se você estiver fazendo isso para economizar espaço, considere se todo o código extra e o tempo de acesso mais lento (porque a maioria das entradas cruzam os limites de endereço) valem a economia de espaço.

By the by, a seguir, é um trecho de um curso de CS em que tivemos que converter ASCII de armazenamento de 8 bits para 7 bits:

    memset(dest,0x00,8);
    memcpy(dest, source, length);

    for (int i = 0; i < 8; i++) {
            if (dest[i] & 0x80) {
                    fprintf(stderr, "%s: %s\n", dest, "Illegal byte sequence");
                    exit(EILSEQ);
            }
    }

    dest[0] = 0x7F & dest[0] | 0x80 & dest[1] << 7;
    dest[1] = 0x3F & dest[1] >> 1 | 0xC0 & dest[2] << 6;
    dest[2] = 0x1F & dest[2] >> 2 | 0xE0 & dest[3] << 5;
    dest[3] = 0x0F & dest[3] >> 3 | 0xF0 & dest[4] << 4;
    dest[4] = 0x07 & dest[4] >> 4 | 0xF8 & dest[5] << 3;
    dest[5] = 0x03 & dest[5] >> 5 | 0xFC & dest[6] << 2;
    dest[6] = 0x01 & dest[6] >> 6 | 0xFE & dest[7] << 1;
    dest[7] = 0x00; //Clearing out

Você pode compactar os dados com, por exemplo, gzip, bzip2 ou lzma e, em seguida, percorrer a base64 para limitar o conjunto de caracteres usado. Isso é benéfico apenas em cadeias maiores de centenas de bytes ou mais.

por que não usar compressão LZ? isso pode ser uma maneira decente de compactar uma string, mas seria mais eficiente no caso de strings longas. Quanto tempo dura a sequência de destino que você deseja codificar?