High-order entropy compressed bit vectors with rank/select

DOI10.3390/A7040608MaRDI QIDQ1736624zbMATH OpenOpenAlexFDO

Authors Kai Beskers, Johannes Fischer

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a7040608

zbMATH Keywords

data compressiondesign and analysis of algorithmsimplementation and testing of algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Nonnumerical algorithms (68W05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Practical entropy-compressed rank/select dictionary
• scientific article; zbMATH DE number 2079421
• Optimal indexes for sparse bit vectors
• Rank and select operations on a word
• Dynamic Entropy-Compressed Sequences and Full-Text Indexes

Cites work

• A note on sequence prediction over large alphabets
• A simple storage scheme for strings achieving entropy bounds
• An analysis of the Burrows-Wheeler transform
• C source code obfuscator
• Efficient fully-compressed sequence representations
• Fully-functional succinct trees
• Practical entropy-compressed rank/select dictionary
• Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
• Ultra-succinct representation of ordered trees with applications

Cited in

(4)

• Faster practical block compression for rank/select dictionaries
• A Learned Approach to Design Compressed Rank/Select Data Structures
• Practical entropy-compressed rank/select dictionary
• Compressed persistent index for efficient rank/select queries

This page was built for publication: High-order entropy compressed bit vectors with rank/select

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736624)