Quel type d'encodage puis-je utiliser pour raccourcir une chaîne?

Je suis intéressé par l'encodage d'une chaîne que j'ai et je suis curieux de savoir s'il existe un type d'encodage pouvant être utilisé qui inclura uniquement des caractères alphanumériques et qui raccourcirait de préférence le nombre de caractères nécessaires pour représenter la chaîne.

Jusqu'à présent, j'ai envisagé d'utiliser l'encodage Base64 pour ce faire, mais cela semble allonger ma chaîne et inclut parfois ==ce que j'aimerais éviter. Exemple:

nom du test | 120101

devient

dGVzdCBuYW1lfDEyMDEwMQ ==

qui va de 16 à 24 caractères et comprend des caractères non alphanumériques.

Quelqu'un connaît-il un autre type d'encodage que je pourrais utiliser pour répondre à mes besoins? Points bonus s'il est intégré au framework .NET ou s'il existe une bibliothèque tierce qui effectuera l'encodage.

Le dernier '=' ou '==' dans Base64 n'est là que pour rendre le nombre de caractères un multiple de 4. Vous pouvez le supprimer, car vous pouvez toujours le remettre plus tard. Notez que Base64 est appelé ainsi car il utilise 64 caractères distincts. Les majuscules, les minuscules et les chiffres, c'est 62. Donc, Base64 utilise également '/' et '+', qui peuvent ou non correspondre à votre facture.

D'une manière générale, si vous souhaitez coder des séquences arbitraires d'octets en caractères alphanumériques, il y a nécessairement une certaine extension de longueur quelque part, car il y a 256 valeurs possibles pour un octet et seulement 62 caractères alphanumériques. On l'appelle parfois le principe du pigeonnier . Un schéma de codage doit avoir une extension de longueur moyenne d'un facteur log 256 / log 62 = 1,344 (moyenne sur toutes les séquences d'octets); sinon, cela signifie que certains pigeons sont écrasés à mort quelque part et que vous ne les récupérerez pas sans dommage (ce qui signifie: deux chaînes distinctes codées de la même manière, le décodage ne peut donc pas fonctionner de manière fiable).

Maintenant, il est fort possible que vos chaînes ne soient pas exactement des "séquences d'octets uniformément aléatoires"; vos chaînes ont une signification, ce qui signifie que la plupart des séquences d'octets possibles ne se produiront pas, car elles n'ont pas de sens. Sur cette base, vous pouvez probablement concevoir un schéma de codage qui entraînera moins d'extension de longueur que le Base64 générique (ou le Base62 si vous devez vous en tenir à des caractères alphanumériques stricts). Il s'agit d' une compression de données sans perte . Il fonctionne sur un modèle probabiliste clairement défini de ce qui peut apparaître en entrée.

Résumé: un schéma générique pour coder des chaînes en séquences alphanumériques de telle sorte qu'il n'y ait jamais ou peu d'extension de longueur ne peut exister; c'est une impossibilité mathématique. Un schéma spécifique adapté au type de chaîne d'entrée que vous attendez peut probablement exister (mais comme vous ne dites pas quel type de chaîne vous pouvez rencontrer, personne ne peut vous aider à ce sujet).

Le recodage des caractères est généralement effectué lorsque le système récepteur ne peut pas les traiter. Par exemple, BASE64 représente des données en utilisant 6 bits (2 ⁶ , donc 64) de caractères pour représenter des séquences de données plus longues (le "==" parfois apparaissant à la fin est un remplissage pour l'alignement). En effet, votre fichier image dans le courrier électronique peut contenir 0xFE et votre serveur de messagerie sera malheureux de le transmettre (ou tout autre caractère traditionnellement non imprimable).

Il n'y a pas d'encodage qui "réduit la taille". Les encodages ne sont que des mappages de bits au caractère qu'ils représentent. Cela dit, ASCII est un jeu de caractères (codage) de 7 bits qui est souvent stocké dans 8 bits d'espace. Si vous limitez les plages que vous acceptez, vous pouvez également éliminer les caractères de contrôle.

L'utilisation de cette méthode signifie que vous devez écrire des choses au niveau des bits, et cela joue aussi un peu l'enfer avec la vitesse et les instructions de la machine car toutes les machines modernes ont des alignements qui sont des multiples de 8 bits. C'est, par exemple, pourquoi Unicode est UTF-8, UTF-16 et UTF-32.

Si vous faites cela pour la sécurité (c'est pourquoi vous l'avez posté sur Security.SE, non?), Il suffit de filtrer les choses et de les stocker normalement. Si vous faites cela pour économiser de l'espace, demandez-vous si tout le code supplémentaire et le temps d'accès plus lent (car la plupart des entrées dépasseront les limites des adresses) valent les économies d'espace.

D'ailleurs, ce qui suit est un extrait d'un cours CS où nous avons dû convertir ASCII du stockage 8 bits en 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

Vous pouvez compresser les données avec par exemple gzip, bzip2 ou lzma, puis exécuter en base64 pour limiter le jeu de caractères utilisé. Cela n'est bénéfique que sur des chaînes plus grandes de centaines d'octets ou plus.

pourquoi ne pas utiliser la compression LZ? cela peut être une façon décente de compresser une chaîne, mais serait plus efficace en cas de longues chaînes. Quelle est la longueur de la chaîne cible que vous souhaitez encoder?