Compression de chaînes ASCII en C

J’ai un code C qui stocke les chaînes ASCII en mémoire sous la forme d’une longueur de quatre octets suivie de la chaîne. Les longueurs de chaîne sont comsockets entre 10 et 250 octets.

Pour réduire l’occupation, j’aimerais compresser chaque chaîne individuellement à la volée tout en conservant la longueur (de la chaîne compressée) suivie de la chaîne compressée.

Je ne veux pas compresser à une scope plus grande que des chaînes individuelles, car toute chaîne peut être lue / écrite à tout moment.

Quelles bibliothèques / algorithmes sont disponibles pour cela?

Merci de votre aide. NickB

ZLib est toujours à votre service – il y a très peu de surcharge pour les cas où la chaîne contient des données non compressibles, elle est relativement rapide, gratuite et peut être facilement intégrée aux programmes C et C ++.

La plupart des algorithmes de compression ne fonctionnent pas très bien avec des chaînes courtes. Voici quelques algorithmes de compression conçus pour compresser des chaînes de texte anglais courtes. S’ils peuvent gérer n’importe quel octet arbitraire dans la chaîne de texte en clair, ces octets rendent souvent les données “compressées” plus longues que le texte en clair. C’est donc une bonne idée pour le compresseur de stocker les données “non compressibles” sans les modifier et de définir un indicateur “littéral” sur ces données (comme suggéré par Steve Jessop).

  • “encodage base 40”: compression maximale 3: 2
  • “Code standard Zork pour l’échange d’informations” (ZSCII): compression maximale 3: 2
  • compression de la paire d’octets : compression maximale 2: 1
  • une table de Huffman statique partagée entre toutes les chaînes (comme suggéré par cygil).
    • idéalement, formé à partir des fréquences de caractères exactes de toutes vos données réelles.
    • Varicode: compression maximale 2: 1
  • Compression PalmDoc (compression d’une paire d’octets + une variante simple de LZ77).

Je ne suis pas sûr que les approches de compression zlib ou LZW fonctionneront bien dans le cas de la compression individuelle de chaînes courtes de moins de 250 octets. Les deux nécessitent généralement la création d’un dictionnaire assez volumineux avant que des gains de compression importants ne soient constatés.

Peut-être un simple codage Huffman avec une arborescence de codage fixe ou partagée entre toutes les occurrences des chaînes? En outre, avez-vous vu le codage ZSCII utilisé pour compresser des chaînes courtes sur des micro-ordinateurs soumis à une contrainte de mémoire dans les années 80?

lien texte

Zlib est certainement votre ami ici, mais assurez-vous d’effectuer quelques tests pour détecter la longueur moyenne de chaîne à laquelle la compression commence à être bénéfique, en raison du faible surcoût des en-têtes de compression.

Par exemple, vous découvrirez peut-être que moins de 20 caractères suffisent pour que la chaîne compressée soit plus grande et que, par conséquent, comprenne uniquement les chaînes les plus longues.

Pourquoi utiliser une longueur de 4 octets lorsque les chaînes ont une longueur de 10 à 250 octets, utilisez une longueur de 1 octet qui vous fera économiser 3 octets par chaîne uniquement.

Les données sont-elles uniquement textuelles, à savoir 0-9 Az ou un sous-ensemble? si c’est le cas, ré-encodez-le pour utiliser ce sous-ensemble et enregistrez quelques bits par caractère.

Regardez maintenant http://gnosis.cx/publish/programming/compression_primer.html dans les sections codage de Huffman et lempel-zev.

Cela devrait vous aider à démarrer.

Lorsque vous utilisez plusieurs chaînes de ce type, il est possible d’éviter la surcharge du pointeur pour chaque chaîne (4 ou 8 octets chacune) en les concaténant avec \0 s (1 octet) et en utilisant une fonction de recherche.

 #include  static const char ssortingngs[]="hello\0world\0test"; char * nthssortingng(const char *s, unsigned n){ while(n--) while(*s++) ; return s; } int main(void) { printf("%s\n",nthssortingng(ssortingngs,1)); return 0; } 

Toutefois, si la longueur de la chaîne est inférieure à UCHAR_MAX, vous pouvez optimiser la recherche en utilisant les espaces réservés avec zéro octet pour stocker les longueurs (plus 1 au début). Cela ne coûte qu’un octet de données supplémentaire, mais évite beaucoup fonction de recherche.

 #include  /* each "ssortingng" is prefixed with its octal length */ static const char lenssortingngs[]="\05hello\05world\04test"; char * ithssortingng(const char *s, unsigned n){ while(n--){ s+=*s+1; } return s; } int main(void) { char *s=ithssortingng(lenssortingngs,1); /* use the length because we don't have terminating \0 */ printf ("%.*s",(unsigned char)*s,s+1); //write(1,s+1,(unsigned char)*s); //POSIX variation via  return 0; } 

Pour les deux variantes, il est préférable de garder en premier les chaînes les plus nécessaires; Cependant, la deuxième méthode vous permettra d’utiliser des données compressées (choisissez celle qui convient le mieux à vos données – la réponse de David Cary contient une liste de solutions utilisables) tant que vous ajustez les séparateurs de longueur à la longueur compressée.

Remarque: pour obtenir le maximum de compression des compresseurs standard, vous souhaiterez probablement modifier le champ de longueur de leurs en-têtes afin qu’ils soient unsigned char (ou unsigned short si la longueur de la chaîne dépasse 256 mais pas 65 536 octets), car la plupart d’entre eux essaieront compression de gros fichiers (cela pourrait économiser 3-7 octets par chaîne)