Peu d'emballage de tableau d'entiers

Je suis d'accord avec keraba que vous avez besoin d'utiliser quelque chose comme le codage de Huffman ou peut-être la Lempel-Ziv-Welch algorithme. Le problème avec peu d'emballage de la façon dont vous parlez, c'est que vous avez deux options:

• Choisir une constante n tel que le plus grand entier peut être représenté.
• Permettre n varier en fonction de la valeur.

La première option est relativement facile à mettre en œuvre, mais qui va vraiment faire perdre beaucoup d'espace, à moins que tous les entiers sont plutôt petits.

La deuxième option présente l'inconvénient majeur que vous avez à transmettre des changements dans la n d'une certaine manière dans la sortie bitstream. Par exemple, chaque valeur devra avoir une longueur associée. Cela signifie que vous êtes le stockage de deux entiers (quoique plus petit des entiers) pour chaque valeur d'entrée. Il ya une bonne chance que vous allez augmenter la taille du fichier avec cette méthode.

L'avantage de Huffman ou LZW est qu'ils créent des codes de telle façon que la longueur des codes peuvent être dérivées à partir de la sortie bitstream sans réellement le stockage de la longueur. Ces techniques permettent d'obtenir de très près à la limite de Shannon.

J'ai décidé de donner à votre idée de départ (constante n, supprimer les bits non utilisés et pack) a essayer pour le plaisir et voici l'implémentation naïve que je suis venu avec:

#include <sys/types.h>
#include <stdio.h>
int pack(int64_t* input, int nin, void* output, int n)
{
int64_t inmask = 0;
unsigned char* pout = (unsigned char*)output;
int obit = 0;
int nout = 0;
*pout = 0;
for(int i=0; i<nin; i++)
{
inmask = (int64_t)1 << (n-1);
for(int k=0; k<n; k++)
{
if(obit>7)
{
obit = 0;
pout++;
*pout = 0;
}
*pout |= (((input[i] & inmask) >> (n-k-1)) << (7-obit));
inmask >>= 1;
obit++;
nout++;
}
}
return nout;
}
int unpack(void* input, int nbitsin, int64_t* output, int n)
{
unsigned char* pin = (unsigned char*)input;
int64_t* pout = output;
int nbits = nbitsin;
unsigned char inmask = 0x80;
int inbit = 0;
int nout = 0;
while(nbits > 0)
{
*pout = 0;
for(int i=0; i<n; i++)
{
if(inbit > 7)
{
pin++;
inbit = 0;
}
*pout |= ((int64_t)((*pin & (inmask >> inbit)) >> (7-inbit))) << (n-i-1);
inbit++;
}
pout++;
nbits -= n;
nout++;
}
return nout;
}
int main()
{
int64_t input[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
int64_t output[21];
unsigned char compressed[21*8];
int n = 5;
int nbits = pack(input, 21, compressed, n);
int nout = unpack(compressed, nbits, output, n);
for(int i=0; i<=20; i++)
printf("input: %lld   output: %lld\n", input[i], output[i]);
}

C'est très inefficace parce que c'est pas un peu à la fois, mais c'était la façon la plus simple à mettre en œuvre, sans aborder les questions de la endianess. Je n'ai pas testé ce soit avec un large éventail de valeurs, celles de l'essai. Aussi, il n'y a pas de vérification des limites et il est présumé que les tampons de sortie sont assez long. Donc, ce que je veux dire, c'est que ce code est probablement seulement bon pour des fins pédagogiques pour vous aider à démarrer.

La plupart de tout algorithme de compression obtiendrez proche du minimum d'entropie nécessaire pour coder les entiers, par exemple, le codage de Huffman, mais accéder à un tableau sera non négligeable.

Si vous avez de taille fixe, par exemple, vous savez que votre numéro est 38bit plutôt que de 64, vous pouvez construire des structures à l'aide de bits spécifications. Amusant vous avez également des éléments plus petits pour tenir dans l'espace restant.

struct example {
/* 64bit number cut into 3 different sized sections */
uint64_t big_num:38;
uint64_t small_num:16;
uint64_t itty_num:10;
/* 8 bit number cut in two */
uint8_t  nibble_A:4;
uint8_t  nibble_B:4;
};

Ce n'est pas big/little endian sûr sans cerceau de saut, ne peut donc être utilisé à l'intérieur d'un programme plutôt que dans les données exportées au format. C'est assez souvent utilisé pour stocker des valeurs booléennes simples bits sans définir des décalages et des masques.

Je ne pense pas que vous pouvez éviter une itération à travers les éléments.
Autant que je sache, le codage Huffman exige que les fréquences de "symboles", qui, sauf si vous savez les statistiques du "processus de génération de nombres entiers, vous aurez à calculer (par itération à travers chaque élément).