Optimal rank and select queries on dictionary-compressed text

DOI10.4230/LIPIcs.CPM.2019.4OpenAlexW2962888942MaRDI QIDQ5088891

Nicola Prezza

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/1811.01209

zbMATH Keywords

rankdictionary compressionselectstring attractors

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (3)

Substring complexities on run-length compressed strings ⋮ Sensitivity of string compressors and repetitiveness measures ⋮ Block trees

Cites Work

• Unnamed Item
• Representing trees of higher degree
• Universal compressed text indexing
• Tree compression using string grammars
• Optimal bounds for the predecessor problem and related problems
• Collage system: A unifying framework for compressed pattern matching.
• Grammar compressed sequences with rank/select support
• Compressed indexes for dynamic text collections
• Access, Rank, and Select in Grammar-compressed Strings
• Should Tables Be Sorted?
• Data compression via textual substitution
• On the Complexity of Finite Sequences
• Grammar-based codes: a new class of universal lossless source codes
• Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings
• Optimal Lower and Upper Bounds for Representing Sequences
• Complete inverted files for efficient text retrieval and analysis
• At the roots of dictionary compression: string attractors
• Random Access to Grammar-Compressed Strings and Trees

This page was built for publication: Optimal rank and select queries on dictionary-compressed text