@inproceedings{6e44976b82ea4db79e599a72d4181a0f,
title = "Hybrid compression of bitvectors for the FM-index",
abstract = "Compressed bit vectors supporting rank and select operations are the workhorse of compressed data structures. We propose a hybrid scheme for implementing compressed bit vectors, which divides the bit vector into blocks and then chooses the encoding of each block separately from a number of different encoding methods. Hybrid encoding is particularly suitable for bit vectors that have lots of local and regional variation, such as those present in the FM-index, a popular compressed data structure for pattern matching. We propose a specific hybrid combination of three simple encoding methods for FM-index bit vectors achieving superior space-time tradeoffs in experiments.",
keywords = "Compressed bitvectors, FM-index, Succinct data structures",
author = "Juha K{\"a}rkk{\"a}inen and Dominik Kempa and Puglisi, \{Simon J.\}",
year = "2014",
doi = "10.1109/DCC.2014.87",
language = "English",
isbn = "9781479938827",
series = "Data Compression Conference Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "302--311",
booktitle = "Proceedings - DCC 2014",
note = "2014 Data Compression Conference, DCC 2014 ; Conference date: 26-03-2014 Through 28-03-2014",
}