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.

News

• 2014-10-17: Hybrid bitvector is now a part of sdsl-lite library.
• 2014-08-21: New version (0.2) available [changelog].

Downloads

• hybrid bitvector 0.2
• hybrid bitvector 0.1

Implemented by

• Juha Kärkkäinen
• Dominik Kempa

References

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.
   [IEEE]