位数组的字对齐混合（WAH）压缩

Mehdi Gholam

4.89/5 (35投票s)

2011年6月22日

CPOL

6分钟阅读

149840

3083

位数组的字对齐混合（WAH）压缩

引言

在互联网上搜索 .NET 实现的 WAH 压缩位数组未果后，我决定在这里撰写并发布一篇文章，以便 .NET 社区不会被遗漏，因为所有可用的实现都是用 Java 语言编写的。这与数据库的位图索引技术这一相当高级的主题相关，我需要它用于我的 RaptorDB 文档数据存储数据库引擎。

这是什么？

BitArray 是 .NET 库中的一种数据结构，用于以紧凑的形式在 Int32 对象数组中存储 true/false 或数据位。WAH 或字对齐混合 BitArray 是 BitArray 的一种特殊行程长度压缩版本，可以节省大量空间和内存。Java 中存在的所有实现本质上都复制了 BitSet 的功能，即使用压缩的内部存储格式进行 AND、OR、NOT 和 XOR 操作。

在我的实现中，我将 BitArray 的功能委托给它自身，只添加了压缩和解压缩例程。这比 Java 方式快得多，但代价是内存使用。为了克服这个问题，我还添加了一个 FreeMemory 方法来释放 BitArray 的内容并保留压缩后的内容。可以说，如果你使用 1 亿位，那么完整的实现比我的实现性能更高，但对于我们大多数用例，我们最多在 1000 万位的范围内。

这个原始方法是由美国能源部伯克利实验室发明的；这是一个名为 FastBit 的项目，用于高能物理系的实验；你可以在这里看到它：FastBit 网站。

我为什么要关心？

你可能会问，那又怎样？嗯，如前所述，BitArray 用于一种称为位图索引（维基百科）的索引技术和按列而不是按行存储数据的基于列的数据库。你可能知道的一个例子是 Microsoft 的 PowerPivot for Excel，它可以在几秒钟内处理数百万行。有趣的是，Microsoft 最近才宣布在即将发布的 SQL Server 平台（2008 R2 之后）中实现位图索引。它长期以来一直被 Oracle 等其他 RDBM 供应商使用。

工作原理

WAH 压缩算法如下：

从数组中取出 31 位。
如果全为零，则将零计数增加 31。
1. 如果一计数 > 0，则输出 32 位，其中第 32 位 = 1，第 31 位 = 1，第 0-30 位 = 一计数。
如果全为一，则将一计数增加 31。
1. 如果零计数 > 0，则输出 32 位，其中第 32 位 = 1，第 31 位 = 0，第 0-30 位 = 零计数。
否则将 31 位作为 32 位输出，其中第 32 位 = 0。
1. 如果零或一计数 > 0，则如上输出。

从上面可以看出，在最坏情况下，你将获得比原始数据多 N/31 位编码，即大小增加约 3%。

你得到什么

WAHBitArray 本质上与 .NET Framework 中的标准 BitArray 相同，并增加了以下功能：

FreeMemory()：这将首先压缩内部 BitArray，然后释放它使用的内存。
GetCompressed()：这将压缩当前的 BitArray，然后将其作为 uint 数组返回。
CountOnes(), CountZeros()：将计算数组中相应的位数。
GetBitIndexes(bool)：将使用 yield 返回相应位位置的枚举；例如，如果位数组包含 10001...，如果 bool 参数为 true，则返回整数 0,4,...，如果 bool 为 false，则返回 1,2,3,...。
Get(), Set()：实现自动调整大小且不抛出异常的方法。
DebugPrint()：生成 1 和 0 值的 string。

Using the Code

要创建 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

要执行操作，你可以执行以下操作：

WAHBitArray result1 = ba1.And( ba2);
WAHBitArray result2 = ba1.Or( ba3);
WAHBitArray result3 = ba1.Xor( ba2);

long count = result1.CountOnes(); // will count the true values

result2.Set(2000000, true); // will resize as needed
bool b = result2.Get(3000000); // will resize as needed

foreach(int pos in result2.GetBitIndexes(true))
{
    ReadDatabaseRecordNumber(pos); // pos is the index of true values
}

使用代码 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 类被 Microsoft 密封，因此无法继承。
如果两个 BitArray 的长度在位操作时不相等，BitArray 会抛出异常，而 WAHBitArray 会在操作前使它们与最大的那个相同。
BitArray 必须以 32 为增量调整大小，否则会破坏压缩位。

版本 2.0

为了提高位压缩和解压缩的速度，以及 .NET Framework 实现不提供对 BitArray 内部数据结构的访问这一事实，我不得不重写 WAHBitArray 中的所有 BitArray 功能。

使用 Reflector 查看 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 位数据可能与两个相邻的 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;
}

版本 2.5

此版本是对 RaptorDB 中所做工作的反馈，是对所有例程的全面修订，侧重于多线程访问和并发问题。一个非常重要的经验教训是在使用资源的源头进行锁定，而不是在更高层次进行锁定，这解决了最低层次的并发问题，并节省了大量麻烦和调试时间。

大部分代码已经过重新格式化和优化。我对这个版本的正确性非常有信心，因为它正在 RaptorDB 中进行最大限度的测试。

历史

初始发布 v1.0: 2011 年 6 月 22 日
更新 v1.1: 2011 年 6 月 24 日
- 位操作现在返回 WAHBitArray 而不是 BitArray
- 位操作将接受 WAHBitArray 或 BitArray 作为输入
- 添加了 CountZeros()、CountOnes() 方法
- 添加了 GetBitIndexes() 方法
更新 v1.2: 2011 年 6 月 28 日
- 具有自动调整大小功能的 Get、Set 方法
更新 v1.3: 2011 年 7 月 23 日
- 不再需要指定初始大小
- 修复了 32 增量调整大小的错误
- 修复了 BitArray 算术中的错误
- 实现了 DebugPrint() 方法
更新 v2.0
- 彻底重写
- 优化了压缩和解压缩，速度提高了约 9 倍
- 所有位操作都在内部完成，无需 BCL BitArray
更新 v2.5: 2012 年 5 月 10 日
- 位线程安全访问
- 优化了 Count() 方法
- 位在高阶 int[] 中设置
- 修复了获取未压缩位的错误
- GetBitIndexes() 将只返回一位
更新 v2.6: 2013 年 6 月 15 日
- 修复了边缘情况解压缩代码的错误（感谢 andrey269）
更新 v2.6.1: 2013 年 6 月 22 日
- 修复了一个逻辑错误
- 添加了一个单元测试项目
更新 v2.6.2: 2013 年 10 月 6 日
- 修复了 WriteOnes() 中最后剩余位输出的错误
更新 v2.7.0: 2015 年 3 月 1 日
- 来自 RaptorDB 的反馈修复和更改