5

Preciso reduzir o tamanho de uma string, porém mantê-la em um range de caracteres pré-determinados.

Uso uma rotina de criptografia que o resultado retornado por ela é um conjunto de caracteres hexadecimal, par a par, representando o código ASCII dos caracteres de uma frase.
Ou seja, ao final do processamento dessa rotina o resultado ainda é submetido a uma conversão usando a função para conversão em hexadecimal:

for char in valResult do
    result := result + IntToHex( ord(char), 2);

O resultado retornado por essa rotina é o que preciso compactar.

Porém, em breve estaremos mudando esse tipo de rotina para criptografias fortes, com criptografias assimétricas, e então será necessário reduzir o tamanho/compactar o resultado do retorno desse tipo de rotina.

Então, Como fazer compactação de string de forma que o resultado dessa rotina teria apenas os caracteres pré-determinados, no meu caso os seguintes caracteres: A-Z e 0-9?

Para facilitar o entendimento, bom seria se pudéssemos ter um exemplo em , ou até mesmo em outra linguagem que depois puderia ser convertido.

3
  • @Bacco, A-Z e 0-9 apenas. Letras somente no maiúsculo. Grato!
    – user3628
    Commented 20/04/2014 às 2:11
  • @Bacco, desculpe, não faço idéia!
    – user3628
    Commented 20/04/2014 às 2:18
  • Isso tá tenso! =) Preciso de uma string com menor tamanho e utilizando esses caracteres para poder resolver meu problema. Não dá para abrir mão de um ou de outro. Todavia, enquanto houver esperança, há luta (rs). Vou continuar insistindo um pouco mais para tentar achar uma solução para esse problema.
    – user3628
    Commented 20/04/2014 às 2:23

1 Resposta 1

2
+50

Como já citado, no caso geral esse problema é impossível: nenhum algoritmo de compactação possui desempenho positivo no caso médio (Princípio da Casa dos Pombos), e ao restringir quais caracteres são permitidos na saída você tem menos bits pra representar a mesma informação - de modo que a demanda por espaço aumenta. Entretanto, em casos específicos pode haver uma solução - só que nem um pouco fácil. Não conheço Delphi, de modo que não vou arriscar produzir um exemplo, mas vou "colocar as cartas na mesa", de modo que você possa avaliar suas possibilidades.

  1. Se suas string forem aleatórias (ex.: uma chave criptográfica gerada aleatoriamente), desista. É teoricamente impossível, nem precisa esperar por uma resposta melhor (a menos que alguém se disponha a explicar por que é impossível, e você tenha interesse em ouvir).

  2. Se suas strings tiverem baixa entropia (ex.: "masculino" e "feminino"), então deve ser possível compactá-las de alguma forma (ex.: "m" e "f"). Textos em linguagem natural (ex.: português) normalmente satisfazem esse requisito, assim como dados que ocupam mais espaço que o mínimo necessário para representar a informação que eles carregam (como no exemplo do gênero acima). Problema: essa compactação tem de reduzir sua string original no mínimo para uns 70% do original pra você continuar no zero-a-zero (assumindo um aumento de 40% ao codificar na base 36, conforme comentário do Bacco) - e mais ainda se você quiser que ela fique menor.

    • O ideal é que isso seja feito usando um algoritmo de compressão já pronto - menos trabalho pra você, e um resultado provavelmente melhor (deixa os detalhes complicados pros profissionais). Isso é mais factível se as strings forem longas. Um exemplo besta seria criar um arquivo com o conteúdo da string, zipar, e converter o arquivo binário resultante pra base 36 (e passar pra maiúsculas).

    • Se você tem uns poucos (2 ou 4) métodos diferentes de compressão que têm resultados melhores ou piores dependendo da string, pode ser vantagem usar 1 ou 2 bits pra dizer qual método está sendo usado, e em seguida a string comprimida (Aviso: 99% do tempo é desnecessário, mesmo porque muitos algoritmos de compressão já fazem isso pra você).

    • Se um método pronto não estiver disponível, e você precisar implementar à mão, sugiro estudar (e se necessário adaptar) um dos algoritmos clássicos de compressão, como a Codificação de Huffman. É mais simples do que parece à primeira vista, e ainda abre espaço para otimizações caso seja possível mover parte da informação para fora da string (ver próximo item).

  3. Toda e qualquer informação que é igual para toda string deve ser retirada da string. Um problema dos algoritmos de compressão é que - além da string comprimida propriamente dita - eles têm que armazenar também o dicionário que mapeia bits/bytes a sequências de caracteres. Se você puder empregar um dicionário único para todas as strings (e esse dicionário seja bom o bastante para comprimi-las todas), então o problema se torna bem mais factível.

    • Exemplo: se todas suas string começam com AVE, aB1 ou 0*( sem exceção, então você pode substituir as três primeiras letras da mesma pelo prefixo binário 0, 10 ou 11, e então comprimir da quarta letra pra frente.

    • Uma forma de aplicar isso seria pegar um conjunto grande de strings (todas que estiverem disponíveis), concatená-las, e aplicar a codificação de huffman ao resultado. Então você pega a tabela de símbolos e põe ela hardcoded no seu código-fonte. Daí pra frente toda string a ser compactada pode usar a mesma tabela, de modo que é praticamente garantido que elas ficarão menores ao passar por esse processo (e menos que alguma delas seja substancialmente diferente do conjunto inicial - ver item 1 novamente).

Notas:

  • Normalmente eu sugeriria utilizar a base 32 em vez da 36, para simplificar muito a conversão. Mas como no seu caso cada fração de bit conta, uma boa saída pode ser usar uma biblioteca de "inteiros com precisão arbitrária" (BigInt) ou "conjuntos de bits" (BitSet). Aqui tem uma, mas não sei avaliar se serve pra esse propósito. A idéia geral é: 1) criar um BigInt com os dados em binário resultantes da fase de compressão; 2) convertê-lo para uma string em base 36, usando alguma função da própria biblioteca. Para obter de volta a string original, basta fazer o processo inverso: cria o BigInt com os dados na base 36, pega os dados em binário e reverte o processo de compressão.

  • Eu expus de modo geral as possibilidades, sem entrar muito em detalhes para não ficar muito extenso. Se você puder detalhar mais o seu problema (i.e. colocar mais contexto), explicar melhor o que pretende fazer, por que, quais as suas limitações, com que tipos de dados está lidando, etc, então pode ser possível que enxerguemos uma saída inesperada. Em compressão, explorar casos particulares é um must. Da forma genérica que a pergunta está, receio que a primeira resposta recebida (i.e. "é impossível") seja de fato a correta...

4
  • Alterei o texto da pergunta, e acredito que ela se encaixe logo no primeiro ponto de sua resposta, ex.: uma chave criptográfica gerada aleatoriamente.
    – user3628
    Commented 20/04/2014 às 14:17
  • @Tiago Pelo que eu entendi na sua descrição, não é uma "chave criptográfica" que você quer comprimir, e sim o "ciphertext". Se for isso, há esperança sim! Vou atualizar a resposta, mas antes me fala: 1) Que tipos de dados estão sendo encriptados? Dá para comprimí-los antes da cifragem? 2) Qual o tamanho médio dessas strings? Uma criptografia forte acrescenta uns bytes a mais na string (IV ou nonce, e talvez um MAC), mas de outra forma não altera muito o seu comprimento. P.S. Já está definido qual algoritmo de criptografia que será usado?
    – mgibsonbr
    Commented 20/04/2014 às 17:09
  • @Tiago Ops, agora que eu li "criptografias assimétricas", então de fato há uma chave a ser transmitida sim... Nesse caso, o overhead será mais do que "uns poucos bytes". :( Esse me parece um problema bem complicado, por isso o máximo de contexto que você puder dar, melhor. Leia essa postagem no meta para entender melhor por que esse contexto é importante. Em particular nesse caso, onde uma solução generalizada é impossível, precisamos nos agarrar aos detalhes particulares.
    – mgibsonbr
    Commented 20/04/2014 às 17:20
  • Obrigado por toda a explicação. E nossa estratégia em relação ao problema foi redirecionada. É um assunto que pretendo me aprofundar, no caso, compactação, criptografia.. Nem sempre as respostas serão da forma que esperamos. Obrigado!
    – user3628
    Commented 20/04/2014 às 23:03

Você deve fazer log-in para responder a esta pergunta.