Click here to Skip to main content
15,868,016 members
Articles / Programming Languages / C#

Word Aligned Hybrid (WAH) Compression for BitArrays

Rate me:
Please Sign up or sign in to vote.
4.89/5 (35 votes)
22 Jul 2011CPOL6 min read 127.5K   2.8K   75  
Word Aligned Hybrid (WAH) Compression for BitArrays
This is an old version of the currently published article.

Introduction

After much searching the internet for a .net implementation for WAH compressed BitArray and not finding one, I decided to write and publish an article here so we the .net community are not left out as all the implementations are in the java language.  This ties into a pretty advanced topic of bitmap indexing techniques for databases and I needed this for my upcoming RaptorDB Document data-store database engine.

ٌWhat is it?

A BitArray is a data structure in .net library for storing true/false or bits of data in a compact form within an array of Int32 objects. A WAH or word-aligned hybrid BitArray is a special run length compressed version of a BitArray which saves a lot of space and memory. All the implementations that exist in java essentially duplicate the functionality of a BitSet that is the AND, OR, NOT and XOR operations with the compressed internal storage format.

In my implementation I defer the functionality of the BitArray to itself and just add compression and decompression routines. This is much faster than the java way at the expense of memory usage, to overcome this I have also added a FreeMemory method to release the BitArray contents and keep the compressed contents. Arguably if you are using 100s million bits then a full implementation is more performant than my implementation but for most of our usecases we are at most in the 10s millions of bits range.

This original method was invented at the Berkeley Labs of US Department of Energy, it is a project named FastBit and is used for high energy physics department experiments, you can see it here : FastBit site  

Why should I care?

So what! you ask?, well as mentioned before BitArrays are used in an indexing technique called bitmap indexes (wiki) and Column based databases which store data in columns instead of rows, a example which you might know is Microsoft's PowerPivot for Excel which can process millions of rows in seconds. Interestingly Microsoft has only recently announced the implementation of bitmap indexes in the upcoming SQL Server platform post 2008 R2. It has long been in use by other RDBM vendors like Oracle.

How it works

The WAH compression algorithm is as follows:

  1. take 31 bits from the array.
  2. if all zeros then increment the zero count by 31.
    1. if ones count > 0 then output 32 bits with bit 32 =1 and bit 31=1 and 0-30 = ones count
  3. if all ones then increment the ones count by 31.
    1. if zeros count >0 then output 32 bits with bit 32=1 and bit 31=0 and 0-30 = zeros count
  4. else output the 31 bits as 32 bits with bit 32 = 0.
    1. if zeros or ones count >0 then output as above before.

From the above in the worst case you will get N/31 more bits encoded or about 3% increase in size to the original. 

What you get

WAHBitArray is essentially the same as the standard BitArray in the .net framework with the following additions:

  • FreeMemory() : this will first compress the internal BitArray then free the the memory it used.
  • GetCompressed() : this will compress the current BitArray then return them as an array of uint.
  • CountOnes() , CountZeros() : will count the respective bits in the array.
  • GetBitIndexes(bool) : will return an enumeration using yield of the respective bit position for example if the bit array contains 10001... this will return integers 0,4,... if the bool parameter was true<code> and 1,2,3,... if bool was false.
  • Get(), Set() : methods implemented with auto resizing and no exceptions.
  • DebugPrint() : generates a string of 1 and 0 values

Using the code   

To create a WAHBitArray you can do the following :
WAHBitArray ba1 = new WAHBitArray(1000000); // 1 million bits

WAHBitArray ba2 = new WAHBitArray(new BitArray(2000000)); // 2 million bits from another bitarray

WAHBitArray ba3 = new WAHBitArray(1000000, new uint[] { /* compressed values here */}); // from a compressed list of uint 


To perform operations you can do the following

C#
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
}

Using the code v1.3

As of version 1.3 you don't need to specify the size of the BitArray and all operations will auto resize as needed.

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  

Points of Interest

  • BitArray class is sealed by Microsoft so inheriting for it was not possible.
  • BitArray throws a exception if the length of two
    BitArrays
    are not equal on bit operations, WAHBitArray makes then the same as the largest before operations.  
  • BitArray must be resized in 32 increments otherwise it mangles the compression bits.

History   

  • Initial Release v1.0 : 22nd June 2011
  • Update v1.1 : 24th June 2011 
    • bit operations now return a WAHBitArray instead of BitArray
    • bit operation will take either a WAHBitArray or a BitArray as the input
    • CountZeros(), CountOnes() methods added
    • GetBitIndexes() method added 
  • Update v1.2 : 28th June 2011
    • get, set methods with auto resizing
  • Update v1.3 : 23rd July 2011
    • removed the need to specify the initial size
    • bug fix resize in 32 increments 
    • bug fix bitarray arithmetic 
    • DebugPrint() method implemented

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Architect -
United Kingdom United Kingdom
Mehdi first started programming when he was 8 on BBC+128k machine in 6512 processor language, after various hardware and software changes he eventually came across .net and c# which he has been using since v1.0.
He is formally educated as a system analyst Industrial engineer, but his programming passion continues.

* Mehdi is the 5th person to get 6 out of 7 Platinum's on Code-Project (13th Jan'12)
* Mehdi is the 3rd person to get 7 out of 7 Platinum's on Code-Project (26th Aug'16)

Comments and Discussions

Discussions on this specific version of this article. Add your comments on how to improve this article here. These comments will not be visible on the final published version of this article.