字对齐混合（WAH）压缩BitArrays
{A}
简介
华压缩的BitArray。NET实现互联网和搜索，没有找到一个后，我决定撰写和发表的文章在这里所以。NET社区不会被排除在外，所有可用的实现在Java语言中。这关系到一个位图索引数据库技术非常先进的话题，我需要为我即将到来的RaptorDB文件数据存储的数据库引擎。它是什么？
一个BitArray中是一个真/假或位在一个紧凑的形式的数据存储在Int32的对象数组。NET库的数据结构。哇音或字对齐混合BitArray中是一个特殊的运行长度压缩一个BitArray中节省了很多空间和内存的版本。在Java中存在的所有的实现基本上是重复的，压缩内部存储格式一个bitset的功能，即是AND，OR，NOT，和XOR操作。
我在执行中，我推迟本身的BitArray的功能，只需要添加压缩和解压例程。这是比牺牲的内存使用Java的方式更快。为了克服这个问题，我还添加了一个FreeMemory的方法来释放BitArray中的内容，并保持压缩的内容。可以说，如果您使用的是100万比特，然后全面实施执行比我更高性能，但对于大多数用例，我们大部分是在10亿位的范围。
这种原始的方法是在美国能源部的伯克利实验室发明的，它是一个名为FastBit项目和用于高能物理部实验，你可以在这里看到:。我为什么要关心？
，你还等什么？问。那么，提到之前，BitArrays所谓的位图索引（{A6}）和列列而不是行存储数据的数据库索引技术。你可能知道的一个例子是微软的Excel中的PowerPivot可以在几秒钟内处理数百万行。有趣的是，微软最近才宣布，在即将到来的SQL Server平台的位图索引的执行情况，2008年后的R2。长期以来，人们一直在使用的其他RDBM厂商，如Oracle。它如何工作
华压缩算法如下:取31位从阵列。如果所有的零，然后递增31计数为零。如果的计数GT;位32 = 1和第31位0，然后输出32位= 1和0-30的计数。如果所有的，然后递增的计数31。如果零计数GT;位32 = 1和第31位0，然后输出32位= 0和0-30 =零计数。否则输出为32位位32 = 0的31位。零或者如果罪名GT;如上0，然后输出。
从上面的，在最坏的情况下，你会得到更多N/31位编码或3％左右提高到原来的大小。您的
WAHBitArray本质上是相同的NET Framework中的标准的BitArray，添加以下。FreeMemory（）:这将首先压缩内部的BitArray，然后释放它使用的内存。GetCompressed（）:这将压缩目前的BitArray，然后返回一个UINT数组。CountOnes CountZeros（），（）:计算数组中的相应位。GetBitIndexes（BOOL）:返回一个枚举，使用各自的位位置的产量，例如，如果该位的数组包含10001 ...这将返回整数0,4，...如果bool参数是真实的，1,2,3，... ...如果bool是假的。（），设置（）:方法与实施自动调整大小，并没有例外。DebugPrint（）:生成一串1和0值。使用代码
要创建一个WAHBitArray，你可以做到以下几点:WAHBitArray ba1 = new WAHBitArray(1000000); // 1 million bits
// 2 million bits from another bitarray
WAHBitArray ba2 = new WAHBitArray(new BitArray(2000000));
WAHBitArray ba3 = new WAHBitArray(1000000, new uint[] { /* compressed values here */});
// from a compressed list of uint
执行操作，您可以执行以下操作:{C}使用代码V1.3
1.3版本，你并不需要指定大小的BitArray中的所有操作，会自动根据需要调整大小。WAHBitArray ba1 = new WAHBitArray(); // no need to specify the size
WAHBitArray ba3 = new WAHBitArray(new uint[] { /* compressed values here */});
// from a compressed list of uint
对于额外的速度，在压缩和解压的位，而事实上，不给BitArray中的内部数据结构的访问。NET Framework实现，我不得不在WAHBitArray重写所有的BitArray功能。
使用反射看到的BCL的BitArray之一的内部实现，可以看到下面的片段:// AND operation
for (int i = 0; i < array.Length; i++)
array[i] &= val[i];
// OR operation
for (int i = 0; i < array.Length; i++)
array[i] |= val[i];
// XOR operation
for (int i = 0; i < array.Length; i++)
array[i] ^= val[i];
正如你可以看到，位操作完成的Int32值。
访问内部UINT现在，[]位，压缩方法，得到31位的数据块，而不是逐个。这是在Take31Bits（）方法，发现在_uncompressed列表中相邻的两个uint值，并有如下几个位操作:public WAHBitArray And(WAHBitArray op)
{
this.CheckBitArray(); // check the bit array is uncompressed
uint[] ints = op.GetUncompressed(); // get the values
FixSizes(ints, _uncompressed); // make the sizes the same
for (int i = 0; i < ints.Length; i++)
ints[i] &= _uncompressed[i]; // do the AND operation
return new WAHBitArray(false, ints); // return a new object
}
压缩及解压缩例程被改写操作UINT []数组如下:private void Compress()
{
_compressed = new List<uint>();
uint zeros = 0;
uint ones = 0;
int count = _uncompressed.Count << 5;
for (int i = 0; i < count; )
{
uint num = Take31Bits(i);
i += 31;
if (num == 0)
{
zeros += 31;
FlushOnes(ref ones);
}
else if (num == 0x7fffffff)
{
ones += 31;
FlushZeros(ref zeros);
}
else
{
FlushOnes(ref ones);
FlushZeros(ref zeros);
_compressed.Add(num);
}
}
FlushOnes(ref ones);
FlushZeros(ref zeros);
}
private void Uncompress()
{
int index = 0;
List<uint> list = new List<uint>();
if (_compressed == null)
return;
foreach (uint ci in _compressed)
{
if ((ci & 0x80000000) == 0) // literal
{
this.Write31Bits(list, index, ci & 0x7fffffff);
index += 31;
}
else
{
uint c = ci & 0x3ffffff;
if ((ci & 0x40000000) > 0) // ones count
this.WriteBits(list, index, c);
index += (int)c;
}
}
this.ResizeAsNeeded(list, index);
_uncompressed = list;
}
因为服用或更新31位的数据可以重叠2个相邻的uint值，一些位按摩如下:private uint Take31Bits(int index)
{
long l1 = 0;
long l2 = 0;
long l = 0;
long ret = 0;
int off = (index % 32);
int pointer = index >> 5;
l1 = _uncompressed[pointer];
pointer++;
if (pointer < _uncompressed.Count)
l2 = _uncompressed[pointer];
l = (l1 << 32) + l2;
ret = (l >> (32 - off)) & 0x07fffffff;
return (uint)ret;
}
