Hybrid compression of bitvectors for the FM-index

[back to the main page]

We present a C++ implementation of a hybrid encoding of compressed bitvectors, which divides the bitvector into blocks and then chooses the encoding of each block separately from a number of different encoding methods. The resulting combination achieves all-around good performance in terms of time and space.

Details and experimental comparison with other methods can be found in [1].
See the README in the package for more information.



Implemented by


  1. Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi. Hybrid Compression of Bitvectors for the FM-Index.
    In Proc. 2014 Data Compression Conference (DCC 2014), IEEE Computer Society, 2014, pp. 302-311.