Alphabet partitioning for compressed rank/select and applications

DOI10.1007/978-3-642-17514-5_27MaRDI QIDQ3060784zbMATH OpenOpenAlexFDO

Authors Jérémy Barbay, Travis Gagie, Yakov Nekrich, Gonzalo Navarro

Publication date 9 December 2010

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17514-5_27

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Recommendations

• Efficient fully-compressed sequence representations
• Compressed Data Structures for Dynamic Sequences
• Improved Dynamic Rank-Select Entropy-Bound Structures
• Compressed representations of sequences and full-text indexes
• Rank/select on dynamic compressed sequences and applications

Cited in

(22)

• On compressing permutations and adaptive sorting
• Top-\(k\) document retrieval in optimal space
• Space-efficient substring occurrence estimation
• Optimal skeleton Huffman trees
• Colored range queries and document retrieval
• Optimal skeleton and reduced Huffman trees
• Compressed Data Structures for Dynamic Sequences
• A space efficient direct access data structure
• Engineering a lightweight external memory suffix array construction algorithm
• LRM-trees: compressed indices, adaptive sorting, and compressed permutations
• Compact representation of graphs of small clique-width
• New space/time tradeoffs for top-\(k\) document retrieval on sequences
• Random access to Fibonacci encoded files
• Practical entropy-compressed rank/select dictionary
• Compact binary relation representations with rich functionality
• Succinct encoding of binary strings representing triangulations
• Distribution-aware compressed full-text indexes
• General document retrieval in compact space
• Compact representation of graphs with bounded bandwidth or treedepth
• Accelerated partial decoding in wavelet trees
• Wavelet trees for all
• A practical alphabet-partitioning rank/select data structure

This page was built for publication: Alphabet partitioning for compressed rank/select and applications

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