Compressed Bit Vectors with Rank and Select Support

  • The main objective of this Bachelor's thesis is to develop a compression for the bit vector, such that rank and select queries still work (reasonable) fast. To this end, the bit vector should be compressed in such a way that it can be decompressed on-the-fly.

    An optional goal of this thesis is the development of an encoding specifically for the bit vectors produced by PaCHash. These bit vectors have some properties which may be used to compress them even better than when using entropy encoding.
     

    For more information, see the detailed description.