Che tipo di codifica posso usare per rendere una stringa più corta?

L'ultimo '=' o '==' in Base64 serve solo a rendere il numero di caratteri un multiplo di 4. Puoi rimuoverlo, poiché puoi sempre rimetterlo in un secondo momento. Nota che Base64 è così chiamato perché usa 64 caratteri distinti. Lettere maiuscole, lettere minuscole e cifre, questo è 62. Quindi Base64 usa anche '/' e '+', che possono o meno adattarsi al tuo conto.

In generale, se vuoi codificare sequenze arbitrarie di byte in caratteri alfanumerici, c'è necessariamente un'estensione di lunghezza da qualche parte, perché ci sono 256 valori possibili per un byte e solo 62 caratteri alfanumerici. A volte viene chiamato il principio del pigeonhole . Uno schema di codifica deve avere un'estensione di lunghezza media di un fattore log 256 / log 62 = 1.344 (media su tutte le sequenze di byte); in caso contrario, significa che alcuni piccioni vengono schiacciati a morte da qualche parte e non li riavrai senza danni (il che significa: due stringhe distinte codificate allo stesso modo, quindi la decodifica non può funzionare in modo affidabile).

Ora, è del tutto possibile che le tue stringhe non siano esattamente "sequenze di byte uniformemente casuali"; le tue stringhe hanno qualche significato che significa che la maggior parte della possibile sequenza di byte non si verificherà, perché sono prive di significato. Su questa base, è possibile escogitare uno schema di codifica che avrà un'estensione di lunghezza inferiore rispetto al Base64 generico (o Base62 se è necessario attenersi a caratteri alfanumerici rigorosi). Questa è compressione dei dati senza perdita . Funziona su un modello probabilistico chiaramente definito di ciò che può apparire come input.

Riepilogo: uno schema generico per codificare stringhe in sequenze alfanumeriche in modo tale che non si verifichi mai o nessuna estensione di lunghezza, non può esistere; è un'impossibilità matematica. Uno schema specifico su misura per il tipo di stringa di input che ci si aspetta probabilmente può esistere (ma dal momento che non si indica quale tipo di stringa si può incontrare, nessuno può aiutarti su questo).

I caratteri di ricodifica vengono generalmente eseguiti quando il sistema ricevente non può elaborarli. Ad esempio, BASE64 sta rappresentando i dati usando 6 bit (2 ⁶ , quindi 64) di caratteri per rappresentare sequenze di dati più lunghe (l'a volte "==" alla fine è padding per l'allineamento). Questo perché il tuo file di immagine in email potrebbe avere 0xFE al suo interno e il tuo server di posta sarà infelice a trasmettere questo (o qualsiasi altro carattere tradizionalmente non stampabile).

Non esiste codifica che "riduca le dimensioni". Le codifiche sono solo mappature di bit al personaggio che rappresentano. Detto questo, ASCII è un set di caratteri a 7 bit (codifica) che viene spesso memorizzato in 8 bit di spazio. Se limiti gli intervalli accettati, puoi anche eliminare i caratteri di controllo.

Usando questo metodo significa che devi scrivere cose a livello di bit, e suona anche un po 'di inferno con la velocità della macchina e l'amp; istruzioni perché tutte le macchine moderne hanno allineamenti multipli di 8 bit. Questo, ad esempio, è il motivo per cui Unicode è UTF-8, UTF-16 e UTF-32.

Se lo stai facendo per sicurezza (è per questo che l'hai postato su Security.SE, giusto?), basta filtrare le cose e salvarle normalmente. Se stai facendo questo per risparmiare spazio, considera se tutto il codice aggiuntivo e il tempo di accesso più lento (poiché la maggior parte delle voci supererà i confini degli indirizzi) vale lo spazio risparmiato.

By the, il seguente è uno snippet da un corso CS in cui abbiamo dovuto convertire ASCII da 8 bit di archiviazione a 7 bit:

    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

Puoi comprimere i dati con ad es. gzip, bzip2 o lzma e quindi eseguire tramite base64 per limitare il set di caratteri utilizzati. Questo è utile solo su stringhe più grandi di centinaia di byte o più.

perché non usare la compressione LZ? questo può essere un modo decente di comprimere una stringa, ma sarebbe più efficiente in caso di stringhe lunghe. Quanto è lunga la stringa di destinazione che vuoi codificare?