Optimal Lower and Upper Bounds for Representing Sequences

DOI10.1145/2629339zbMath1398.68103arXiv1111.2621OpenAlexW2164107415MaRDI QIDQ4962192

Djamal Belazzougui, Gonzalo Navarro

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

succinct data structurestext indexingstring compression

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 (23)

r-indexing the eBWT ⋮ Grammar compressed sequences with rank/select support ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Compressed dynamic range majority and minority data structures ⋮ A new class of string transformations for compressed text indexing ⋮ Random access in persistent strings and segment selection ⋮ The nearest colored node in a tree ⋮ Constructing and indexing the bijective and extended Burrows-Wheeler transform ⋮ Succinct data structures for nearest colored node in a tree ⋮ Unnamed Item ⋮ Block trees ⋮ Fast compressed self-indexes with deterministic linear-time construction ⋮ Unnamed Item ⋮ Lempel-Ziv-78 compressed string dictionaries ⋮ Range majorities and minorities in arrays ⋮ Efficient and compact representations of some non-canonical prefix-free codes ⋮ Refining the \(r\)-index ⋮ The alternating BWT: an algorithmic perspective ⋮ Optimal rank and select queries on dictionary-compressed text ⋮ A new class of searchable and provably highly compressible string transformations ⋮ Tree path majority data structures ⋮ Space-efficient Huffman codes revisited ⋮ Space efficient merging of de Bruijn graphs and Wheeler graphs

This page was built for publication: Optimal Lower and Upper Bounds for Representing Sequences