High-order entropy compressed bit vectors with rank/select (Q1736624)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: High-order entropy compressed bit vectors with rank/select |
scientific article; zbMATH DE number 7042227
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | High-order entropy compressed bit vectors with rank/select |
scientific article; zbMATH DE number 7042227 |
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
0.7901505827903748
0 references
0.7897169589996338
0 references
