整数数组的位压缩

我同意keraba的观点,你需要使用像huffman编码或者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]);
}

这是非常低效的,因为一次只执行一个步骤,但这是实现它而不处理持久性问题的最简单方法。我也没有用大范围的值来测试这个,只是测试中的值。此外,没有边界检查,并且假设输出缓冲区足够长。所以我要说的是,这个代码可能只适合教育目的,让你开始。

大多数压缩算法都会接近对整数进行编码所需的最小熵,例如huffman编码,但是像数组一样访问它是不容易的。

今天我发布了: PackedArray: Packing Unsigned Integers Tightly ( github project )

它实现了一个随机访问容器,其中的项在位级别打包。换句话说,它的行为就好像你能够操纵一个 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

我知道这似乎是一个显而易见的说法,因为我确信实际上有一个解决方案,但是为什么不使用较小的类型,比如 uint8_t (max 255)?或 uint16_t (max 65535)?我相信你可以在一个 int64_t 使用定义的值和/或运算等,但是,除了学术练习之外,为什么?

关于学术练习, Bit Twiddling Hacks 是一本好书。

如果您有固定的大小,例如您知道您的数字是38位而不是64位,那么您可以使用位规范来构建结构。有趣的是你还有一些小元素可以放在剩下的空间里。

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;
};

如果没有一些跳跃,这不是大/小端的安全,因此只能在程序中使用,而不能在导出的数据格式中使用。它经常用于将布尔值存储在单个位中,而不定义移位和掩码。

从jason b的实现开始,我最终编写了自己的版本,它处理位块而不是单个位。一个区别是它是lsb:它从最低的输出位开始到最高的输出位。这只会使使用二进制转储文件(如Linux)进行读取变得更加困难 xxd -b . 作为一个细节, int* 可以简单地更改为 int64_t* ,最好是 unsigned . 我已经用几百万个阵列测试了这个版本,它看起来很可靠,所以我将分享其余的:

int pack2(int *input, int nin, unsigned char* output, int n)
{
        int obit = 0;
        int ibit = 0;
        int ibite = 0;
        int nout = 0;
        if(nin>0) output[0] = 0;
        for(int i=0; i<nin; i++)
        {
                ibit = 0;
                while(ibit < n) {
                        ibite = std::min(n, ibit + 8 - obit);
                        output[nout] |= (input[i] & (((1 << ibite)-1) ^ ((1 << ibit)-1))) >> ibit << obit;
                        obit += ibite - ibit;
                        nout += obit >> 3;
                        if(obit & 8) output[nout] = 0;
                        obit &= 7;
                        ibit = ibite;
                }
        }
        return nout;
}

int unpack2(int *oinput, int nin, unsigned char* ioutput, int n)
{
        int obit = 0;
        int ibit = 0;
        int ibite = 0;
        int nout = 0;
        for(int i=0; i<nin; i++)
        {
                oinput[i] = 0;
                ibit = 0;
                while(ibit < n) {
                        ibite = std::min(n, ibit + 8 - obit);
                        oinput[i] |= (ioutput[nout] & (((1 << (ibite-ibit+obit))-1) ^ ((1 << obit)-1))) >> obit << ibit;
                        obit += ibite - ibit;
                        nout += obit >> 3;
                        obit &= 7;
                        ibit = ibite;
                }
        }
        return nout;
}

我认为您不能避免在元素之间迭代。 afaik-huffman编码需要“符号”的频率,除非知道生成整数的“进程”的统计信息,否则必须计算(通过遍历每个元素)。