High-order entropy compressed bit vectors with rank/select (Q1736624)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | High-order entropy compressed bit vectors with rank/select |
scientific article |
Statements
High-order entropy compressed bit vectors with rank/select (English)
0 references
26 March 2019
0 references
Summary: We design practical implementations of data structures for compressing bit-vectors to support efficient rank-queries (counting the number of ones up to a given point). Unlike previous approaches, which either store the bit vectors plainly, or focus on compressing bit-vectors with low densities of ones or zeros, we aim at low entropies of higher order, for example \(101010 \dots 10\). Our implementations achieve very good compression ratios, while showing only a modest increase in query time.
0 references
design and analysis of algorithms
0 references
data compression
0 references
implementation and testing of algorithms
0 references
0 references
