Practical Entropy-Compressed Rank/Select Dictionary

DOI10.1137/1.9781611972870.6zbMath1428.68134OpenAlexW1949346071MaRDI QIDQ5233491

Kunihiko Sadakane, Daisuke Okanohara

Publication date: 11 September 2019

Published in: 2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611972870.6

Mathematics Subject Classification ID

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

Related Items (42)

Optimal encodings for range majority queries ⋮ Block graphs in practice ⋮ Document listing on repetitive collections with guaranteed performance ⋮ Space efficient data structures for nearest larger neighbor ⋮ Range selection and predecessor queries in data aware space and time ⋮ A space efficient direct access data structure ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Entropy-bounded representation of point grids ⋮ Colored range queries and document retrieval ⋮ Algorithms to compute the Burrows-Wheeler similarity distribution ⋮ Efficient construction of the BWT for repetitive text using string compression ⋮ New algorithms on wavelet trees and applications to information retrieval ⋮ Wavelet trees for all ⋮ Optimal skeleton and reduced Huffman trees ⋮ Efficient fully-compressed sequence representations ⋮ Optimal indexes for sparse bit vectors ⋮ Better External Memory LCP Array Construction ⋮ Practical compressed suffix trees ⋮ High-order entropy compressed bit vectors with rank/select ⋮ Fixed block compression boosting in FM-indexes: theory and practice ⋮ Efficient Compression and Indexing of Trajectories ⋮ Optimal Skeleton Huffman Trees ⋮ A Self-index on Block Trees ⋮ Approximate query processing over static sets and sliding windows ⋮ Efficient dynamic range minimum query ⋮ Simple and efficient fully-functional succinct trees ⋮ LRM-trees: compressed indices, adaptive sorting, and compressed permutations ⋮ Applications of non-uniquely decodable codes to privacy-preserving high-entropy data representation ⋮ Space-efficient construction of Lempel-Ziv compressed text indexes ⋮ New space/time tradeoffs for top-\(k\) document retrieval on sequences ⋮ Unnamed Item ⋮ Accelerated partial decoding in wavelet trees ⋮ Fast and compact planar embeddings ⋮ Haplotype-aware graph indexes ⋮ Locally Compressed Suffix Arrays ⋮ Fast Compressed Tries through Path Decompositions ⋮ General Document Retrieval in Compact Space ⋮ Compact and succinct data structures for multidimensional orthogonal range searching ⋮ Faster compressed quadtrees ⋮ DenseZDD: a compact and fast index for families of sets ⋮ Improved and extended locating functionality on compressed suffix arrays ⋮ Practical Compact Indexes for Top-kDocument Retrieval

This page was built for publication: Practical Entropy-Compressed Rank/Select Dictionary