整数数组的位打包

Question

我有一个整数数组,让我们假设它们是类型int64_t.现在,我知道n每个整数的每个第一位都是有意义的(也就是说,我知道它们受到某些界限的限制).

以所有不必要的空间被移除的方式转换数组的最有效方法是什么(即我有第一个整数a[0],第二个是a[0] + n bits等等)？

我希望它尽可能地通用,因为它n会不时变化,但我想可能会对n2或者某些特定功能进行智能优化.

当然我知道我可以只重复价值超过价值,我只想问你StackOverflowers你是否能想到更聪明的方式.

编辑:

这个问题不是关于压缩数组以尽可能减少空间.我只需n bits要从每个整数"切割" 并给出数组,我知道n我可以安全切割的位的确切位置.

Answer 1

我同意keraba你需要使用像霍夫曼编码或者Lempel-Ziv-Welch算法这样的东西.你所说的方式包装的问题在于你有两个选择:

• 选择一个常数n,以便可以表示最大的整数.
• 允许n在值之间变化.

第一个选项相对容易实现,但实际上会浪费大量空间,除非所有整数都很小.

第二种选择的主要缺点是你必须在输出比特流中以某种方式传递n的变化.例如,每个值必须具有与之关联的长度.这意味着您为每个输入值存储两个整数(尽管是较小的整数).使用此方法很有可能增加文件大小.

Huffman或LZW的优点在于它们以这样的方式创建码本:可以从输出比特流导出码的长度而不实际存储长度.这些技术使您可以非常接近香农极限.

我决定给你最初的想法(常数n,删除未使用的位和包装)尝试一下,这是我提出的天真实现:

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

这是非常低效的,因为一步一步,但这是实现它的最简单的方法,而不处理endianess的问题.我没有用很多值来测试它,只测试了测试中的值.此外,没有边界检查,并假设输出缓冲区足够长.所以我要说的是,这段代码可能只对教育目的有帮助,可以帮助您入门.

Answer 2

今天我发布了:PackedArray:紧密包装无符号整数(github项目).

它实现了一个随机访问容器,其中项目在位级别打包.换句话说,它就像你能够操纵eg uint9_t或uint17_t数组一样:

PackedArray principle:
  . compact storage of <= 32 bits items
  . items are tightly packed into a buffer of uint32_t integers

PackedArray requirements:
  . you must know in advance how many bits are needed to hold a single item
  . you must know in advance how many items you want to store
  . when packing, behavior is undefined if items have more than bitsPerItem bits

PackedArray general in memory representation:
  |-------------------------------------------------- - - -
  |       b0       |       b1       |       b2       |
  |-------------------------------------------------- - - -
  | i0 | i1 | i2 | i3 | i4 | i5 | i6 | i7 | i8 | i9 |
  |-------------------------------------------------- - - -

  . items are tightly packed together
  . several items end up inside the same buffer cell, e.g. i0, i1, i2
  . some items span two buffer cells, e.g. i3, i6

Answer 3

大多数压缩算法都接近编码整数所需的最小熵,例如,霍夫曼编码,但像数组一样访问它将是非平凡的.

Answer 4

我知道这似乎是显而易见的事情，因为我确信确实有一个解决方案，但为什么不使用较小的类型，例如uint8_t（最大 255）？或uint16_t（最大 65535）？int64_t我确信您可以使用定义的值和/或操作等进行位操作，但是，除了学术练习之外，为什么呢？

在学术练习方面，《Bit Twiddling Hacks》是一本很好的读物。