High-Order Entropy Compressed Bit Vectors with Rank/Select

Algorithms

Kai Beskers¹  Johannes Fischer² 

[1] Institut für Theoretische Informatik, Karlsruhe Institute of Technology, Kaiserstraße 12, 76131 Karlsruhe, Germany; E-Mail:;Fakultät für Informatik, Technical University of Dortmund, Otto-Hahn-Straße 14, 44227 Dortmund, Germany

关键词: design and analysis of algorithms;    data compression;    implementation and testing of algorithms;   

DOI  :  10.3390/a7040608

来源: mdpi

【 摘 要 】

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 . Our implementations achieve very good compression ratios, while showing only a modest increase in query time.

【 授权许可】

CC BY   
© 2014 by the authors; licensee MDPI, Basel, Switzerland.