J'ai du code C qui stocke des chaînes ASCII en mémoire en tant que longueur de quatre octets suivie de la chaîne. Les longueurs de la chaîne sont dans la plage 10-250 octets.
Réduire l'occupation J'aimerais compresser chaque chaîne individuellement à la volée, conservant toujours la longueur (de la chaîne compressée) suivie de la chaîne compressée.
Je ne veux pas comprimer à une portée plus grande que les chaînes individuelles car toute chaîne peut être lue / écrite à tout moment.
Quelles bibliothèques / algorithmes sont disponibles pour ce faire?
Merci pour votre aide. Nickb
6 Réponses :
zlib est toujours à votre service - il a une très petite surcharge pour les cas lorsque la chaîne contient des données non compressables, C'est relativement rapide, gratuit et peut être facilement intégré aux programmes C et C ++.
Zlib est définitivement votre ami ici, mais assurez-vous d'effectuer quelques tests pour détecter la longueur moyenne de la chaîne à laquelle la compression commence à être bénéfique, en raison de la petite générale des en-têtes de compression.
Par exemple, vous découvrirez peut-être que moins de 20 caractères, la chaîne compressée est effectivement plus grande, et ne compriment donc que les chaînes plus longues.
Et si vous pouvez épargner 1 bit du champ de taille pour signaler si la chaîne est comprimée ou non, vous n'avez même pas à deviner: tenter juste de compresser chaque chaîne. Si cela devient plus petit, rangez-le compressé. Si ce n'est pas le cas, rangez-le non compressé. C'est à peu près ce que Pkzip permet (et j'assume d'autres conteneurs compressés, c'est juste pkzip est celui que j'avais mis en œuvre une fois). Malheureusement, la gamme de taille 10-250 n'admette pas efficacement un bit de «rechange» sur une architecture 8 bits.
Pourquoi utiliser une longueur de 4 octets lorsque les chaînes sont de 10 à 2550 octets longues, utilisez une longueur d'octets qui vous sauvera 3 octets par chaîne seule.
est la textuelle de données uniquement à partir de 0-9 A-Z ou de certains sous-ensemble ?? Si tel est le cas, reprochez-le pour utiliser ce sous-ensemble et économiser quelques bits par caractère.
Regardez maintenant http://gnose.cx/publish/programming/Compression_primer. HTML dans la section de codage Huffman et la section Lempel-Zev.
qui devrait vous aider à démarrer.
Je ne suis pas sûr que les approches de compression de ZLIB ou de LZW fonctionnent bien en cas de compression individuelle des chaînes courtes de moins de 250 octets. Les deux nécessitent généralement de créer un dictionnaire assez important avant que des gains de compression significatifs soient vus.
Peut-être un simple codage de Huffman avec un arbre de codage fixe, ou un partagé entre toutes les instances des cordes? Aussi, avez-vous vu le codage ZSCII utilisé pour comprimer les chaînes courtes sur des micro-ordinateurs contraints de mémoire dans les années 80?
La plupart des algorithmes de compression ne fonctionnent pas très bien avec des cordes courtes. Voici quelques algorithmes de compression conçus pour compresser des chaînes de texte anglais courtes. Bien qu'ils puissent gérer n'importe quel octet arbitraire dans la chaîne en plainte, De tels octets rendent souvent les données "comprimées" plus longtemps que le texte en clair. Donc, c'est une bonne idée du compresseur de stocker des données «non compressables» inchangées et définissez un drapeau «littéral» sur ces données (comme suggéré Steve Jessop).
Lorsque vous utilisez plusieurs chaînes telles que celles-ci, il est possible d'éviter la surcharge de pointeur pour chaque chaîne (4 ou 8 octets chacune) en les concaténant avec \ 0 code> S (1 octet) et à l'aide d'une recherche Fonction. #include <stdio.h>
/* each "string" is prefixed with its octal length */
static const char lenstrings[]="\05hello\05world\04test";
char * ithstring(const char *s, unsigned n){
while(n--){
s+=*s+1;
}
return s;
}
int main(void) {
char *s=ithstring(lenstrings,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 <unistd.h>
return 0;
}