Emballage de bits d'une éventail d'entiers

La plupart des algorithmes de compression se rapprocheront de l'entropie minimale nécessaire pour encoder les entiers, par exemple, codage de Huffman, mais l'accédant comme un tableau sera non trivial.

Je suis d'accord avec Keraba que vous devez utiliser quelque chose comme le codage de Huffman ou peut-être l'algorithme de Lempel-ZIV-WELCH. Le problème avec l'emballage de la manière dont vous parlez est que vous avez deux options:

• Choisissez une constante n telle que le plus grand nombre d'entier peut être représenté. Li>
• Autoriser N de varier de la valeur à la valeur. LI> ul>

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

  La deuxième option a l'inconvénient majeur que vous avez Transmettre des changements de N en quelque sorte dans la sortie Bitstream. Par exemple, chaque valeur devra avoir une longueur associée à celle-ci. Cela signifie que vous stockez deux entiers (bien que des entiers plus petits) pour chaque valeur d'entrée. Il y a une bonne chance que vous augmentez la taille du fichier avec cette méthode. P>

  L'avantage de Huffman ou de LZW est qu'ils créent des livres de codes de manière à ce que la longueur des codes puisse être dérivée du bits de sortie de la sortie. sans stocker réellement les longueurs. Ces techniques vous permettent de devenir très proches de la limite de Shannon. P>

  J'ai décidé de donner votre idée originale (constante N, supprimer des bits inutilisés) un essai pour le plaisir et voici la mise en œuvre naïve que je suis venu Avec: P>

  #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]);
  }
  

Je ne pense pas que vous puissiez éviter d'itération à travers les éléments. Le codage d'Afaik Huffman nécessite les fréquences des "symboles", qui sauf si vous connaissez les statistiques du "processus" générant les entiers, vous devrez calculer (en itérant à tous les éléments).

Si vous avez des tailles fixes, par exemple Vous savez que votre numéro est 38 bits plutôt que 64, vous pouvez créer des structures à l'aide de spécifications de bits. Amusant vous avez également des éléments plus petits pour vous installer 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;
};